Optimized Chernoff Bound

Question

I'm trying to find the optimized Chernoff bound of a sum of i.i.d. discrete random variables X_i, 0$\leq$ i < n, with support {-1,0,1}. I also know that pX₀(1) > pX₀(-1). However, I'm not sure if I optimized the bound correctly over t.

My attempt looks like this:

I computed the moment generating function of X₀ as

M_X0(t) = E[$e^{tX0}$] = $\sum_{k=1}^{\infty} e^{tX0(k)}$pX₀(k) = $e^{t(-1)}$pX₀(-1) + $e^{t(1)}$pX₀(1) + pX₀(0)

I then found the moment generating function of the sum of the random variables from 0 to n-1 by multiplying their respective moment generating functions:

M_Sn = M[$\sum_{i=0}^{n-1}$ X_i] = M_X0 M_X1 … M_Xn-1 = [$e^{-t}$pX₀(-1) + $e^{t}$pX₀(1)+pX₀(0)]$^{n}$

The optimized Chernoff bound for Pr[S_n$\le$a] is given by

Pr[S_n$\le$a] $\le$ min $e^{ta}$ $\prod _ { i = 0 } ^ n E[e^{-tXi}]$
Pr[S_n$\le$0] $\le$ [$e^{-t}$pX₀(-1) + $e^{t}$pX₀(1) + pX₀(0)]$^{n}$

Letting c1 = pX₀(-1) and c2 = pX₀(1), I then minimize the above expression by taking its derivative and setting it equal to 0 to obtain

-c1$e^{-t}$ + c2$e^{t}$ = 0
c2$e^{t}$ = c1$e^{-t}$
$e^{2t}$ = c1/c2
2t = ln(c1/c2)
t = $\frac 1 { 2 }$ln$\frac {c1} {c2}$

Substituting the optimized value of t into the generic Chernoff bound I obtain

Pr(S_n$\leq$0) $\leq$ [($\frac {pX0(-1)} {pX0(1)}$) $^{-1/2}$ pX₀(-1) + ($\frac {pX0(-1)} {pX0(1)}$) $^{1/2}$ pX₀(1) + pX₀(0)]$^n$

Is this the correct optimized Chernoff bound for Pr[S_n$\le$0]? Thanks for your help and insights.

Answer 1

Your calculation seems to be correct but your final value of t is less than 0 as probability of getting a 1 is greater than getting a -1 as you stated earlier. So you can't use that value if you actually try to minimize the expression you have to put t equals to 0 which will be of no use.