# Confusion about the proof that optimizing InfoNCE equals to maximizing mutual information

In the appendix of Representation Learning with Contrastive Predictive Coding, van den Oord et al. prove that optimizing InfoNCE is equivalent to maximize the mutual information between input image $$x_t$$ and the context latent $$c_t$$ as follows: where $$x_{t+k}$$ is the image at time step $$t+k$$, $$X_{neg}$$ is a set of negative samples that do not appear in the sequence $$x_t$$ belongs to, and $$N-1$$ is the negative samples used to compute InfoNCE.

I'm confused about Equation $$(8)$$. van den Oord et al. stressed that Equation $$(8)$$ becomes more accurate as $$N$$ increases, but I cannot see why. Here's my understanding, for $$x_j\in X_{neg}$$, we have $$p(x_j|c_t)\le p(x_j)$$ . Therefore, $$\sum_{x_j\in X_{neg}}{p(x_j|c_t)\over p(x_j)}\le N-1$$ and this does not become accurate as $$N$$ increases. In fact, I think the gap between the left and right of $$\le$$ increases as $$N$$ increases. Do I make any mistake?

Well, conditional probability (density) does not necessarily need to be no greater than its marginal probability (density). That means $$p(x_j|c_t)\le p(x_j)$$ is not always true. For example, consider two discrete r.v.s $$X,Y\in\{0,1\}$$ such that $$P(X=0,Y=0)=0.05,\\ P(X=1,Y=0)=0.05,\\ P(X=0,Y=1)=0.05,\\ P(X=1,Y=1)=0.85$$. We have $$P(X=0)=0.1$$; however, $$P(X=0|Y=0)=0.5$$.