5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Are the $X_i$ independent ? $\endgroup$ – Gabriel Romon Aug 30 '19 at 13:24
  • $\begingroup$ @GabrielRomon Yes, thanks. $\endgroup$ – J.John Aug 30 '19 at 13:25
  • $\begingroup$ Do you mean $\Pr(X_i=c_2)=1-\alpha/i$ instead of $\Pr(X_i=c_2/i)=1-\alpha/i$ ? $\endgroup$ – Gabriel Romon Aug 30 '19 at 13:26
  • $\begingroup$ @GabrielRomon No, I really actually mean $X_i=c_2/i$, otherwise, the expectation cannot decay as $1/i$. $\endgroup$ – J.John Aug 30 '19 at 13:30
  • $\begingroup$ 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$.... $\endgroup$ – Olivier Aug 30 '19 at 15:20
4
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – J.John Aug 31 '19 at 7:21
  • $\begingroup$ @J.John see my edit. $\endgroup$ – Olivier Aug 31 '19 at 8:54
  • $\begingroup$ Very nice! ${}$ $\endgroup$ – Gabriel Romon Aug 31 '19 at 9:03
  • $\begingroup$ @Olivier Awesome, very nice. $\endgroup$ – J.John Aug 31 '19 at 9:37
  • $\begingroup$ What is the purpose if not indiscrete? $\endgroup$ – Olivier Aug 31 '19 at 10:42
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – J.John Aug 30 '19 at 14:20
  • $\begingroup$ @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}$. $\endgroup$ – Gabriel Romon Aug 30 '19 at 14:37
  • $\begingroup$ Nice question; I wonder what is the correct order of magnitude for the tail... $\endgroup$ – Olivier Aug 30 '19 at 15:07
  • $\begingroup$ @Olivier Perhaps you could run simulations ? I'm also curious. $\endgroup$ – Gabriel Romon Aug 30 '19 at 15:20
  • $\begingroup$ @GabrielRomon if I had no lectures to prepare I would do ! :-) $\endgroup$ – Olivier Aug 30 '19 at 15:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.