# Independence of coin tosses (Exercise 1.5.3 from Probability and Random Processes by Grimmett and Stirzaker)

A fair coin is tossed repeatedly. Show that the following two statements are equivalent:

(a) the outcomes of the different tosses are independent, (b) for any given finite sequence of heads and tails, the chance of this sequence occurring in the first $m$ tosses is $2^{-m}$ where $m$ is the length of the sequence.

Here is my attempt at a proof:

$\mathrm{(a)} \implies \mathrm{(b)}$:

Assume (a). Suppose that we are given a finite sequence of heads and tails of length $m$. Let $A_k$ be the event that the $k^{\rm th}$ toss of the coin agrees with the $k^{\rm th}$ position in the sequence. Then the probability that the first $m$ tosses agree with the given sequence is $P(A_1 \cap A_2 \cap \ldots \cap A_m)$. Since the individual tosses are independent of each other $P(A_1 \cap A_2 \cap \ldots \cap A_m) = P(A_1) P(A_2) \ldots P(A_m)$ and since the coin is fair $P(A_k) = 2^{-1}$. Hence $P(A_1 \cap A_2 \cap \ldots \cap A_m) = 2^{-m}$. Since the given sequence was arbitrary, (a) $\implies$ (b).

$\mathrm{(b)} \implies \mathrm{(a)}$:

Assume (b). Suppose that we are given a finite sequence of heads and tails of length $m$. Let $A_k$ be the event that the $k^{\rm th}$ toss of the coin agrees with the given sequence at the $k^{\rm th}$ position. Then because there are $2^{m - 1}$ possible sequences of tosses in which the $k^{\rm th}$ position agrees with the given sequence and each of them has a probability of $2^{-m}$ of occurring, the probability of $A_k$ occurring is $P(A_k) = 2^{m - 1} 2^{-m} = 2^{-1}$. But $P(A_1 \cap A_2 \cap \ldots \cap A_m) = 2^{-m} = (2^{-1})^{m} = P(A_1) P(A_2) \ldots P(A_m)$. Thus the events $A_k$ are independent of each other and since the given sequence was arbitrary, (b) $\implies$ (a).

Is it correct? I am not sure if the second part is correct.

• I think the second part is incorrect because I haven't shown that $P(A_i \cap A_j) = P(A_i) P(A_j), P(A_i \cap A_j \cap A_k) = P(A_i) P(A_j) P(A_k)$, etc. – Raj Feb 12 '15 at 19:42

Your proof of (a)$\Rightarrow$(b) is fine.
In order to prove (b)$\Rightarrow$(a) we have to assume (b) and then have to prove the following:
Given any finite subset $J\subset{\Bbb N}_{\geq1}$ and any function $$\beta:\quad J\to{\Bbb B}:=\{0,1\},\qquad k\mapsto \beta_k$$ one has $$P\bigl[X_k=\beta_k \ (k\in J)\bigr]={1\over 2^{|J|}}\ .$$ Proof. Let $N:=\max J$. On account of (b) all $2^N$ possible outcomes in the first $N$ tosses have the same probability ${1\over 2^N}$. Exactly $2^{N-|J|}$ of these outcomes satisfy $$X_k=\beta_k\quad(k\in J)\ .$$ It follows that $$P\bigl[X_k=\beta_k \ (k\in J)\bigr]=2^{N-|J|}\cdot{1\over 2^N}={1\over 2^{|J|}}\ ,$$ as stated.