ECE Ph.D. Qualifying Exam

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

Comments on Solution 1:

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?


Back to QE CS question 1, August 2013

Back to ECE Qualifying Exams (QE) page

Alumni Liaison

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

Dr. Paul Garrett