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 / a

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.