- #1

WMDhamnekar

MHB

- 376

- 28

How to use importance sampling identity to obtain the Chernoff bounds as given below?

Let X have moment generating function ##\phi(t)= E[e^{tX}]##. Then, for any c > 0 ,

##P[X\geq c ]\leq e^{-tc} \phi(t), \text{if t > 0}##

##P[X \leq c]\leq e^{-tc}\phi(t), \text{if t<0} ##

Here's an example of using the importance sampling identity to obtain Chernoff bounds for a binomial random variable.

Suppose we have a binomial random variable ##X \sim \text{Bin}(n,p)##, where

Let ##X = \sum_{i=1}^n X_i##, where the ##X_i## are independent Bernoulli random variables with parameter

Then, by the importance sampling identity, we have ##P(X \geq (1+\delta)np) = E_Q\left[\prod_{i=1}^n \frac{dP_i}{dQ_i}I_{X \geq (1+\delta)np}\right]##

Now, let ##\phi_i(t) = E[e^{tX_i}] = 1 + p(e^t - 1)## and ##\psi_i(t) = E_Q[e^{tX_i}] = 1 + q(e^t - 1)##.

By choosing ##Q_i## such that ##\frac{dP_i}{dQ_i} = e^{tX_i - \log \phi_i(t)}##, we obtain ##P(X \geq (1+\delta)np) = E_Q\left[e^{tX - n\log \phi(t)}I_{X \geq (1+\delta)np}\right]##

Applying Markov's inequality, we get ##P(X \geq (1+\delta)np) \leq e^{-t(1+\delta)np}E_Q\left[e^{tX - n\log \phi(t)}\right] = e^{-t(1+\delta)np}\prod_{i=1}^n\psi_i(t)e^{-\log \phi_i(t)} = e^{-t(1+\delta)np}\left(\frac{1+q(e^t-1)}{1+p(e^t-1)}\right)^n##

This is the Chernoff bound for a binomial random variable. By choosing an appropriate value of

In my opinion, this solution seems to look correct. Do you have any doubts? Let me know, so that I shall clear them.

Let X have moment generating function ##\phi(t)= E[e^{tX}]##. Then, for any c > 0 ,

##P[X\geq c ]\leq e^{-tc} \phi(t), \text{if t > 0}##

##P[X \leq c]\leq e^{-tc}\phi(t), \text{if t<0} ##

*Solution:*Here's an example of using the importance sampling identity to obtain Chernoff bounds for a binomial random variable.

Suppose we have a binomial random variable ##X \sim \text{Bin}(n,p)##, where

**n**is the number of trials and**p**is the probability of success on each trial. We want to bound the probability that**X**deviates from its mean by more than a certain amount, i.e., we want to bound ##P(X \geq (1+\delta)np)## for some ##\delta > 0##.Let ##X = \sum_{i=1}^n X_i##, where the ##X_i## are independent Bernoulli random variables with parameter

**p**. Let ##Q_i## be a Bernoulli distribution with parameter**q**, and let ##Q = Q_1 \times \cdots \times Q_n##.Then, by the importance sampling identity, we have ##P(X \geq (1+\delta)np) = E_Q\left[\prod_{i=1}^n \frac{dP_i}{dQ_i}I_{X \geq (1+\delta)np}\right]##

Now, let ##\phi_i(t) = E[e^{tX_i}] = 1 + p(e^t - 1)## and ##\psi_i(t) = E_Q[e^{tX_i}] = 1 + q(e^t - 1)##.

By choosing ##Q_i## such that ##\frac{dP_i}{dQ_i} = e^{tX_i - \log \phi_i(t)}##, we obtain ##P(X \geq (1+\delta)np) = E_Q\left[e^{tX - n\log \phi(t)}I_{X \geq (1+\delta)np}\right]##

Applying Markov's inequality, we get ##P(X \geq (1+\delta)np) \leq e^{-t(1+\delta)np}E_Q\left[e^{tX - n\log \phi(t)}\right] = e^{-t(1+\delta)np}\prod_{i=1}^n\psi_i(t)e^{-\log \phi_i(t)} = e^{-t(1+\delta)np}\left(\frac{1+q(e^t-1)}{1+p(e^t-1)}\right)^n##

This is the Chernoff bound for a binomial random variable. By choosing an appropriate value of

**t**, we can obtain a tight bound on the tail probability.In my opinion, this solution seems to look correct. Do you have any doubts? Let me know, so that I shall clear them.

Last edited: