Homework 1 Coin Flipping & Symmetry

EECS 126: Probability and Random Processes
Homework 1

1. Coin Flipping & Symmetry
Alice and Bob have 2n + 1 fair coins (where n ≥ 1), each coin with probability of heads equal
to 1/2. Bob tosses n+ 1 coins, while Alice tosses the remaining n coins. Assuming independent
coin tosses, show that the probability that, after all coins have been tossed, Bob will have
gotten more heads than Alice is 1/2.
Hint: Consider the event A = {more heads in the first n + 1 tosses than the last n tosses}.
2. Passengers on a Plane
There are N passengers in a plane with N assigned seats (N is a positive integer), but after
boarding, the passengers take the seats randomly. Assuming all seating arrangements are
equally likely, what is the probability that no passenger is in their assigned seat? Compute
the probability when N → ∞.
Hint: Use the inclusion-exclusion principle and the power series e
x =
P∞
j=0 x
j/j!.
3. Expanding the NBA
The NBA is looking to expand to another city. In order to decide which city will receive a new
team, the commissioner interviews potential owners from each of the N potential cities (N is
a positive integer), one at a time. Unfortunately, the owners would like to know immediately
after the interview whether their city will receive the team or not. The commissioner decides
to use the following strategy: she will interview the first m owners and reject all of them
(m ∈ {1, . . . , N}). After the mth owner is interviewed, she will pick the first city that is better
than all previous cities. The cities are interviewed in a uniformly random order. What is the
probability that the best city is selected? Assume that the commissioner has an objective
method of scoring each city and that each city receives a unique score.
You should arrive at an exact answer for the probability in terms of a summation. Approximate
your answer using Pn
i=1 i
−1 ≈ ln n and find the optimal value of m that maximizes the
probability that the best city is selected. You can also say ln(n − 1) ≈ ln n.
Hint: Consider the events Bi = {i-th city is the best} and A = {best city is chosen}.
4. Random Walk on a Circle
Suppose we have n points labeled {1, 2, . . . , n} around a circle. An ant starts at point 1, and
at each second has an equal probability of moving clockwise or counterclockwise to an adjacent
point. For each point k ∈ {2, 3, . . . , n}, find the probability that the first time the ant lands
at k, it has visited all other points already.
5. Superhero Basketball
Superman and Captain America are playing a game of basketball. At the end of the game,
Captain America scored n points and Superman scored m points, where n > m are positive
integers. Supposing that each basket counts for exactly one point, what is the probability that
1
after the start of the game (when they are initially tied), Captain America was always strictly
ahead of Superman? (Assume that all sequences of baskets which result in the final score of n
baskets for Captain America and m baskets for Superman are equally likely.)
Hint: Think about symmetry. First, try to figure out which is more likely: there was a tie
and Superman scored the first point, or there was a tie and Captain America scored the first
point?
2