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$.

  • $\begingroup$ What is the source for this exercise? $\endgroup$ – 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)$.


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.