Probability – Bound on MGF of Product of Two Independent Binomials

binomial distributionpr.probability

Consider the following: $r_1,…,r_t$ are iid symmetric signs taking value $\pm1$, independent of $B\sim Binomial(p, q)$ with integer $p$ and $q=p^{-1.01}$.

Question: Consider $t$ as a non-decreasing function of $p$. For which such non-decreasing function of $p$ does there exist a constant $\lambda>0$ independent of $p$ such that the following holds:
$$E[\exp(\lambda B \sum_{u=1}^t \frac{r_u}{\sqrt t})] \le 1.05,$$
for $p$ large enough.

Remark:
Note that $\tilde Z = \sum_u\frac{r_u}{\sqrt t}$ has variance 1 and is very close to $N(0,1)$, for instance by Tusnady's inequality. If $\tilde Z$ were replaced by 1 inside the exponential, we could proceed as follows: using the exact formula for the MGF of the binomial, and using $(1+x/p)^p\le e^x$,
$$
E[\exp(\lambda B)=
(1-q + qe^\lambda)^p
\le (1 + qe^\lambda)^p \le \exp(pq e^\lambda) \le \exp(p^{-0.01} e^{\lambda}),
$$

so that for any constant $\lambda$ (say, $\lambda=1$), the RHS is bounded from above by 1.05 or any other constant strictly greater than 1. If $t$ is constant, not growing to $\infty$ simultaneously as $p$, then we can use this remark to answer the question.

Edit: Another remark: the previous argument shows
$$E[\exp(\lambda \tilde Z B)=
(1-q + qe^{\lambda\tilde Z})^p
\le (1 + qe^{\lambda\tilde Z})^p \le \exp(pq e^{\lambda\tilde Z}) \le \exp(p^{-0.01} e^{\lambda\tilde Z})
$$

and since $\tilde Z\le \sqrt t$ always holds,
$\sqrt t = \log(p^{0.009})\asymp \log p$ with $\lambda=0$ works. The harder question is with $t$ varying more rapidly than this.

Best Answer

$\newcommand{\la}{\lambda}$The estimate of $t$ that you got cannot be improved. Indeed, let \begin{equation} S_t:=\sum_{u=1}^t \frac{r_u}{\sqrt t}. \end{equation} Suppose, as you did, that \begin{equation} E\exp(\la BS_t)\le1.05 \end{equation} for some real $\la>0$. Then \begin{equation} 1.05\ge\frac{\la^{2p}}{(2p)!}\,EB^{2p}\,ES_t^{2p} \gg \frac{\la^{2p}}{p^{2p}}\,EB^{2p}\,ES_t^{2p}, \end{equation} where $a\gg b$ means that $a\ge c^p b$ for some universal real constant $c>0$.

Using Corollaries 1 and 2 by LataƂa, we get \begin{equation} EB^{2p}\gg\Big(\frac p{\ln p}\Big)^{2p} \end{equation} and \begin{equation} ES_t^{2p}\gg \min[t^p,p^p]. \end{equation} Thus, \begin{equation} 1.05\gg \frac{\la^{2p}}{p^{2p}}\,\Big(\frac p{\ln p}\Big)^{2p}\,\min[t^p,p^p] =\la^{2p}\Big(\frac{\min[t,p]}{\ln^2 p}\Big)^p, \end{equation} which implies $\sqrt t=O(\ln p)$, as claimed.