- #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} ##
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.
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: