Part 2

Consider $ n $ independent flips of a coin having probability $ p $ of landing on heads. Say that a changeover occurs whenever an outcome differs from the one preceding it. For instance, if $ n=5 $ and the sequence $ HHTHT $ is observed, then there are 3 changeovers. Find the expected number of changeovers for $ n $ flips. Hint: Express the number of changeovers as a sum of Bernoulli random variables.

Solution 1

The number of changeovers $ Y $ can be expressed as the sum of n-1 Bernoulli random variables:

$ Y=\sum_{i=1}^{n-1}X_i $.

Therefore,

$ E(Y)=E(\sum_{i=1}^{n-1}X_i)=\sum_{i=1}^{n-1}E(X_i) $.

For Bernoulli random variables,

$ E(X_i)=p(E_i=1)=p(1-p)+(1-p)p=2p(1-p) $.

Thus

$ E(Y)=2(n-1)p(1-p) $.

Solution 2

For $ n $ flips, there are $ n-1 $ changeovers at most. Assume random variable $ k_i $ for changeover,

$ p({k_i}=1)=p(1-p)+(1-p)p=2p(1-p) $

$ E(k)=\sum_{i_1}^{n-1}p(k_i=1)=2(n-1)p(p-1) $

Critique on Solution 2:

It might be better to claim the changeover as a Bernoulli random variable so the logic is easier to understand.

Back to QE CS question 1, August 2013

Back to ECE Qualifying Exams (QE) page