# Are typical sets larger, when information is messier?

Let $0\le q<p\le \frac{1}{2}$, and let $P,Q$ be two Bernoulli Random Variables such that: $$Pr[P=1]=p ; Pr[P=0]=1-p$$ and $$Pr[Q=1]=q ; Pr[Q=0]=1-q$$ My question: Does it follow that, for any $\epsilon>0$ and $n$ as large as desired $|A_\epsilon^{(n)}(Q)|<|A_\epsilon^{(n)}(P)|$? I.e., that the Typical Set of $P$ is larger than that of $Q$?

Intuitively, I would say yes because of $q<p\le \frac{1}{2} \Rightarrow H(q)<H(p)$, and that the "messier" the information (i.e., the higher the entropy), the more elements in the Typical Set, but I've been unable to prove this.

What I've tried:

• Working with typical sets size bounds, namely that: $(1-\epsilon)2^{n(H(q)-\epsilon)}\le|A_\epsilon^{(n)}(Q)|\le2^{n(H(q)+\epsilon)}$. I was able to prove that $2^{-n(H(p)-\epsilon)}<2^{-n(H(q)-\epsilon)}$ and $2^{-n(H(p)+\epsilon)}<2^{-n(H(q)+\epsilon)}$, but that seems like a dead end.
• Proving that $A_\epsilon^{(n)}(Q)\subsetneq A_\epsilon^{(n)}(P)$ but that's false.
• Finding an Injective Function: $f:A_\epsilon^{(n)}(Q)\rightarrow A_\epsilon^{(n)}(P)$ but couldn't find one.
• Interesting question! It may be better suited to Mathematics, though; if you don't get useful answers after a few days and want us to migrate your question there, please raise a flag! – Raphael Aug 31 '17 at 4:47

Recall that $$A_\epsilon^{(n)}(P) = \left\{ (x_1,\ldots,x_n) \in \{0,1\}^n : 2^{-n(h(p)+\epsilon)} \leq p^{\sum_{i=1}^n x_i} (1-p)^{\sum_{i=1}^n (1-x_i)} \leq 2^{-n(h(p)-\epsilon)} \right\}.$$ We can rephrase the condition as follows. First, it is equivalent to $$2^{-n(h(p)+\epsilon+\log(1-p))} \leq \left(\frac{p}{1-p}\right)^{\sum_{i=1}^n x_i} \leq 2^{-n(h(p)-\epsilon+\log(1-p))}.$$ Taking the logarithm, we obtain $$-n(h(p)+\epsilon+\log(1-p)) \leq \log_2 \frac{p}{1-p} \sum_{i=1}^n x_i \leq -n(h(p)-\epsilon+\log(1-p)).$$ This means that $$|A_\epsilon^{(n)}(P)| = 2^n \Pr\left[\frac{n(h(p)-\epsilon+\log(1-p))}{\log \frac{1-p}{p}} \leq \mathrm{Bin}(n,1/2) \leq \frac{n(h(p)+\epsilon+\log(1-p))}{\log \frac{1-p}{p}}\right]$$ In order to estimate the probability on the right, we need to use binomial tail bounds. The Chernoff bounds is a well-known upper bound, and there are almost matching lower bounds, see for example (1) and (3) in Pelekis, A lower bound on binomial tails: an approach via tail conditional expectations. Plugging these bounds, we would get a rather accurate estimate for $|A_\epsilon^{(n)}(P)|$, which we could then compare with $|A_\epsilon^{(n)}(Q)|$, estimated using the same method.
As mentioned in the question, it can be shown that: $$(1-\epsilon)2^{n(H(q)-\epsilon)}\le|A_\epsilon^{(n)}(Q)|\le2^{n(H(q)+\epsilon)}$$ And similiarly: $$(1-\epsilon)2^{n(H(p)-\epsilon)}\le|A_\epsilon^{(n)}(P)|\le2^{n(H(p)+\epsilon)}$$ So in order to prove what we wanted, it's enough to find some $\epsilon_0>0$ and $n_0$ such that for all $\epsilon<\epsilon_0, n>n_0$: $$2^{n(H(q)+\epsilon)}<(1-\epsilon)2^{n(H(p)-\epsilon)}$$ Let $d:=H(P)-H(Q)>0$, $\epsilon_0:=\frac{d}{2}$.
Claim: The above holds for all $0<\epsilon<\epsilon_0$ and $n$ large enough such that $n>\frac{log(1-\epsilon)}{2\epsilon-d}$. Proof: $$2^{n(H(q)+\epsilon)}<(1-\epsilon)2^{n(H(p)-\epsilon)}\iff$$ $$log(\frac{2^{n(H(q)+\epsilon)}}{(1-\epsilon)})<log(2^{n(H(p)-\epsilon)})\iff$$ $$nH(q)+n\epsilon-log(1-\epsilon)<nH(p)-n\epsilon\iff$$ $$2n\epsilon-nd<log(1-\epsilon)\iff$$ $$n>\frac{log(1-\epsilon)}{2\epsilon-d}$$ Because the last inequation holds (by definition), so does the first, and that is Q.E.D.