Sale!

# Homework 1 Coin Flipping & Symmetry

\$30.00

Category:

## Description

Rate this product

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
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.