Bounding tails of sum of not identical random variables

Question

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.

Answer 1

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.

Answer 2

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)$$