Homework 4: Probability in Motion

Geometric probability, absorbing random walks, and coupon collection

Derive three classic probability results and check them in important special cases.
ProbabilityIndividualWritten derivations
Your goal: turn each random process into a precise probability model, derive the requested result, and use boundary or special cases to show that the result is sensible.
Submithw4submission.pdf
AnnouncedMon, Oct 19, 2026after Lecture 21: Probability
DueMon, Nov 2, 202611:59 PM Eastern · 14 days
RequirementShow intermediate steps
ImportantSubmission contract

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.

Two circular pools. In the left pool, three numbered positions lie on one side of a dashed diameter. In the right pool, three positions are spread around the circle and no semicircle contains them all.

Three points may all fit on one side of a diameter, or they may wrap around the circle so that no semicircle contains all three.
  1. For \(n=2\), compute the probability that all ducks are contained in some semicircle.
  2. For \(n=3\), compute the same probability.
  3. For general integer \(n \ge 2\), derive the probability that all \(n\) ducks are contained in some semicircle.
TipHint

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

A horizontal number line with absorbing endpoints negative N and positive M. From state k, a curved arrow points left with probability one minus p and another points right with probability p.

From an interior state \(k\), the walker moves left with probability \(1-p\) or right with probability \(p\); the endpoints are absorbing.
  1. Derive the recurrence for \(P_k\) and state both boundary conditions.
  2. Express \(P_{-N+1}\) and \(P_{-N+2}\) in terms of \(p\) and \(P_{-N+3}\), assuming \(N \ge 3\).
  3. Solve for \(P_k\) for every \(-N \le k \le M\). Handle the fair-walk case \(p=\tfrac12\) separately from \(p\ne\tfrac12\).
  4. Evaluate \(P_2\) when \(p=0.6\), \(M=10\), and \(N=6\).
  5. 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.

TipHint

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.

One draw from a pack branches with equal probability to card types one, two, three, four, and through type N.

Every draw selects one of the \(N\) card types with probability \(1/N\).
  1. What is the probability of drawing one specified type on a single draw?
  2. What is the expected number of draws until that specified type appears for the first time?
  3. If exactly \(k\) distinct types have already been collected, what is the expected number of additional draws until a new type appears?
  4. 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\).
TipHint

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.