I am trying to understand the proof of Lemma 1 in [this paper (Section 9.2)](https://arxiv.org/pdf/1809.03113.pdf).


The proof shows that given a discrete probability distribution $P=(p\_1,p\_2,...,p\_k)$ where $p\_1 \geq p\_2 \geq ... \geq p\_k$, and a discrete probability distribution $Q=(q\_0,q\_0,q\_3,q\_4...,q\_k)$ where $q\_0 = q\_0 \geq q\_3 \geq q\_4 \geq ... \geq q\_k$. Then for a fixed $P$, and a fixed $\alpha>1$, the minimizer of:


$$\min\_{q\_0,q\_3,...,q\_k} p\_1(\frac{q\_0}{p\_1})^\alpha + p\_2(\frac{q\_0}{p\_2})^\alpha + \sum\_{i=3}^{k}p\_i(\frac{q\_i}{p\_i})^\alpha$$


$$\text{such that:}\\ 2q\_0 + q\_3 + ... + q\_k = 1\\q\_i-q\_0\leq 0 \quad i\geq 3\\-q\_i\leq 0$$


Is given by $q\_0 = (\frac{p\_1^{1-\alpha}+p\_2^{1-\alpha}}{2})^\frac{1}{1-\alpha}$ and $q\_i = \frac{1-2q\_0}{1-p\_1-p\_2}p\_i$ for $i\geq 3$. I think I understand how these are found, however they then claim that plugging these quantities into the Renyi divergence formula:


$$D\_\alpha := \frac{1}{1-\alpha}\log\bigg[p\_1(\frac{q\_0}{p\_1})^\alpha + p\_2(\frac{q\_0}{p\_2})^\alpha + \sum\_{i=3}^{k}p\_i(\frac{q\_i}{p\_i})^\alpha\bigg]$$


gives:


$$-\log\bigg[1-p\_1-p\_2 + 2(\frac{p\_1^{1-\alpha} + p\_2^{1-\alpha}}{2})^\frac{1}{1-\alpha}\bigg]\quad\quad\quad[\*]$$


Perhaps I have misunderstood but I do not understand how $[\*]$ is found. When I plug $q\_0$ and $q\_i$ into the Renyi divergence formula, I get:


\begin{equation\*}
\begin{split}
D\_\alpha &= \frac{1}{1-\alpha}\log\bigg[(p\_1^{1-\alpha} + p\_2^{1-\alpha})q\_0^\alpha + \sum\_{i=3}^{k}p\_i(\frac{q\_i}{p\_i})^\alpha\bigg]\\
&= \frac{1}{1-\alpha}\log\bigg[(p\_1^{1-\alpha} + p\_2^{1-\alpha})(\frac{p\_1^{1-\alpha} + p\_2^{1-\alpha}}{2})^\frac{\alpha}{1-\alpha} + \sum\_{i=3}^{k}p\_i(\frac{q\_i}{p\_i})^\alpha\bigg]\\
&= \frac{1}{1-\alpha}\log\bigg[2(\frac{p\_1^{1-\alpha} + p\_2^{1-\alpha}}{2})^\frac{1}{1-\alpha} + \sum\_{i=3}^{k}p\_i(\frac{q\_i}{p\_i})^\alpha\bigg]\\
&= \frac{1}{1-\alpha}\log\bigg[2(\frac{p\_1^{1-\alpha} + p\_2^{1-\alpha}}{2})^\frac{1}{1-\alpha} + \sum\_{i=3}^{k}p\_i(\frac{1-2q\_0}{1-p\_1-p\_2})^\alpha\bigg]\\
&= \frac{1}{1-\alpha}\log\bigg[2(\frac{p\_1^{1-\alpha} + p\_2^{1-\alpha}}{2})^\frac{1}{1-\alpha} + (1-p\_1-p\_2)^{1-\alpha}(1-2q\_0)^\alpha\bigg]\\
&= \frac{1}{1-\alpha}\log\bigg[2(\frac{p\_1^{1-\alpha} + p\_2^{1-\alpha}}{2})^\frac{1}{1-\alpha} + (1-p\_1-p\_2)^{1-\alpha}(1-2(\frac{p\_1^{1-\alpha}+p\_2^{1-\alpha}}{2})^\frac{1}{1-\alpha})^\alpha\bigg]\quad\quad [!]
\end{split}
\end{equation\*}


How do I get from this to $[\*]$ or is there an obvious mistake I am making?


=====


Edit: Looking again at the KKT conditions, I'm not sure now how they arrive at $q\_0 = (\frac{p\_1^{1-\alpha}+p\_2^{1-\alpha}}{2})^\frac{1}{1-\alpha}$ and $q\_i = \frac{1-2q\_0}{1-p\_1-p\_2}p\_i$ for $i\geq 3$.


Let $Q = (q\_0, q\_0, q\_3)$


Then the Lagrangian is 
\begin{equation\*}
\begin{split}
L = p\_1(\frac{q\_0}{p\_1})^\alpha + p\_2(\frac{q\_0}{p\_2})^\alpha + p\_3(\frac{q\_3}{p\_3})^\alpha + \mu\_1(q\_3-q\_0) - \mu\_2q\_0 - \mu\_3q\_3 + \lambda(2q\_0 + q\_3 - 1)
\end{split}
\end{equation\*}


Differentiating and setting the slack variables to 0, gives:
\begin{equation\*}
\begin{split}
& \lambda = -\alpha(\frac{q\_3}{p\_3})^{\alpha - 1}\\
& 2\lambda = -\alpha(\frac{q\_0}{p\_1})^{\alpha - 1} - \alpha(\frac{q\_0}{p\_2})^{\alpha - 1}
\end{split}
\end{equation\*}


Then $q\_0 = (\frac{p\_1^{1-\alpha}+p\_2^{1-\alpha}}{2})^\frac{1}{1-\alpha}
\iff q\_3 = p\_3$. However, I don't understand why $q\_3$ must equal $p\_3$.



Lower bound Renyi divergence between two discrete probability distributions
The author is here.
We did make a mistake in the formula. $q^\*=\left(\frac{p\_1^{1-\alpha}+p\_2^{1-\alpha}}{2}\right)^{\frac{1}{1-\alpha}}$ is not the minimizer for $q\_0$. It should be $\frac{q^\*}{1-p\_1-p\_2+2q^\*}$. The corresponding minimizer for $q\_i$ should be $\frac{p\_i}{1-p\_1-p\_2+2q^\*}$.


I was misled by my code when I wrote the paper. In my code, I obtain the value of $Q$ by replacing $p\_1$ and $p\_2$ with $q\_0$ and renormalize the whole thing. I forgot to reflect the renormalization in the formula.


The correct minimizers should give you the bound we proposed. We apologize for this mistake and will revise our paper. Thank you for pointing it out.


I hope this will also answer why the solver for the KKT conditions seems incorrect. I cannot recall exactly how it was derived, but I remember the key is to realize $q^\*/p\_i$ is the ratio between $q\_0$ and $p\_i$ for $i\geq 3$.


