Description

Department of Electrical Engineering and Computer Sciences
EECS 126: Probability and Random Processes
Problem Set 5
1. Midterm
Solve all of the problems on the midterm again (including the ones you got correct).
2. Convergence in Probability
Let ( , be a sequence of i.i.d. random variables distributed uniformly in [−1,1]. Show that the following sequences ( converge in probability to some limit.
(a) Yn = Qni=1 Xi.
(b) Yn = max{X1,X2,…,Xn}.
(c) Yn = (X12 + ··· + Xn2)/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

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