Past exam of the computer science course of the University of Oxford / 2015 / Probability and computing / 1

The expectation of a real random variable $X$ on a probability space is its integral against the probability measure:For a discrete random variable, this becomes $\mathbb{E}X={\sum }_{x}x\mathbb{P}(X=x)$; for a random variable with probability density function $f$, it becomes $\mathbb{E}X={\int }_{-\infty }^{\infty }xf(x)dx$. A finite expectation requires $\mathbb{E}|X|<\infty$, making $X$ an integrable random variable. An extended expectation can also be defined when just one of the positive and negative parts has finite expectation; the indeterminate difference $\infty -\infty$ is not allowed.

For a real random variable $X$ with finite expectation $\mu =\mathbb{E}X$, its variance isWhen the second moment is finite, expansion and linearity of expectation give $\mathrm{Var}(X)=\mathbb{E}[X^2]-{\mu }^2$. The definition also permits infinite variance when the expectation is finite but the second moment is infinite.

Chebyshev's inequality assumes a real random variable $X$ with finite expectation $\mu$ and finite variance ${\sigma }^2$. For every real $a>0$,No independence assumption is needed. Applying Markov's inequality to the nonnegative random variable $(X-\mu {)}^2$ proves the formula, including the zero-variance case.

Let $D_i$ be the result of roll $i$, so $X={\sum }_{i=1}^{100}{D}_i$. Each $D_i$ has the uniform distribution on a finite set $\{1,\dots ,6\}$, givingand hence variance $\mathrm{Var}(D_i)=91/6-(7/2{)}^2=35/12$. The rolls are independent, so linearity of expectation and variance additivity for independent random variables giveAll the required moments are finite. Taking $a=50$ in Chebyshev's inequality now yieldsThis is an upper bound, rather than an exact tail probability.

Choose a positive integer-valued random variable with probability mass functionThese masses are positive. They sum to one because the partial fraction decompositionmakes their sum a telescoping series with value $2/(1\cdot 2)=1$. Its expectation is another telescoping series:By contrast, since $k+1\le 2k$ and $k+2\le 3k$ for $k\ge 1$, its second moment satisfiesThe comparison uses the divergent harmonic series. To check the variance directly, for $k\ge 4$ we have $(k-2{)}^2\ge k^2/4$, so the corresponding tail of $\mathbb{E}[(X-2{)}^2]$ also diverges. ThusHere “unbounded” means infinite variance for this single probability distribution.

For $X$ with binomial distribution $B(n,p)$, where $n$ is a nonnegative integer and $0\le p\le 1$, use its probability mass function and the binomial theorem:This moment-generating function of a binomial distribution is finite for every real $t$, since the random variable has finite support. The formula also includes the degenerate cases $p=0$, $p=1$ and $n=0$.

The independence of $X$ and $Y$ permits factoring the expectation of the product $e^{tX}{e}^{tY}$. The moment-generating function of a binomial distribution from the previous part therefore givesThis is the moment-generating function of $B(n+m,p)$. Both moment-generating functions are finite on a neighbourhood of zero, so the uniqueness theorem for moment-generating functions identifies the probability distribution:The common success probability $p$ and independence are both used in this argument.