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

Let $A_i$ be the event that candidate $i$ succeeds. The countable additivity axiom adds probabilities only for mutually disjoint events. Successes of different candidates are not mutually exclusive, so replacing the probability of their union by ${\sum }_i\mathbb{P}(A_i)=1$ misuses that axiom. Without disjointness one obtains only the union bound, not certainty. The same sum is the expected value of the number of successes, which also need not imply at least one.

If the ten outcomes are mutually independent events, with each success probability $0.1$, all fail with probability $0.9^{10}$. HenceThe independence assumption is essential. The marginal probabilities alone allow any union probability from $0.1$ up to $1$; perfectly overlapping success events give the lower endpoint and disjoint successes give the upper endpoint.

The independent random variables have a product joint probability mass function. For integers $r,t\ge 0$,It is zero for all other pairs. The factors are the respective Poisson distribution masses, with the product justified by independence.

By the definition of a probability generating function and the power series for the exponential function,The series is absolutely convergent for every finite real $s$; in particular the expression is finite for all $s>1$, as needed for the later tail estimate.

For $Z=2(X+Y)+1$, independence givesThe initial factor $s$ accounts for the shift by one; substituting $s^2$ accounts for doubling the random variable. Its support consists of positive odd integers.

Conditioning on $Z=z$ has positive probability exactly when $z=2r+1$ for an integer $r\ge 0$. This is the same event as $X+Y=r$. The addition of independent Poisson random variables gives a Poisson distribution with parameter $\lambda +\mu$ for the sum. Therefore, for $0\le t\le r$,Thus $X\mid \{Z=2r+1\}\sim \mathrm{Binomial}(r,\lambda /(\lambda +\mu ))$. The case $r=0$ is a constant zero random variable. For even, nonpositive, or noninteger $z$, the conditioning event has zero probability, so an event-conditional probability distribution is not specified by the quotient formula. This is a two-component case of Poisson-multinomial conditioning.

Because $s>1$, the function $t\mapsto s^t$ is increasing and nonnegative. Thus $\{X\ge x\}=\{s^X\ge s^x\}$. Applying Markov's inequality to the nonnegative random variable $s^X$, whose expected value is finite by assumption, yieldsUnder the usual probability generating function convention $X$ takes nonnegative integer values. The argument itself works for any real random variable if $G_X(s)$ is understood as the finite expected value $\mathbb{E}[s^X]$.

Insert the Poisson distribution probability generating function into the preceding bound:For fixed $x>\lambda$, differentiate the exponent with respect to $s$. Its derivative is $\lambda -x/s$, and its second derivative is $x/s^2>0$, so its unique minimum occurs at $s=x/\lambda >1$. At that value,ConsequentlyThis Chernoff bound remains valid for noninteger positive thresholds $x>\lambda$; the event is then the same as exceeding or equalling its integer ceiling.