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

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.