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