Question

Return to Example 6.2.7.

a. Prove that the \({\min _{s > 0}}\psi \left( s \right)\exp \left( { - snu} \right)\) equals \({q^n}\), where q is given in (6.2.16).

b. Prove that \(0 < q < 1\). Hint: First, show that\(0 < q < 1\)if \(u = 0\). Next, let\(x = up + 1 - p\)and show that \(\log \left( q \right)\)is a decreasing function of x.

Short answer

1. It is proven thatthe \(\mathop {\min }\limits_{s > 0} \psi \left( s \right)\exp \left( { - snu} \right)\) equals \({q^n}\).

2. It is proved that\(0 < q < 1\)and log(q) is a decreasing function of x.

Step-by-step solution

Given information

\({X_1},{X_2},...\) be a sequence of i.i.d. geometric random variables with parameter p.

(a) Proving that \({\min _{s > 0}}\psi \left( s \right)\exp \left( { - snu} \right) = {q^n}\)

Moment generating function (m.g.f):

Let X be a random variable. For each real number t,

Define \(\psi \left( t \right) = E\left( {{e^{tx}}} \right)\)

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

Chernoff Bounds:

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

Then, for every real t,

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

This theorem is most useful when X is the sum of the n i.i.d. random variables, each with finite m.g.f. and when t=nufor a large value of n and some fixed n.

To prove that the \(\mathop {\min }\limits_{s > 0} \psi \left( s \right)\exp \left( { - snu} \right)\) equals \({q^n}\) where

\(q = \left[ {p\left( {1 - u} \right) + 1 - p} \right]{\left[ {\frac{{\left( {1 - u} \right)p + 1 - p}}{{up + 1 - p}}\left( {1 - p} \right)} \right]^{u + \left( {1 - p} \right)/p}}\)…….. (1)

First, insert the value of \(s = - \log \left[ {\frac{{\left( {1 - u} \right)p + 1 - p}}{{up + 1 - p}}\left( {1 - p} \right)} \right]\) into the equation below

\(\Pr \left( {X \ge nu} \right) \le \mathop {\min }\limits_{s > 0} {\left( {\frac{{p\left( {\exp \left[ { - s\left( {1 - p} \right)/p} \right]} \right)}}{{1 - \left( {1 - p} \right)\exp \left( s \right)}}} \right)^n}\exp \left( { - snu} \right)\)

This gives,

\(n\left[ {\log \left( p \right) + \left( {\frac{{1 - p}}{p} + u} \right)\log \left\{ {\frac{{\left( {1 + u} \right)p + 1 - p}}{{up + 1 - p}}\left( {1 - p} \right)} \right\} - \log \left\{ {1 - \frac{{1 - p}}{{\frac{{\left( {1 + u} \right)p + 1 - p}}{{up + 1 - p}}\left( {1 - p} \right)}}} \right\}} \right]\)

The last term can be rewritten as

\(\log \left\{ {1 - \frac{{1 - p}}{{\frac{{\left( {1 + u} \right)p + 1 - p}}{{up + 1 - p}}\left( {1 - p} \right)}}} \right\} = - \log \left( p \right) + \log \left\{ {\left( {1 + u} \right)p + 1 - p} \right\}\)

The result is then

\(\begin{array}{l}n\left[ {\log \left( p \right) + \left( {\frac{{1 - p}}{p} + u} \right)\log \left\{ {\frac{{\left( {1 + u} \right)p + 1 - p}}{{up + 1 - p}}\left( {1 - p} \right)} \right\} - \log \left( p \right)\log \left\{ {\left( {1 + u} \right)p + 1 - p} \right\}} \right]\\ = n\left[ {\left( {\frac{{1 - p}}{n} + u} \right)\log \left\{ {\frac{{\left( {1 + u} \right)p + 1 - p}}{{up + 1 - p}}\left( {1 - p} \right)} \right\} + \log \left\{ {\left( {1 - u} \right)p + 1 - p} \right\}} \right]\end{array}\)

This is easily recognized that the n times the logarithm of equation (1).

(b) Proving that \(0 < q < 1\) log (q) is a decreasing function of x

For all u, q is given by \(q = \left[ {p\left( {1 - u} \right) + 1 - p} \right]{\left[ {\frac{{\left( {1 - u} \right)p + 1 - p}}{{up + 1 - p}}\left( {1 - p} \right)} \right]^{u + \left( {1 - p} \right)/p}}\)

For u=0. \(q = {\left( {1 - p} \right)^{\left( {1 - p} \right)/p}}\)

Since,

\(0 < 1 - p < 1\)and \(\frac{{\left( {1 - p} \right)}}{p} > 0\)

Since,

\(0 < q < 1\) when u=0

In general, u, let \(x = p\left( {1 + u} \right) + 1 - p\) and rewrite

\(\log \left( q \right) = \log \left( {p + x} \right) + \frac{{p + x}}{p}\log \frac{{\left( {1 - p} \right)\left( {p + x} \right)}}{x}\)

Since x is a linearly increasing function of u, if it is shown to decrease in x, then q is decreasing in u.

The derivative of \(\log \left( q \right)\)concerning x is

\( - \frac{p}{{x\left( {p + x} \right)}} + \frac{1}{p}\log \frac{{\left( {1 - p} \right)\left( {p + x} \right)}}{x}\)

The first term is negative, and the second term is negative at \(u = 0\left( {x = 1} \right)\)

To be sure that the sum is always negative, examine the second term more closely. The derivative of the second term is

\(\frac{1}{p}\left( {\frac{1}{{p + x}} - \frac{1}{x}} \right) = \frac{{ - 1}}{{x\left( {p + x} \right)}} < 0\)

Hence the derivative is always negative, and q is less than 1 for all u.