# Sum of identically distributed but not independent Bernoulli's is non-uniform

Let $$X_1,X_2,\dots$$ denote a sequence of identically distributed, exchangeable, but not independent, Bernoulli$$(p)$$ random variables. If there exists $$n>0$$ such that

$$\sum_{i=1}^{n}X_i$$

is not uniformly distributed on $$\{0,1,\dots,n\}$$, how can we show that this implies

$$\sum_{i=1}^{n}X_i + X_{n+1}$$

is not uniformly distributed on $$\{0,1,\dots,n+1\}$$? If $$p \ne 1/2$$ then the claim follows by expectations, so we can consider $$p=1/2$$.

• What is the source for this exercise? – Did Sep 28 '18 at 18:00

First, some notations: for every $$n$$, let $$X_{1:n}=(X_1,X_2,\ldots,X_n)$$, and, for every word $$w=(w_1,w_2,\ldots,w_n)$$ in $$\{0,1\}^n$$, let $$|w|=w_1+w_2+\cdots+w_n$$. Now, to the proof, which uses crucially the exchangeability hypothesis.

Assume that, for some $$n\geqslant1$$, $$|X_{1:n+1}|$$ is uniformly distributed on $$\{0,1,\ldots,n+1\}$$.

Then, by exchangeability, for every word $$w$$ in $$\{0,1\}^{n+1}$$, $$P(X_{1:n+1}=w)$$ depends only on $$|w|$$. For each $$k$$ in $$\{0,1,\ldots,n+1\}$$, there are $${n+1\choose k}$$ words $$w$$ in $$\{0,1\}^{n+1}$$ such that $$|w|=k$$, hence, for every word $$w$$ in $$\{0,1\}^{n+1}$$ such that $$|w|=k$$, $$P(X_{1:n+1}=w)={n+1\choose k}^{-1}P(|X_{1:n+1}|=k)=(n+2)^{-1}{n+1\choose k}^{-1}$$ For every word $$v$$ in $$\{0,1\}^n$$, the event $$[X_{1:n}=v]$$ is the disjoint union of the events $$[X_{1:n}=v,X_{n+1}=0]$$ and $$[X_{1:n}=v,X_{n+1}=1]$$. If $$|v|=k$$ for some $$k$$ in $$\{0,1,\ldots,n\}$$, then $$|v0|=k$$ and $$|v1|=k+1$$, hence $$P(X_{1:n}=v)=(n+2)^{-1}{n+1\choose k}^{-1}+(n+2)^{-1}{n+1\choose k+1}^{-1}$$ Now, it happens that $$(n+2)^{-1}{n+1\choose k}^{-1}+(n+2)^{-1}{n+1\choose k+1}^{-1}=(n+1)^{-1}{n\choose k}^{-1}\tag{\ast}$$ hence $$P(X_{1:n}=v)=(n+1)^{-1}{n\choose k}^{-1}$$ Summing these over the $${n\choose k}$$ words $$v$$ in $$\{0,1\}^n$$ such that $$|v|=k$$, one gets, for every $$k$$ in $$\{0,1,\ldots,n\}$$, $$P(|X_{1:n}|=k)=(n+1)^{-1}$$ Thus, if $$|X_{1:n+1}|=X_1+X_2+\cdots+X_{n+1}$$ is uniformly distributed on $$\{0,1,\ldots,n+1\}$$, then $$|X_{1:n}|=X_1+X_2+\cdots+X_n$$ is uniformly distributed on $$\{0,1,\ldots,n\}$$.

By contraposition, this proves the desired statement -- and also that, as soon as $$|X_{1:n}|=X_1+X_2+\cdots+X_{n}$$ is uniformly distributed on $$\{0,1,\ldots,n\}$$ for some $$n\geqslant1$$, then $$|X_{1:1}|=X_1$$ is uniformly distributed on $$\{0,1\}$$, and, again by exchangeability, every $$X_n$$ is uniformly distributed on $$\{0,1\}$$, that is, necessarily, $$p=\frac12$$.

Exercise: Prove $$(\ast)$$.

Here is a large hint/outline.

A good method is to prove the contrapositive. Letting $$S_{n}=\sum_{i=1}^n X_i$$, assume that $$S_{n+1}$$ is uniformly distributed over $$\{0,1,\dots,n+1\}$$, and prove that $$S_n$$ is uniform as well.

To prove this, use the decomposition $$P(S_n=k) = P(S_n=k\cap X_{n+1}=0)+P(S_n=k\cap X_{n+1}=1)\tag{*}$$ We need to somehow relate the events on the RHS to events of the form $$\{S_{n+1}=h\}$$, whose probabilities are known to be $$\frac1{n+2}$$.

If we consider our sample space to be the set of sequences of $$n+1$$ zeroes and ones, then $$\{S_n=k\}\cap \{X_{n+1}=0\}$$ consists of all $$\binom{n}k$$ sequences ending in a $$0$$ and consisting of $$k$$ ones. By exchangeability, these events are all equally likely. In particular, letting $$E$$ be the event that $$X_i=1$$ for $$i=1,2,\dots,k$$ and $$X_i=0$$ for $$i=k+1,k+2,\dots,n+1$$ (the string $$11\dots100\dots0$$), then $$P(S_n=k\cap X_{n+1}=0) = \binom{n}k\cdot P(E)$$ On the other hand, $$E$$ is a subset of the event $$\{S_{n+1}=k\}$$, which consists of $$\binom{n+1}{k}$$ equally likely sequences, so we also have $$\frac1{n+2}=P(S_{n+1}=k)=\binom{n+1}k\cdot P(E)$$ The last two equations allow you to eliminate $$P(S_n=k\cap X_{n+1}=0)$$ in $$(*)$$. You can do something similar to eliminate $$P(S_n=k\cap X_{n+1}=1)$$.