Homework 4: Probability in Motion
Geometric probability, absorbing random walks, and coupon collection
hw4submission.pdf
Upload one PDF named hw4submission.pdf to Canvas. Define any event or random variable you introduce, justify the main steps of each derivation, and simplify final expressions when possible. No starter download is required for this written assignment.
1. Ducks in a circular pool
There are \(n\) ducks on the circumference of a circular pool. Each duck’s position is selected independently and uniformly at random. A closed semicircle may be rotated to any orientation after the positions are observed. Configurations with coincident or exactly opposite positions have probability zero and do not affect the answer.

- For \(n=2\), compute the probability that all ducks are contained in some semicircle.
- For \(n=3\), compute the same probability.
- For general integer \(n \ge 2\), derive the probability that all \(n\) ducks are contained in some semicircle.
Symmetry and anchoring: rotating the entire configuration does not change its probability. Consider a clockwise semicircle whose starting boundary passes through one observed duck. Explain why some such anchored semicircle contains all ducks whenever the configuration fits in a semicircle, and why these anchor events do not overlap except on probability-zero configurations.
2. Random walk with absorbing barriers
A walker starts at integer position \(k\) on the interval \([-N,M]\), where \(M,N\) are positive integers. At every step, the walker moves right with probability \(p\) and left with probability \(q=1-p\). Reaching \(-N\) or \(M\) ends the walk.
Let
\[P_k = \Pr(\text{reach } M \text{ before } -N \mid X_0=k).\]
For Parts 1-3, assume \(0<p<1\).

- Derive the recurrence for \(P_k\) and state both boundary conditions.
- Express \(P_{-N+1}\) and \(P_{-N+2}\) in terms of \(p\) and \(P_{-N+3}\), assuming \(N \ge 3\).
- Solve for \(P_k\) for every \(-N \le k \le M\). Handle the fair-walk case \(p=\tfrac12\) separately from \(p\ne\tfrac12\).
- Evaluate \(P_2\) when \(p=0.6\), \(M=10\), and \(N=6\).
- Evaluate \(P_2\) when \(p=0.4\), \(M=10\), and \(N=6\).
For each numerical answer, give at least four decimal places and briefly compare the two biased walks.
First-step analysis: condition on whether the next step is left or right, then express \(P_k\) using the probabilities at those neighboring states. The law of total probability is
\[\Pr(A)=\sum_i \Pr(A\mid B_i)\Pr(B_i),\]
where the \(B_i\) are disjoint events covering all possible outcomes. Here, the two next-step directions form that partition.
The absorbing states supply the boundary values. As a check, your closed form should produce \(P_{-N}=0\) and \(P_M=1\). In the fair case, the answer should be linear in the starting position.
3. Coupon collector
There are \(N\) distinct card types, with \(N \ge 1\). Each independent draw produces one of the \(N\) types uniformly at random. Duplicates are kept but do not increase the number of distinct types collected.

- What is the probability of drawing one specified type on a single draw?
- What is the expected number of draws until that specified type appears for the first time?
- If exactly \(k\) distinct types have already been collected, what is the expected number of additional draws until a new type appears?
- Derive the expected total number of draws \(E[T]\) required to collect all \(N\) types. Express the result using the harmonic number \(H_N\) and define \(H_N\).
Waiting-time stages: let \(W_k\) be the number of additional draws needed to obtain a new type when \(k\) distinct types have been collected. While that stage lasts, each independent draw has the same success probability \(s_k\). Counting the successful draw, the waiting time has mean
\[E[W_k]=\frac{1}{s_k}.\]
Find \(s_k\) by counting the types still missing. Then use \(T=\sum_{k=0}^{N-1}W_k\) and linearity of expectation:
\[E[T]=\sum_{k=0}^{N-1}E[W_k].\]
Linearity does not require the stage durations to be independent.