Application of Chernoff Bound I was having a read of the paper here: Information Theoretic Limits of Selecting Binary Graphical Models in High Dimensions. I am having a lot of trouble understanding the proof of equation 38 in the text. In particular, I understand the Chernoff Bound as far as,
$$
\frac{1}{n} \log \mathbb{P}_\theta\left[V \geq 0\right] \leq \frac{1}{n} \inf_{s > 0} \log\mathbb{E}_\theta\left[\exp\left\{sV\right\}\right]
$$
However I am not clear on how the subsequent equality follows. 
$$
\frac{1}{n} \inf_{s > 0} \log\mathbb{E}_\theta\left[\exp\left\{sV\right\}\right] \overset{?}{=}  \inf_s \sum_{x\in\left(-1,+1\right)^p} \left[\mathbb{P}_\theta\left(x\right)\right]^{1-s} \left[\mathbb{P}_{\theta'}\left(x\right)\right]^{s}
$$
If someone could explain this equality (perhaps show a few intermediate steps) I would be most appreciative.
 A: Okay, I see you intended me to click on the link and look at the paper. 
That particular line is very difficult because they skip steps, and they also have a typo where they forgot the log.  Here are the steps explained:  
From equation (36) and the definition of $V$ given at the start of the proof of Lemma 3: 
$V = \frac{1}{n}\sum_{i=1}^n \log P_{\theta'}(X_i) - \frac{1}{n}\sum_{i=1}^n\log P_{\theta}(X_i)$.
Each $X_i$ is itself a vector with $p$ dimensions, each component taking values in $\{-1,1\}$. It is assumed that $\{X_1, ..., X_N\}$ are i.i.d. vectors with mass function $P_{\theta}(x)=Pr[X_1=x]$.  The $P_{\theta'}(x)$ function can be viewed as some other mass function that is not the mass function for the $X_i$ vectors.  Using the above definition of $V$ we get: 
\begin{eqnarray*}
e^{sV} &=& e^{\frac{s}{n}\sum_{i=1}^n\log P_{\theta'}(X_i)}e^{\frac{-s}{n}\sum_{i=1}^n\log P_{\theta}(X_i)}\\
&=& \prod_{i=1}^nP_{\theta'}(X_i)^{s/n}\prod_{i=1}^nP_{\theta}(X_i)^{-s/n} \\
&=& \prod_{i=1}^n P_{\theta'}(X_i)^{s/n}P_{\theta}(X_i)^{-s/n}
\end{eqnarray*}
Taking expectations and using independence gives: 
\begin{eqnarray*}
E[e^{sV}] &=& \prod_{i=1}^nE[P_{\theta'}(X_i)^{s/n}P_{\theta}(X_i)^{-s/n}] \\
&=& \prod_{i=1}^n\sum_{x\in\{-1,1\}^p} P_{\theta}(x)P_{\theta'}(x)^{s/n}P_{\theta}(x)^{-s/n} \\
&=& \prod_{i=1}^n\sum_{x\in\{-1,1\}^p} P_{\theta'}(x)^{s/n}P_{\theta}(x)^{1-s/n}\\
&=& \left( \sum_{x\in\{-1,1\}^p} P_{\theta'}(x)^{s/n}P_{\theta}(x)^{1-s/n}\right)^n
\end{eqnarray*}
Therefore:
\begin{eqnarray*}
\frac{1}{n}\inf_{s>0}\log E[e^{sV}] &=& \inf_{s>0}\log \left( \sum_{x\in\{-1,1\}^p}P_{\theta'}(x)^{s/n}P_{\theta}(x)^{1-s/n}\right) \\
&=& \inf_{r>0}\log \left( \sum_{x\in\{-1,1\}^p}P_{\theta'}(x)^{r}P_{\theta}(x)^{1-r}\right) 
\end{eqnarray*}
where the last step made the substitution $r=s/n$ (with the understanding that taking the infimum over $s/n$ is the same as taking the infimum over $s$).  If you like, you can change the variable $r$ back to the variable $s$, which is what they did.

I believe that explains (and corrects) that particular line in their proof.  However, I have no idea how they get the next line: 
$\leq \log Z(\theta/2+\theta'/2) - (1/2)\log Z(\theta) - (1/2)\log Z(\theta')$. 
I would have to look more carefully at the definition of the $Z(\theta)$ function to understand this. 
