Past exam of the mathematics course of the year 1 of the natural sciences course of the University of Cambridge / 2010 / Paper 1 / 12

Use independent choices with constant probabilities $p$ and $q=1-p$. Completing the entire reverse circuit while the forward-moving object never moves requires the first $F$ choices all to be reverse moves. ThusHere and below, a zero-length product is interpreted as one, including at $p=0$ or $p=1$.

After $j$ choices, let $C_j$ be the number of forward moves. The two unwrapped positions are $C_j$ and $F-(j-C_j)$, whose gap is $F-j$. It follows that the first subsequent meeting occurs exactly at step $F$, regardless of the order of the choices. Its position is the number of forward moves in that block.

That count has a binomial distribution with parameters $F,p$. ThereforeThe two endpoint labels $0$ and $F$ represent the same physical seat reached by different complete circuits; the unwrapped convention distinguishes their probabilities.

The meeting position $N$ is the sum of $F$ independent Bernoulli random variables, each of mean $p$ and variance $pq$. Linearity of expectation and variance additivity for independent random variables giveThese are the mean and variance of the unwrapped integer label specified in the question, rather than circular angular statistics.

For the forward-moving object to have been waiting at the meeting position, the last move must be a reverse move. The preceding $F-1$ choices must then contain exactly $n$ forward moves and $F-n-1$ reverse moves. Choosing their order givesAt $n=F$ the probability is zero, since the reverse-moving object was already at that unwrapped position initially. At $n=0$ the displayed formula is $q^F$, consistent with the forward object waiting at its initial position throughout. Equivalently, use the binomial convention $\left(\genfrac{}{}{0ex}{}{F-1}{F}\right)=0$ to include this endpoint in the same formula without a negative power of $q$.

Let $N$ be the meeting label. If $N>n$, the forward-moving object has already crossed $n$ while the reverse-moving object has not yet reached it, so the forward object wins the race to $n$. If $N<n$, the reverse object passed $n$ first. If $N=n$, the required event is exactly the special meeting from part (d).

These disjoint possibilities giveThis includes the endpoints: for $n=0$ the probability is $1$, and for $n=F$ it is $0$, with the initial positions understood in the unwrapped convention.

First take $1\le n\le F-1$. The forward object reaches $n$ at its $n$th move, while the reverse object reaches that label at its $(F-n)$th move. If the forward object wins after $k$ reverse moves, then $0\le k\le F-n-1$. The final choice is forward; among the preceding $n+k-1$ choices, exactly $k$ are reverse. By the negative binomial stopping argument, this case has probability $\left(\genfrac{}{}{0ex}{}{n-1+k}{k}\right)p^n{q}^k$.

Sum these mutually exclusive cases and equate the result to part (e), using parts (b) and (d). This proves the success-failure stopping identity here:The right side splits the same race into a special meeting at $n$ and all meetings beyond $n$; the left side splits it according to the number of reverse moves at the winning time.

At $n=F$, both sides are zero with an empty sum and $\left(\genfrac{}{}{0ex}{}{F-1}{F}\right)=0$. At $n=0$, the event has probability one; the right side equals ${\sum }_{k=0}^F\left(\genfrac{}{}{0ex}{}{F}{k}\right)p^k{q}^{F-k}=1$. The printed left side includes $\left(\genfrac{}{}{0ex}{}{-1}{0}\right)$ and is outside the usual nonnegative-upper-index combinatorial definition. With the explicit generalized convention $\left(\genfrac{}{}{0ex}{}{-1}{0}\right)=1$, its $k=0$ term is one and all $k\ge 1$ terms vanish, so the identity also holds at that endpoint. Without this convention the displayed sum is undefined there; the zero-target race must instead be stated separately. All identities extend to $p=0,1$ by their polynomial forms.