EECS 126: Probability and Random Processes

Problem Set 2

1. Among Us

In the game of Among Us, there are 9 players. 4 of them are imposters and 5 of them are

crewmates. There is also a deck of 17 cards containing 11 “sabotage” cards and 6 “task” cards.

Imposters want to play sabotage cards, and crewmates want to play task cards. Here’s how

the play proceeds.

• A captain and a first mate are chosen uniformly at random from the 9 players.

• The captain draws 3 cards from the deck and gives 2 to the first mate, discarding the

third.

• The first mate chooses one to play.

Now suppose you are the first mate, but the captain gave you 2 sabotage cards. Being a

crewmate, you wonder, did the captain just happen to have 3 sabotage cards, or was the

captain an imposter who secretly discarded a task card. In this scenario, what’s the probability

that the captain is an imposter? Let’s assume that imposter captains always try to discard

task cards, and crewmate captains always try to discard sabotage cards.

2. Lightbulbs

Consider an n × n array of switches. Each row i of switches corresponds to a single lightbulb

Li

, so that Li

lights up if at least i switches in row i are flipped on. All of the switches start

in the “off” position, and each are flipped “on” with probability p, independently of all others.

What is the expected number of lightbulbs that will be lit up? Express your answer in closed

form without any summations.

3. Compact Arrays

Consider an array of n entries, where n is a positive integer. Each entry is chosen uniformly

randomly from {0, . . . , 9}. We want to make the array more compact, by putting all of the

non-zero entries together at the front of the array. As an example, suppose we have the array

[6, 4, 0, 0, 5, 3, 0, 5, 1, 3].

After making the array compact, it now looks like

[6, 4, 5, 3, 5, 1, 3, 0, 0, 0].

Let i be a fixed positive integer in {1, . . . , n}. Suppose that the ith entry of the array is

non-zero (assume that the array is indexed starting from 1). Let X be a random variable

which is equal to the index that the ith entry has been moved after making the array compact.

Calculate E[X] and var(X).

1

4. Borel-Cantelli & Strong Law

In this problem, we walk through a proof of the strong law (assuming finite 4th moments)

that relies only on basic probability. In class we covered the Borel-Cantelli lemma, which

states that for events (An)∞

n=1, if P∞

n=1 P(An) < ∞, then

P(An i.o.) = 0,

where we define the event {An i.o.} = ∩n≥1 ∪m≥n An as the event where infinitely many An

occur.

(a) Let X1, X2, . . . be i.i.d. with EXi = 0 and EX4

i < ∞ (and so we also have finite second

and third moments). Let Sn = X1 + · · · + Xn, and compute E[S

4

n

]. Write your answer in

terms of the moments E[X2

i

], E[X3

i

], E[X4

i

].

(b) Fix an > 0, and use Markov’s inequality to show that, for any n,

P(|Sn/n| > ) ≤ O(n

−2

).

(c) Finally, use Borel-Cantelli to conclude that P(limn→∞ Sn/n = 0) = 1. This a weaker (the

full theorem assumes only finite first moments) form of the strong law of large numbers.

5. Bounds for the Coupon Collector’s Problem

Recall the coupon collector’s problem, where each box contains a single coupon, and there are

n different types of coupons. We let X be a random variable which is equal to the number of

boxes bought until one of every type of coupon is obtained.

The expected value of X is nHn, where Hn is the harmonic number of order n which is defined

as

Hn

∆=

Xn

i=1

1

i

,

and satisfies the inequalities

ln n ≤ Hn ≤ ln n + 1.

(a) Use Markov’s inequality in order to show that

P(X > 2nHn) ≤

1

2

.

(b) Use Chebyshev’s inequality in order to show that

P(X > 2nHn) ≤

π

2

6(ln n)

2

.

Note: You can use the identity

X∞

i=1

1

i

2

=

π

2

6

.

(c) Define appropriate events and use the union bound in order to show that

P(X > 2nHn) ≤

1

n

.

Note: The sequence an = (1 − 1/n)

n

, for n = 1, 2, 3, . . ., is strictly increasing and

limn→∞ an = 1/e.

2