Latest revision as of 16:28, 23 February 2017

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

@@ Line 29: / Line 29: @@
 The number of changeovers <math>Y</math> can be expressed as the sum of n-1 Bernoulli random variables:
-<math>Y=\sum_{i=1}^{n-1}X_i</math>
+<math>Y=\sum_{i=1}^{n-1}X_i</math>.
-<math class="inline">\Phi_{\mathbf{X}}\left(\omega\right)=E\left[e^{i\omega\mathbf{X}}\right]=\int_{-\infty}^{\infty}\frac{A}{2}e^{-A\left|x\right|}\cdot e^{i\omega x}dx=\frac{A}{2}\left[\int_{-\infty}^{0}e^{x\left(A+i\omega\right)}dx+\int_{0}^{\infty}e^{x\left(-A+i\omega\right)}dx\right]</math><math class="inline">=\frac{A}{2}\left[\frac{e^{x\left(A+i\omega\right)}}{A+i\omega}\biggl|_{-\infty}^{0}+\frac{e^{x\left(-A+i\omega\right)}}{-A+i\omega}\biggl|_{0}^{\infty}\right]=\frac{A}{2}\left[\frac{1}{A+i\omega}-\frac{1}{-A+i\omega}\right]</math><math class="inline">=\frac{A}{2}\cdot\frac{A-i\omega+A+i\omega}{A^{2}+\omega^{2}}=\frac{A^{2}}{A^{2}+\omega^{2}}.</math>
+Therefore,
-'''(b)'''
+<math>E(Y)=E(\sum_{i=1}^{n-1}X_i)=\sum_{i=1}^{n-1}E(X_i)</math>.
-<math class="inline">P\left(\left\{ \left|\mathbf{X}-\overline{\mathbf{X}}\right|\leq2\sigma\right\} \right)=1-P\left(\left\{ \left|\mathbf{X}-\overline{\mathbf{X}}\right|>2\sigma\right\} \right).</math>  By [[ECE 600 Chebyshev Inequality|Chebyshev Inequality]], <math class="inline">P\left(\left\{ \left|\mathbf{X}-\overline{\mathbf{X}}\right|>2\sigma\right\} \right)\leq\frac{\sigma^{2}}{\left(2\sigma\right)^{2}}=\frac{1}{4}</math> .
+For Bernoulli random variables,
-<math class="inline">P\left(\left\{ \left|\mathbf{X}-\overline{\mathbf{X}}\right|\leq2\sigma\right\} \right)\geq\frac{3}{4}.</math>
+<math>E(X_i)=p(E_i=1)=p(1-p)+(1-p)p=2p(1-p)</math>.
+Thus
+<math>E(Y)=2(n-1)p(1-p)</math>.
+<font color="red"><u>'''Comments on Solution 1:'''</u>
+Good solution with appropriate explanation.
+</font>
 ----
 ==Solution 2==
-Write it here.
+For n flips, there are n-1 changeovers at most. Assume random variable <math>k_i</math> for changeover,
+<math>P(k_i=1)=p(1-p)+(1-p)p=2p(1-p)</math>
+<math>E(k)=\sum_{i=1}^{n-1}P(k_i=1)=2(n-1)p(1-p)</math>
+<font color="red"><u>'''Critique on Solution 2:'''</u>
+The solution is correct. However, it's better to explicitly express <math>k_i</math> as a Bernoulli random variable. This makes it easier for readers to understand.
+</font>
+----
+==Solution 3==
+<p>
+First, we define a Bernoulli random variable
+</p>
+<p><span class="mwe-math-fallback-source-inline tex" dir="ltr">$ X = \left\{ \begin{array}{ll}  0, &amp; the&nbsp;change&nbsp;over&nbsp;does&nbsp;not&nbsp;occur\\  1, &amp; the&nbsp;change&nbsp;over&nbsp;occurs  \end{array} \right. $</span>
+</p><p>Then we can compute
+</p><p><span class="mwe-math-fallback-source-inline tex" dir="ltr">$P(X = 1) = P(1-P)+(1-P)P = P-{P}^{2}+P-{P}^2=2P-2{P}^{2} $</span>
+</p><p><span class="mwe-math-fallback-source-inline tex" dir="ltr">$P(X = 0) = P•P+(1-P)(1-P) = {P}^{2}+1-2P+{P}^2 $</span>
+</p><p>Define Y as the number of changes occurred in n flips, there exists at most n-1 changes
+</p><p><span class="mwe-math-fallback-source-inline tex" dir="ltr">$E(Y)=E(\sum_{i=1}^{n-1}X_i)=\sum_{i=1}^{n-1}E(X_i) $</span>
+</p><p><span class="mwe-math-fallback-source-inline tex" dir="ltr">$E(X_i)=p(X_i=1)=p(1-p)+(1-p)p=2p(1-p) $</span>
+</p><P>Therefore, we have a final solution as
+</p><p><span class="mwe-math-fallback-source-inline tex" dir="ltr">$ E(Y)=2(n-1)p(1-p) $</span>.
+</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?
 ----
-[[ECE_PhD_QE_CNSIP_2000_Problem1|Back to QE CS question 1, August 2000]]
+[[ECE-QE_CS1-2013|Back to QE CS question 1, August 2013]]
 [[ECE_PhD_Qualifying_Exams|Back to ECE Qualifying Exams (QE) page]]

Difference between revisions of "ECE PhD QE CNSIP 2013 Problem1.1" - Rhea

Latest revision as of 16:28, 23 February 2017

Contents

Part 1

Solution 1

Solution 2

Solution 3

Similar Question

Alumni Liaison