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

A partition of a set $\Omega$ is a collection of nonempty subsets $B_i$ such that $B_i\cap B_j=\varnothing$ for $i\ne j$ and ${\bigcup }_{i\in I}{B}_i=\Omega$. Thus every outcome lies in exactly one cell. For a probability-space partition the cells must also be measurable events. Nonempty cells may nevertheless have probability zero.

For an integrable random variable $X$, the law of total expectation on the finite or countable measurable partition isHere $\mathbb{E}(X\mid B_i)=\mathbb{E}[X{1}_{B_i}]/\mathbb{P}(B_i)$ for positive-probability cells; null cells contribute zero and need no conditional value. The series is absolutely convergent since its absolute terms sum to at most $\mathbb{E}|X|$. For a nonnegative $X$, the same identity is valid with possible value $+\infty$.

For a nonnegative integer-valued random variable $X$, its probability generating function isAt $s=0$, use $0^0=1$ so $G_X(0)=\mathbb{P}(X=0)$. The series also converges absolutely for complex $|s|\le 1$; for $s$ near zero, its coefficients recover the probability mass function.

Summing a geometric series gives the probability generating function of the zero-based geometric distribution:The series converges for $|(1-p)s|<1$, in particular on $[0,1]$. At $p=1/2$, $G_N(s)=1/(2-s)$, $G_N^{\prime }(s)=(2-s{)}^{-2}$, and $G_N^{\prime \prime }(s)=2(2-s{)}^{-3}$. The factorial moment identities give $\mathbb{E}(N)=G_N^{\prime }(1)=1$ and $\mathbb{E}[N(N-1)]=G_N^{\prime \prime }(1)=2$. Thus

Use the measurable partition $B_n=\{N=n\}$ for $n\ge 0$, omitting any null cells. For $0\le s\le 1$, the random variable $s^X$ is bounded, so the law of total expectation applies without moment assumptions. Conditional on $N=n$, the sum contains exactly $n$ terms. Independence of $N$ from the whole sequence preserves their joint law under this conditioning; independence of the $Y_k$ then givesFor $n=0$ the empty sum is zero and the empty product is one, in agreement with the formula. Therefore the probability generating function of an independent random sum is

A Bernoulli random variable with parameter $1/2$ has $G_Y(s)=(1+s)/2$. Part (i) and the geometric distribution formula giveComparing coefficients in the probability generating function identifiesThus $X$ has the zero-based geometric distribution with success parameter $2/3$. The probabilities sum to one, and its mean $1/2$ agrees with the random-sum mean $\mathbb{E}(N)\mathbb{E}(Y_1)=1\cdot 1/2$.