3
$\begingroup$

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.
$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – Raphael Aug 31 '17 at 4:47
0
$\begingroup$

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.

Unfortunately, this calculational method seems like a lot of work, better done with the aid of a computer algebra system, and I am not motivated enough to actually carry it through. However, it seems likely (if not certain) that this method will be able to settle the conjecture.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.