Communication, Networking, Signal and Image Processing (CS)

Question 1: Probability and Random Processes

August 2013

# Part 1

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

Good solution with appropriate explanation.

## 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(1-p)$

Critique on Solution 2:

The solution is correct. However, it's better to explicitly express $k_i$ as a Bernoulli random variable. This makes it easier for readers to understand.

## Solution 3

First, we define a Bernoulli random variable

$X = \left\{ \begin{array}{ll} 0, & the change over does not occur\\ 1, & the change over occurs \end{array} \right.$

Then we can compute

$P(X = 1) = P(1-P)+(1-P)P = P-{P}^{2}+P-{P}^2=2P-2{P}^{2}$

$P(X = 0) = P•P+(1-P)(1-P) = {P}^{2}+1-2P+{P}^2$

Define Y as the number of changes occurred in n flips, there exists at most n-1 changes

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

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

Therefore, we have a final solution as

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

## Similar Question

Bits are sent over a communications channel in packets of 12. If the probability of a bit being corrupted over this channel is 0.1 and such errors are independent, what is the probability that no more than 2 bits in a packet are corrupted? If 6 packets are sent over the channel, what is the probability that at least one packet will contain 3 or more corrupted bits?

## Alumni Liaison

Basic linear algebra uncovers and clarifies very important geometry and algebra.

Dr. Paul Garrett