Chernoff Bounds using importance sampling identity

[WMDhamnekar]

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.