# Lower Bound of Divergence

I want to prove that a lower bound of the Divergence between two probability distributions $$p$$ and $$q$$ defined on the set $$\mathcal{U}$$ can be expressed by defining a subset $$\mathcal{S}\subset\mathcal{U}$$ with the following expression:

$$$$D(p||q)\geq d_2(p(\mathcal{S})||q(\mathcal{S}))\text,$$$$

where $$p(\mathcal{S})=\sum_{u\in \mathcal{S}}p(u)$$, similarly for $$q(\mathcal{S})$$, and $$d_2(\alpha||\beta)=\alpha\log \frac{\alpha}{\beta}+(1-\alpha)\log \frac{1-\alpha}{1-\beta}$$

I suppose that this could be proven with the data processing theorem for divergence but I don't know how to arrange terms to find the previous expression.

• If you started from $\mathcal{U}$ and you were looking for $\mathcal{S}$, you could probably use the data processing theorem. But what if $\mathcal{S}$ contained non-overlaping distributions? Are $p,q$ at least confined over the same range of output values? – A_A Oct 6 '18 at 10:59
• What are your restrictions on $\mathcal S$? What happens for $\mathcal S=\emptyset$? What for $S=\{\arg\min\limits_{s\in \mathcal U} p(s)\}$ – Marcus Müller Oct 6 '18 at 11:23

$$D(p||q)\geq D(\tilde{p}||\tilde{q})$$
with $$\tilde{p}(v)=\sum_{u}P(u)W(v|u)$$ is true for all valid probability kernels $$W(v|u) (\sum_v W(v|u)=1 \forall u \in \mathcal{U},, W(u,v) \geq 0 \forall u,v)$$, we could define a kernel in such a way that $$\tilde{p}$$ and $$\tilde{q}$$ are Bernoulli distributions: $$$$W(v|u)={0 if u \in \mathcal{S}, v=0 or u \notin \mathcal{S} ; 1 if u \notin \mathcal{S}, v=0 or u \in \mathcal{S}}$$$$
Now $$D(\tilde{p}||\tilde{q})=\sum_v\tilde{P}\log\frac{tilde{P}}{tilde{Q}}=p(\mathcal{S})\log\frac{p(\mathcal{S})}{q(\mathcal{S})}+(1-p(\mathcal{S}))\log\frac{1-p(\mathcal{S})}{1-q(\mathcal{S})}:= d_2(p(\mathcal{S})||q(\mathcal{S}))$$