Problem Set 2 Among Us

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