InfoNCE Derivation I have a small question about the derivation in the InfoNCE paper and it is killing me.
In appendix A.1, it is estimating the mutual information with InfoNCE as follows:
$$
\begin{align}
\mathcal{L}_{N}^{opt}&=-\mathbb{E}_{X}log[ \frac{ \frac{ p(x_{t+k}|c_{t}) }{p(x_{t+k})} }{ \frac{ p(x_{t+k}|c_{t}) }{p(x_{t+k})}+\sum_{x_{j}\in X_{neg}}\frac{ p(x_{j}|c_{t}) }{ p(x_{j}) } } ]\tag{6}\\
&=\mathbb{E}_{X}log[ 1+\frac{ p(x_{t+k}) }{ p(x_{t+k})|c_{t} }\sum_{ x_{j}\in X_{neg} }\frac{ p(x_{j}|c_{t}) }{p(x_{j})} ]\tag{7}\\
& \approx \mathbb{E}_{X}log[ 1+\frac{ p(x_{t+k}) }{ p(x_{t+k}|c_{t}) }(N-1)\mathbb{E}_{x_{j}}\frac{ p(x_{j}|c_{t}) }{ p(x_{j}) } ]\tag{8} \\
&=\mathbb{E}_{X}log[ 1+\frac{ p(x_{t+k}) }{ p(x_{t+k}|c_{t}) }(N-1) ]\tag{9}\\
&\ge \mathbb{E}_{X}log[ \frac{ p(x_{t+k}) }{ p(x_{t+k}|c_{t}) }N  ]\tag{10} \\
&= -I(x_{t+k},c_{t})+log(N)\tag{11} \\
\end{align}
$$
I don't understand how to come up with equation (10) from equation(9). To be specific, I don't understand why
$$
\begin{align}
\frac{ p(x_{t+k}) }{ p(x_{t+k}|c_{t}) } \le 1
\end{align}
$$
where $x_{t+k}$ and $c_{t}$ are dependent.
At first I thought it is because $P(X)P(Y)<P(X,Y)$ when $X$ and $Y$ are dependent so I ask this question Joint Probability of Two Dependent Random Variables. However it seems to not be the case.
 A: In what follows, I will drop the subscripts so that $x:=x_{t+k}$ and $c:=c_t$.
Consider $LHS=log [1+{\frac {p(x)}{p(x|c)}}(N-1)]$, the quantity we want to bound.
Then
\begin{eqnarray*}
LHS-log(N)&=&log [{\frac 1 N}+{\frac {p(x)}{p(x|c)}}{\frac {N-1}{N}}]\\
& = & log {\frac {p(x|c)+(N-1)p(x)}{N p(x|c)}}\\
& = & log {\frac {p(x|c)+(N-1)p(x)}{N}}-log p(x|c)\\
& \geq& {\frac 1 N} \log p(x|c)+{\frac {N-1}{N}} \log p(x)-\log p(x|c)\\
& = & {\frac {N-1}N}log {\frac {p(x)}{p(x|c)}}
\end{eqnarray*}
where we have used the concavity of log to go from the 3rd to 4th line.
Rearranging,
$$LHS\geq {\frac {N-1}N}log {\frac {p(x)}{p(x|c)}}+log(N)$$
Now at this point, I am guessing that the authors are considering $N$ to be large enough that ${\frac {N-1}{N}}$ is close enough to 1 for practical purposes. And indeed, earlier on in the derivation of this inequality they make an approximation that is only exact in the limit of large $N$ (eq. 7 to 8). So if we make the approximation ${\frac {N-1}{N}}\approx 1$, then we get
$$LHS\geq \log {\frac {p(x)}{p(x|c)}}+\log N=\log N{\frac {p(x)}{p(x|c)}}$$ as desired.
