2
$\begingroup$

I am interested in techniques for showing the concentration of sum of $n$ iid geometric random variables $X_1, X_2, \cdots, X_n$, say with success probability $p = 1/2$, taken to some power $d$. Let $S_n^{(d)} = X_1^d + \cdots + X_n^d$ be the sum of the random variables and let $\mu_d = \mathbb{E}(S_n^{(d)})$. I would like to show something of the form

$$P\left\lbrace S_n^{(d)} > (1 + \delta) \mu_d \right\rbrace \leq C\exp\left(-f(\delta) n^{\alpha}\right)$$

for some positive constant $C$, some $\delta \geq 0$, and some $0 < \alpha \leq 1$ that may be a function of $d$. For the case that $d = 1$, one is able to use a standard Chernoff type approach to obtain that

$$P\left\lbrace S_n^{(1)} > (1 + \delta) \mu_1 \right\rbrace \leq \exp\left(-g(\delta) n\right)$$

using the fact that $\mu_1 = 2n$ and letting $g(\delta) = (1 + 2\delta) \log\left(1 + 2 \delta\right) - 2 (1 + \delta) \log\left(1 + \delta\right)$. However, it seems such an approach breaks down for $d > 1$ because finding an upper bound for $\mathbb{E}\left(\exp(s X_i^d)\right)$, where $s$ is some positive parameter, is not possible.

The idea I had instead is to break the probability into pieces by conditioning. Let $b$ be some positive real number to be set later. Let $B$ be the indicator r.v. that is 1 if and only if $\forall i: X_i \leq b$ and let $E_d$ be an indicator that is $1$ if and only if $S_n^{(d)} > (1 + \delta) \mu_d$. Then we can do

\begin{align} P\left\lbrace E_d = 1 \right\rbrace &= P\left\lbrace E_d = 1 | B = 1\right\rbrace \underbrace{P\left\lbrace B = 1 \right\rbrace}_{\leq 1} + \underbrace{P\left\lbrace E_d = 1 | B = 0\right\rbrace}_{\leq 1} P\left\lbrace B = 0\right\rbrace \\ &\leq P\left\lbrace E_d = 1 | B = 1\right\rbrace + P\left\lbrace B = 0\right\rbrace \end{align}

By union bound, we can find that

\begin{align} P\left\lbrace B = 0 \right\rbrace &= P\left\lbrace \exists i: X_i > b\right\rbrace \\ &\leq \frac{n}{2^b} \\ &= \exp\left(-(b \ln(2) - \ln(n)\right) \end{align}

Also, $P\left\lbrace E_d = 1 | B = 1\right\rbrace$ seems to be something we can reason about with Hoeffding's inequality (using generalized sum version here) now since by the conditioning, the random variables in the sum are bounded. To help simplify this, I also worked out that $\frac{d! n}{2 \ln^{d+1}(2)} \leq \mu_d \leq \frac{d! n}{\ln^{d+1}(2)}$. With these ideas, we can find that

\begin{align} P\left\lbrace E_d = 1 | B = 1\right\rbrace &= P\left\lbrace S_n^{(d)} > (1 + \delta) \mu_d | \forall i: X_i \leq b\right\rbrace \\ &\leq \exp\left(- \frac{\delta^2 \mu_d^2}{n b^{2d}}\right) \\ &\leq \exp\left(- \left(\frac{ \delta d!}{2 \ln^{d+1}(2)}\right)^2 \frac{n}{b^{2d}}\right) \end{align}

If we combine the results, we obtain

\begin{align} P\left\lbrace S_n^{(d)} > (1 + \delta) \mu_d \right\rbrace &\leq \exp\left(- \left(\frac{ \delta d!}{2 \ln^{d+1}(2)}\right)^2 \frac{n}{b^{2d}}\right) + \exp\left(-(b \ln(2) - \ln(n)\right) \\ &\leq 2 \exp\left(- \min \left \lbrace \left(\frac{ \delta d!}{2 \ln^{d+1}(2)}\right)^2 \frac{n}{b^{2d}}, b \ln(2) - \ln(n)\right \rbrace \right) \end{align}

If one chooses $b = n^{1/(2d+1)}$, then for large enough $n$ we have

\begin{align} P\left\lbrace S_n^{(d)} > (1 + \delta) \mu_d \right\rbrace &\leq 2 \exp\left(- n^{1/(2d+1)}\min \left \lbrace \left(\frac{ \delta d!}{2 \ln^{d+1}(2)}\right)^2, \ln(2)/2\right \rbrace \right) \end{align}

which just about give us a result that fits what we want. However, this seems to be a bit weak, especially since setting $d = 1$ gives us an exponent for $n$ of $1/3$, which is noticeably worse than what was found by Chernoff.

Any recommendations or ideas on how one can obtain a stronger result for the $d > 1$ cases?

$\endgroup$
1

0

You must log in to answer this question.