# Bounding tails of sum of not identical random variables

Let $$\{X_i\}_{i=1}^n$$ be a set of $$n$$ statistically independent random variables such that $$\Pr(X_i=c_1)=\alpha/i$$, and $$\Pr(X_i=c_2/i)=1-\alpha/i$$, and the constants $$c_1<0,c_2>0$$, and $$\alpha>0$$, are such that the expectation of each random variable $$\mathbb{E}(X_i) \leq -\beta/i$$, for some $$\beta>0$$. I want to upper bound the following probability $$\Pr\left(\sum_{i=1}^nX_i>C\right),$$ for some value of $$C>0$$. I am also interested in upper bounding $$\Pr\left(\max_{1\leq j\leq n}\sum_{i=1}^jX_i>C\right).$$ Note that $$\sum_{i=1}^n\mathbb{E}(X_i) = -\beta\sum_{i=1}^n1/i$$, and so it diverges to $$-\infty$$ logarithmically in $$n$$. Since the random variables are highly non-identical I am not sure how to derive meaningful upper bound on these probabilities. I'm interested in any non-trivial (i.e., strictly less than $$1$$). I tried to use Hoeffding's inequality but it seems that it is not the "right tool" to use in this scenario.

• Are the $X_i$ independent ? – Gabriel Romon Aug 30 '19 at 13:24
• @GabrielRomon Yes, thanks. – J.John Aug 30 '19 at 13:25
• Do you mean $\Pr(X_i=c_2)=1-\alpha/i$ instead of $\Pr(X_i=c_2/i)=1-\alpha/i$ ? – Gabriel Romon Aug 30 '19 at 13:26
• @GabrielRomon No, I really actually mean $X_i=c_2/i$, otherwise, the expectation cannot decay as $1/i$. – J.John Aug 30 '19 at 13:30
• Back of the envelope calculation suggest the tail of the max is at least $e^{-\gamma C}$, for some positive constant $\gamma$ by assuming the first trials are all positive up to the time you reach $k$.... – Olivier Aug 30 '19 at 15:20

The classical method of exponentiating before taking Markov inequality gives a better bound for the tail of $$S_n$$, polynomial in $$n$$. To wit:

According to the question,

$$E[X_n] = c_1 \frac{\alpha}{n} + \frac{c_2}{n} (1-\frac{\alpha}{n}) \sim \frac{c_1 \alpha+c_2}{n}$$

and I will set $$\gamma =c_1 \alpha + c_2$$, a quantity that is negative by your assumption.

Let $$\beta >0$$ be a parameter that we will be chosen after. By Markov inequality:

$$P[S_n >x] = P[e^{\beta S_n} >e^{\beta x}] \le \frac{E[e^{\beta S_n}]}{e^{\beta x}}$$

Now,

\begin{align*} E[e^{\beta X_n}]& =e^{\beta c_1} \frac{\alpha}{n} + e^{\beta\frac{c_2}{n}}(1-\frac{\alpha}{n})\\ & = (1 + (e^{\beta c_1}-1)) \frac{\alpha}{n} + (1+ \beta \frac{c_2}{n} + O(\frac{1}{n^2}))(1-\frac{\alpha}{n}) \\ & = 1 + \frac{1}{n} ((e^{\beta c_1}-1) \alpha+ \beta c_2 ) + O(\frac{1}{n^2}) \end{align*}

Now consider: $$\varphi: \beta \mapsto (e^{\beta c_1}-1) \alpha+ \beta c_2$$

For $$\beta$$ small, we have $$\varphi(\beta)=\beta (c_1 \alpha + c_2) +O(\beta^2)= \gamma \beta + c_2 +O(\beta^2)$$, and we said $$\gamma<0$$; this proves the function has a negative derivative at $$0$$, hence its minimum, attained at $$\beta_0>0$$, is strictly negative: call it $$\varphi(\beta_0)<0.$$

Then for some constant $$C<\infty$$ (to incorporate the products of the remainders in $$O(1/n^2))$$,

$$P[S_n >x] = \frac{E[e^{\beta_0 S_n}]}{e^{\beta_0 x}} \le C e^{\varphi(\beta_0) \log(n) -\beta_0 x} =C n^{\varphi(\beta_0)} e^{-\beta_0 x},$$

which gives you a polynomial decay, that should be close to the truth (reasoning heuristically). You also have for free the exponential decay in $$x$$.

--

As for the max,

$$M_n =\Big(\frac{e^{\beta_0 S_n}}{E[e^{\beta_0 S_n}]}\Big)_n$$ is a positive martingale. By the above, we may write $$E[e^{\beta_0 S_n}]= C_n n^{\varphi(\beta_0)}$$ for a sequence $$C_n$$ converging to $$C \in (0,\infty)$$. Now, Doob's martingale inequality gives:

$$P(\max_{m =0...n} M_m \ge x)\le \frac{E[M_0]}{x}$$

which gives in our case:

$$P(\max_{m =0...n} \frac{e^{\beta_0 S_n}}{C_n n^{\varphi(\beta_0)}} \ge x)\le \frac{1}{x}$$

In particular (this is much weaker!),

$$P(\max_{m =0...n} e^{\beta_0 S_m} \ge x \max C_m)\le \frac{1}{x}$$

meaning:

$$P( \max_{m =0...n} S_m \ge \frac{\log(x \max C_m)}{\beta_0}) \le \frac{1}{x}$$

or

$$P( \max_{m =0...n} S_m \ge x)\le (\max C_m) e^{-\beta_0 x}$$

and the right hand side does no more depend on $$n$$, so it is indeed a bound on the max over the whole path.

--

It has to be checked there is no hidden dependence in the constant $$C$$ above : I don't think so, but I have not checked carefully.

• That's great, thanks! For the max, indeed by union bound if $\phi(\beta_0)$ is small than $-1$ we will have a constant upper bound. But, in particular example it could be the case that it might be bigger than $-1$. – J.John Aug 31 '19 at 7:21
• @J.John see my edit. – Olivier Aug 31 '19 at 8:54
• Very nice! ${}$ – Gabriel Romon Aug 31 '19 at 9:03
• @Olivier Awesome, very nice. – J.John Aug 31 '19 at 9:37
• What is the purpose if not indiscrete? – Olivier Aug 31 '19 at 10:42

For the record, here's what Hoeffding yields: $$P(S_n>C)\leq \exp\left(-2 \frac{\left(C-\sum_{i=1}^n \frac 1i \left[\alpha c_1 + (1-\frac{\alpha}i)c_2 \right] \right)^2}{\sum_{i=1}^n \left(\frac{c_2}i -c_1 \right)^2} \right)$$

Note that under OP's assumption, $$\alpha c_1+c_2\leq 0$$ and \begin{aligned}C-\sum_{i=1}^n \frac 1i \left[\alpha c_1 + (1-\frac{\alpha}i)c_2 \right] &= C+\alpha c_2\sum_{i=1}^n \frac 1{i^2}+|\alpha c_1+c_2|\sum_{i=1}^n \frac 1i\\ &\geq C+\alpha c_2 + |\alpha c_1+c_2| \log(n+1) \end{aligned}

One also has $$\sum_{i=1}^n \left(\frac{c_2}i -c_1 \right)^2\leq 2\sum_{i=1}^n \frac{c_2^2}{i^2} + 2c_1^2n\leq 4c_2^2 + 2c_1^2n$$, hence the bound $$P(S_n>C)\leq \exp\left(\frac{-2[|\alpha c_1+c_2| \log(n+1)+ C+\alpha c_2]^2}{2c_1^2n + 4c_2^2} \right)$$ The argument of $$\exp$$ is asymptotically $$\displaystyle \sim \frac{-2(\alpha c_1+c_2)^2}{2c_1^2} \frac{\log^2 n}{n}$$, so the RHS of the bound goes to $$1$$, and this is not a concentration bound.

Using Markov's bound, $$P(S_n >C)\leq \frac{V(S_n)}{[C-E(S_n)]^2}$$

and $$\displaystyle V(S_n) = \sum_{i=1}^n V(X_i) = \sum_{i=1}^n \left( \frac{c_1^2\alpha}i + \left(1-\frac{\alpha}i\right) \frac{c_2^2}{i^2} - \frac 1{i^2} \left[\alpha c_1 + (1-\frac{\alpha}i)c_2 \right]^2 \right)$$ which is asymptotically $$\sim c_1^2 \alpha \log n$$. A bit more work should provide a constant $$A$$ such that $$\forall n,\; V(S_n)\leq c_1^2 \alpha \log n + A$$

Using the same lower bound on $$[C-E(S_n)]^2$$ as before, $$P(S_n >C) \leq \frac{c_1^2 \alpha \log n + A}{(\alpha c_1+c_2)^2 \log^2(n)} = O\left( \frac{1}{\log n} \right)$$

• Thanks. That's what I got also. Is there any method to get something meaningful, i.e., even upper bounding the probability by some constant $c<1$. Maybe it is actually impossible to do that, and the probability in question actually converges to 1? – J.John Aug 30 '19 at 14:20
• @J.John See my edit. I got an asymptotic upper bound that goes to $0$. With a bit more work in the inequalities I think you can get a non-asymptotic bound in $\frac 1{\log n}$. – Gabriel Romon Aug 30 '19 at 14:37
• Nice question; I wonder what is the correct order of magnitude for the tail... – Olivier Aug 30 '19 at 15:07
• @Olivier Perhaps you could run simulations ? I'm also curious. – Gabriel Romon Aug 30 '19 at 15:20
• @GabrielRomon if I had no lectures to prepare I would do ! :-) – Olivier Aug 30 '19 at 15:22