EEC 126 Discussion 4 Solutions

EE126 Discussion 4: Solutions
Jerome Thai
February 20, 2014
Continuous random variables
Problem 1. Let X be uniformly distributed in [0, 1]. Assume that, given X = x, the random
variable Y is exponentially distributed with rate x + 1.
(a) Calculate E[Y ].
(b) Find MLE[X|Y = n].
(c) Find MAP[X|Y = n].
Solution. (a) We first note that E[Y ] = E[E[Y |X]]. Computing E[Y |X]:
E[Y |X = x] = E[exp(x + 1)] = 1/(x + 1)
R1
From above, E[Y ] = E[E[Y |X = x]] = E[(1 + x)1 ] = x=0 (1 + x)1 = [ln(1 + x)]10 = ln 2
(b, c) As X is uniformly distributed the MAP and MLE are equivalent. This means we just need
to compute the MLE, i.e. the X that maximizes the likelihood of Y = y:
MLE[X|Y = n] = arg max f (Y = y | X = x)
x
= arg max (1 + x)e(1+x)y

x
We can find this by calculating derivatives and setting it equal to zero:

+ x)e(x+1)y = y(1 + x)e(x+1)y + e(x+1)y
= e(x+1)y ((x + 1)y + 1) = 0
= x = y1 1
d
dx (1
Recognizing that x is also limited to be in the range of
1
MAP[X | Y = y] = y1 1
[0, 1]. Thus:

if y 0.5
if 0.5 y 1
otherwise
Problem 2. Let X, Y be two independent Exp(1) random variables. Calculate E[X | X > y] (two
different ways).
Solution. We can note that by the memoryless property of the exponential distribution, given
{X > Y = y}, X Y is exponentially distributed with rate 1. Thus,
E[X | X > y] = y + 1
We can find this result by direct calculation. Using Bayes rule:
P (X [x, x + dx] and X > y) = P (X [x, x + dx] | X > y)P (X > y)
1
hence
Z
xP (X [x, x + dx] | X > y)P (X > y)
xP (X [x, x + dx] and X > y) =

x0
x0
The term on the left-hand side inside the integral is equal to 0 for x < y:
Z
Z
xP (X [x, x + dx] | X > y)
xP (X [x, x + dx] and X > y) = P (X > y)
x0
xy
in other words
Z
xex dx = E[X | X > y]P (X > y)
hence:
R +
y
E[X | X > y] =
with
Z
xe
dx =
[xex ]+
y
xex dx
P (X > y)
Z
+
R +
=
xex dx
ey
ex dx = yey + [ex ]+
= ey (1 + y)
y
hence
E[X | X > y] = y + 1
Markov chains
Problem 3. a) Give an example of a Markov chain Xn on {0, 1, 2, 3} and a function of the Markov
chain that is not a Markov chain.
b) Give an example of a Markov chain Xn on {0, 1, 2, 3} and a function of that Markov chain that
is not constant and not identical to Xn and that is a Markov chain.
Solution. a) Let Xn be cyclic on {0, 1, 2, 3}, i.e., moving from 0 to 1 to 2 to 3 to 0, etc, with
probability 1. Assume that X0 is uniform on {0, 1, 2, 3}. Let f (0) = 0, f (1) = 1, f (2) = f (3) = 2.
Then f (Xn ) is not a Markov chain. Indeed,
P [f (X2 ) = 2 | f (X1 ) = 2, f (X0 ) = 2] = 0
whereas
P [f (X2 ) = 2 | f (X1 ) = 2] > 0
b) Any one-to-one function will do. For a non-trivial example where the function is many-toone, we use symmetry. Let Xn be the MC with the state transition diagram shown below. Then
f (Xn ) with f (0) = 0, f (1) = 1, f (2) = 1, f (3) = 0 is a MC. The main idea is that the future
of f (Xn ) looks the same whether Xn = 0 or Xn = 3 and also whether Xn = 1 or Xn = 2, by
symmetry.
Problem 4. You roll a die until the sum of the last two rolls yields 9. What is the average number
of rolls?
Figure 1: MC for problem 3.

Solution. We can follow the same approach as done in class. For the sum of the last two rolls to
be 9, both rolls must be greater than or equal to 3. Lets define the following two definitions:
1) Let be the average remaining number of rolls given you have just rolled 1 or 2.
2) Let be the average remaining number of rolls given you have just rolled 3-6.
Once we reach there is 1/6 probability of having the sum equal 9.
= (1/3)( + 1) + (2/3)( + 1)
= 1/6 1 + (1/3)( + 1) + (1/2)( + 1)
Solving this gives = 10.5, = 9. This it takes on average 10.5 rolls for the sum to equal 9.
Problem 5. Consider the numbers 1, 2, , 12 written around a ring as they usually are on a
clock. Consider the Markov chain with state space {1, 2, , 12} that at any time jumps with
equal probability to one of the two adjacent numbers. What is the expected number of steps that
the Markov chain will take to return to its original position?
Solution. Let {Xn , n 0} denote the Markov chain of interest. By symmetry, we may assume
without loss of generality that we start in state 1. Let h(x) := E[T1 | X0 = x], where
T1 := inf{n 1 : Xn = 1}
By symmetry we must have h(x) = h(14 x) for all x {1, 2, , 12}. Thus it suffices to write
the following first step equations (whose validity can be seen from the Markov property):
h(1)
h(2)
h(3)
h(4)
h(5)
h(6)
h(7)
= 1 + h(2)/2 + h(12)/2 = 1 + h(2)

= 1 + 1/2 0 + h(3)/2 = 1 + h(3)/2
= 1 + h(2)/2 + h(4)/2
= 1 + h(3)/2 + h(5)/2
= 1 + h(4)/2 + h(6)/2
= 1 + h(5)/2 + h(7)/2
= 1 + h(6)/2 + h(8)/2 = 1 + h(6)
Note that we have substituted h(12) by h(2) and h(8) by h(6), so these equations only involve the
variables h(1), h(2), , h(7). We can rewrite the last six equations as
h(2)
h(3) h(2)
h(4) h(3)
h(5) h(4)
h(6) h(5)
h(7) h(6)
= 2 + h(3) h(2)
= 2 + h(4) h(3)
= 2 + h(5) h(4)
= 2 + h(6) h(5)
= 2 + h(7) h(6)
=1
3
This form is set up for easy successive substitution starting from the bottom equation and working
upwards, which allows us to conclude that h(2) = 11. Substituting this in the first of these equations
gives h(1) = 12.
Confidence intervals
Note 1. Let X be a random variable with finite expected value and finite non-zero variance 2 .
Then for any real number a > 0,
P (|X | > a) 2 /a2
Problem 6. In order to estimate the probability of head in a coin flip, p, you flip a coin n times,
and count the number of heads, Sn . You use the estimator p = Sn /n. You choose the sample size
n to have a guarantee
P (|Sn/n p| )
Determine how the value of n suggested by Chebyshev inequality changes when is reduced to half
of its original value? How does it change when is reduced to its original value?
Solution. The random variable Sn /n has mean p and variance np(1 p)/n2 = p(1 p)/n, hence,
P (|Sn/n p| )
p(1 p)
n2
by Chebyshev inequality. Hence we want:

=
p(1 p)
n2
or n =
p(1 p)
2
When is reduced to half of its original value, we need four times more flips to have the same
guarantee, and when is reduced to half of its original value, we need two times more flips.

EEC 126 Discussion 4 Solutions

Uploaded by

Copyright:

Available Formats

EEC 126 Discussion 4 Solutions

Uploaded by

Document Information

Original Description:

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

EEC 126 Discussion 4 Solutions

Uploaded by

Copyright:

Available Formats

EE126 Discussion 4: Solutions

Continuous random variables

= arg max (1 + x)e(1+x)y

We can find this by calculating derivatives and setting it equal to zero:

Recognizing that x is also limited to be in the range of

[0, 1]. Thus:

xP (X [x, x + dx] | X > y)P (X > y)

xP (X [x, x + dx] and X > y) =

xex dx = E[X | X > y]P (X > y)

Figure 1: MC for problem 3.

= 1 + h(2)/2 + h(12)/2 = 1 + h(2)

by Chebyshev inequality. Hence we want:

You might also like