91Ó°ÊÓ

It is given that \({X_1},{X_2},...\)are i.i.d. geometric random variables with parameter p.

Moment Generating Function:

Let X be a random variable.

For each real number t, define \(\psi \left( t \right) = E\left( {{e^{tx}}} \right)\) ……………………. (1)

The function \(\psi \left( t \right)\) is called the moment generating function of X.

Markov Inequality:

Suppose that X is a random variable such that \(\Pr \left( {X \ge 0} \right) = 1\).

Then for every real number\(t > 0\),

\(\Pr \left( {X \ge t} \right) \le \frac{{E\left( X \right)}}{t}\).

Let X be a random variable with a moment generating function (m.g.f.) \(\psi \).

Let, for every real t, \(\Pr \left( {X \ge t} \right) \le \mathop {\min }\limits_{s > 0} \exp \left( { - st} \right)\psi \left( s \right)\)

The result is trivial if the m.g.f. is infinite for all s>0.

So, assume that the m.g.f. is finite for at least some s>0.

For every t and every s>0 such that the m.g.f. is finite, then

\(\begin{array}{c}\Pr \left( {X > t} \right) = \Pr \left( {\exp \left( {sX} \right) > \exp \left( {st} \right)} \right)\\ \le \frac{{E\left( {\exp \left( {sX} \right)} \right)}}{{{\mathop{\rm ex}\nolimits} \left( {st} \right)}}\end{array}\)

\( = \psi \left( s \right)\exp \left( { - st} \right)\) From equation (1)

where the second equality follows from the above Markov inequality.

Since \(\Pr \left( {X > t} \right) \le \exp \left( { - st} \right)\psi \left( s \right)\)

Therefore, for every s, \(\Pr \left( {Y > t} \right) \le \mathop {\min }\limits_s \exp \left( { - st} \right)\psi \left( s \right)\)