Past exam of the year 1 of the computer science course of the University of Oxford / 2023 / Discrete mathematics, probability and continuous mathematics / 8

In independent Bernoulli trials with success probability $p$, $N$ counts failures before the first success. The event $N=n$ requires $n$ failures followed by one success, giving $(1-p{)}^{n}p$. This is the zero-based geometric distribution, rather than the count of trials including the success.

Let $q=1-p$. By the definition of a probability generating function and the geometric series,The series converges absolutely when $|qs|<1$, equivalently $|s|<1/(1-p)$.

Differentiate the probability generating function inside its radius of convergence:The first moment and second factorial moment are $\mathbb{E}[N]=G_N^{\prime }(1)=q/p$ and $\mathbb{E}[N(N-1)]=G_N^{\prime \prime }(1)=2q^2/p^2$. Consequently

Take an independent and identically distributed sequence with $X_i\sim \mathrm{Bernoulli}(r)$, independent of $N$. Conditional on $N=n$, the random sum ${\sum }_{i=1}^n{X}_i$ has binomial distribution with parameters $n,r$, including the empty sum at $n=0$. This construction therefore has exactly the prescribed joint law of $(N,Z)$ and represents $Z$ as the required random sum.

For a literal representation that retains an already given pair $(N,Z)$, enlarge the probability space by auxiliary randomness. Conditional on $N=n,Z=z$, choose uniformly a size-$z$ subset of $\{1,\dots ,n\}$, put ones at those indices and zeros at the others, and append independent Bernoulli variables of parameter $r$. Given $N=n$, a specified length-$n$ pattern with $z$ ones has probability $\left(\genfrac{}{}{0ex}{}{n}{z}\right)r^z(1-r{)}^{n-z}/(\genfrac{}{}{0ex}{}{n}{z})=r^z(1-r{)}^{n-z}$. Thus the entire sequence is independent and identically distributed and independent of $N$, while its first $N$ terms sum to the original $Z$.

The probability generating function of an independent random sum states that, for a nonnegative integer-valued $N$ independent of independent and identically distributed nonnegative integer-valued summands, $G_{{\sum }_{i=1}^N{X}_i}(s)=G_N(G_{X_1}(s))$ wherever the expectations converge. Here $G_{X_1}(s)=1-r+rs$, so, writing $q=1-p$,It is valid at least for $|s|\le 1$, and its power series in fact converges for $|s|<(p+qr)/(qr)$.

Set $p_{\ast }=p/[p+(1-p)r]$. The preceding probability generating function becomes $p_{\ast }/[1-(1-p_{\ast })s]$, identifyingEquivalently, for $z\in \mathbb{N}$, $\mathbb{P}(Z=z)=p_{\ast }[(1-p_{\ast }){]}^z$. Since $0<p,r<1$, also $0<p_{\ast }<1$. This is the existing geometric count under Bernoulli thinning, with the zero-based convention specified.

The given four probabilities factor into independent Bernoulli indicators for the occurrence of $A$ and $B$ on each trial, with parameters $p$ and $r$. Independent trials make the full sequence of $A$ indicators independent of the full sequence of $B$ indicators. Let $N$ count trials strictly before the first $A$. Then $N\sim {\mathrm{Geom}}_0(p)$, independently of the $B$ indicators, and the desired count is their sum over these $N$ trials. Therefore its distribution is ${\mathrm{Geom}}_0(p/[p+(1-p)r])$, as in part (b).

The word “before” excludes the stopping trial: an $AB$ on that trial stops the experiment but does not add to the count. Another check is to discard all $ab$ trials. Among the remaining relevant outcomes, stopping has probability $p/[p+(1-p)r]$ and an additional pre-stopping $B$ has the complementary probability, again giving the same zero-based geometric distribution.