Problem Set 5 Convergence in Probability

EECS 126: Probability and Random Processes
Problem Set 5
Fall 2021
1. Midterm
Solve all of the problems on the midterm again (including the ones you got correct).
2. Convergence in Probability
Let (Xn)∞
n=1, be a sequence of i.i.d. random variables distributed uniformly in [−1, 1]. Show
that the following sequences (Yn)∞
n=1 converge in probability to some limit.
(a) Yn =
Qn
i=1 Xi
.
(b) Yn = max{X1, X2, . . . , Xn}.
(c) Yn = (X2
1 + · · · + X2
n
)/n.
3. Gambling Game
Let’s play a game. You stake a positive initial amount of money w0. You toss a fair coin. If it
is heads you earn an amount equal to three times your stake, so you quadruple your wealth.
If it comes up tails you lose everything. There is one requirement though, you are not allowed
to quit and have to keep playing, by staking all your available wealth, over and over again.
Let Wn be a random variable which is equal to your wealth after n plays.
(a) Find E[Wn] and show that limn→∞ E[Wn] = ∞.
(b) Since limn→∞ E[Wn] = ∞, this game sounds like a good deal! But wait a moment!!
Where does the sequence of random variables {Wn}n≥0 converge almost surely (i.e. with
probability 1) to?
4. Twitch Plays Pokemon
You wake up one day and are surprised to see that it is 2014, when the world was peaceful.
You immediately start playing Twitch Plays Pokemon. Suddenly, you realized that you may
be able to analyze Twitch Plays Pokemon.
You
Stairs
Figure 1: Part (a)
(a) The player in the top left corner performs a random walk on the 8 checkered squares and
the square containing the stairs. At every step the player is equally likely to move to
any of the squares in the four cardinal directions (North, West, East, South) if there is a
square in that direction. Find the expected number of moves until the player reaches the
stairs in Figure 1.
1
[Hint: Use symmetry to reduce the number of states in your Markov chain]
You
Stairs Stairs
Figure 2: Part (b)
(b) The player randomly walks in the same way as in the previous part. Find the probability
that the player reaches the stairs in the bottom right corner in Figure 2.
[Hint: For each squared box, assign a variable that denotes the probability of reaching
the “good” stairs. Use symmetry again to reduce the number of such variables.]
Hint: For both problems use symmetry to reduce the number of states and variables. The
equations are very reasonable to solve by hand.
5. Discrete Uniform Records
Consider a Markov chain (Xn, Yn) that moves on N
2
0
(where by N0 we mean N∪ {0}) as follows.
From (i, j) the chains moves to either (i + 1, j) or (i, k) for some 0 ≤ k < j, with each of these
j + 1 possibilities chosen uniformly at random. Let T = min{n ≥ 0 : Yn = 0} be the first time
the chain hits the x-axis.
(a) Find a recurrence for E[T] for any initial position (X0, Y0) = (i, j).
(b) Find the distribution of XT for any initial position (i, j). Hint: Develop first step equations
for the moment generating function MXT
(s) = Ei,j [e
sXT ]. Later we will learn about
characteristic functions ϕX(t) = E[e
itX], which are essentially the Fourier transforms of
our random variables (whereas the m.g.f. is the Laplace transform). The m.g.f. and
characteristic functions both have the property of carrying complete information about
the distribution of a random variable. For the purposes of this class, we may think of
these two transforms as equivalent.
6. Noisy Guessing
Let X, Y , and Z be i.i.d. with the standard Gaussian distribution. Find E[X | X + Y, X +
Z, Y − Z].
Hint: Argue that the observation Y − Z is redundant.
2