Question

Let \({X_1},{X_2},...\)be a sequence of i.i.d. random variables having the exponential distribution with parameter 1. Let \({Y_n} = \sum\limits_{i = 1}^n {{X_i}} \)for each \(n = 1,2,...\)

a. For each\(u > 1\), compute the Chernoff bound on \(\Pr \left( {{Y_n} > nu} \right)\).

b. What goes wrong if we try to compute the Chernoff bound when\(u < 1\).

Short answer

a. The Chernoff bound for \(\Pr \left( {{Y_n} > nu} \right)\) is\({\left[ {u{e^{\left( {1 - u} \right)}}} \right]^n}\).

b. If \(u < 1\), then \(\Pr \left( {X \ge t} \right) \le \mathop {\min }\limits_{x > 0} \;\exp \left( { - st} \right)\psi \left( s \right)\) is minimized over \(s > 0\)near \(s = 0\),

which provides a useless bound of 1 for \(\Pr \left( {{Y_n} > nu} \right)\).

Step-by-step solution

Given information

Let \({X_1},{X_2},...\) is the sequence of i.i.d random variables follows exponential distribution with parameter 1.

Computing the Chernoff bound on \(\Pr \left( {{Y_n} > nu} \right)\)

The m.g.f of the exponential distribution with parameter 1 is\(\frac{1}{{1 - s}}\)for\(s < 1\).

Since, \({Y_n} = \sum\limits_{i = 1}^n {{X_i}} \) for each \(n = 1,2,...\)

Hence,

The m.g.f. of \({Y_n}\) is \(\frac{1}{{{{\left( {1 - s} \right)}^n}}}\) for\(s < 1\).

From theorem 6.2.7, The Chernoff bound is the minimum (over\(s > 0\)) of\(\frac{{{e^{ - nus}}}}{{{{\left( {1 - s} \right)}^n}}}\)

The logarithm of this is\( - n\left[ {us + \log \left( {1 - s} \right)} \right]\), which is minimized at \(s = \frac{{\left( {u - 1} \right)}}{u}\), which is positive if and only if \(u > 1\).

Therefore, the Chernoff bound for \(\Pr \left( {{Y_n} > nu} \right)\) is\({\left[ {u{e^{\left( {1 - u} \right)}}} \right]^n}\).

Computing the Chernoff bound on \(\Pr \left( {{Y_n} > nu} \right)\) when \(u < 1\)

If \(u < 1\), then \(\Pr \left( {{Y_n} > nu} \right) \le \mathop {\min }\limits_{x > 0} \;\exp \left( { - st} \right)\psi \left( s \right)\) is minimized over \(s > 0\)near \(s = 0\),

which provides a useless bound of 1 for \(\Pr \left( {{Y_n} \ge nu} \right)\)