0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Raj Feb 12 '15 at 19:42
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks for the answer! Is the first part correct? $\endgroup$ – Raj Feb 13 '15 at 16:19
  • $\begingroup$ Just saw your comment about the first part. Thanks again. $\endgroup$ – Raj Feb 13 '15 at 17:02

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.