Past exam of the year 1 of the computer science course of the University of Oxford / 2003 / Calculus, probability, linear algebra, discrete mathematics, logic and proof, and models of computation / 5

For events $A,B$ with $\mathbb{P}(B)>0$, the conditional probability isIt measures the probability of $A$ after restricting the sample space to $B$ and renormalizing. This quotient does not define conditional probability given an event of zero probability.

The partition theorem is the law of total probability. If $B_1,B_2,\dots$ form a finite or countable partition of a sample space into pairwise disjoint events with positive probabilities, then for any event $A$,Indeed, $A$ is the disjoint union of the events $A\cap B_j$, so countable additivity gives the formula after applying the definition of conditional probability. Zero-probability members can be omitted.

Let $X_j$ be the indicator random variable that coin $j$ shows a head. Each expectation is $\mathbb{E}{X}_j=1/2$, so linearity of expectation gives the expected number of heads:For the game, write $p_i$ for the probability that $H$ eventually holds all $n$ coins when starting with $i$. The states $0,n$ are absorbing, so $p_0=0$ and $p_n=1$. Conditioning on the first toss and using the law of total probability givesThus $p_{i+1}-p_i=p_i-p_{i-1}$: successive differences are constant, and $p_i=A+Bi$. The boundary values give $A=0$, $B=1/n$, hence the gambler's ruin answer isFor completeness, the game terminates with probability one. From any nonabsorbing state, a run of $n$ consecutive heads would reach $n$ within the next $n$ tosses, and that run has probability $2^{-n}$. Conditional on survival, the same bound applies to the next block. Therefore the probability of surviving $kn$ tosses is at most $(1-2^{-n}{)}^k$, which tends to zero.

Let $W$ be the event that $H$ wins, and $F$ the event that his first toss is a tail. For a nontrivial starting state $1\le i\le n-1$, a first tail has probability $1/2$ and changes his holding to $i-1$. By the chain rule for probabilities,Since $\mathbb{P}(W)=i/n>0$, the definition of conditional probability givesIn particular, when $i=1$, losing the first coin would end the game in defeat, so the conditional answer is zero. At $i=0$ conditioning on victory is undefined, while at $i=n$ the game has already ended and no first toss occurs.

Let $I$ be the number of heads in the initial allocation tosses. Then $I$ has the binomial distribution with parameters $n$ and $1/2$. Given $I=i$, the winning probability is $i/n$, including the already finished games $i=0,n$. The law of total probability and linearity of expectation giveThus, for $n\ge 1$,