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

Sale!