Upper bound on $P(n^{-1}\sum_{i=1}^n (X_i - \lambda_i)>t)$ for independent $X_i\sim\operatorname{Poisson}(\lambda_i)$

Let $$X_1,\dots,X_n$$ be independent random variables, $$X_i \sim \operatorname{Poisson}(\lambda_i),$$ $$i=1,\dots,n.$$ Let $$S=n^{-1}\sum_{i=1}^n X_i, \quad\quad \lambda=n^{-1}\sum_{i=1}^n \lambda_i.$$ Find an upper bound for $$P(S-\lambda>t)$$. What $$t$$ do we need in order $$P(S-\lambda>t)\leq n^{-\tau}$$ for some $$\tau>0$$?

I am not sure how to go about finding an upper bound for $$P(S-\lambda > t)$$ in this problem. Any help would be appreciated.

• Try Cantelli's inequality. – user158565 Nov 4 '18 at 0:07
• This seems like a poorly-worded pair of questions; as is, an upper bound of $1$ works well for the first question, and we can always find a $\tau>0$ such that $n^{-\tau} \geq 1-P(S=0)$, so any $t>-\lambda$ works for the second question. (Note $P(S=0)$ is the probability of $x=0$ where $x \sim \text{Poisson}(\sum \lambda_i)$, and is always $>0$.) – jbowman Nov 4 '18 at 0:28
• Is this a homework question? In that case add the self-study tag. – Martijn Weterings Nov 4 '18 at 7:45

$$\sum_{i=1}^n X_i$$ follows Poisson distribution with parameter $$\sum_{i=1}^n \lambda_i$$. So $$S =n^{-1} \sum_{i=1}^n X_i$$ has mean $$n^{-1}\sum_{i=1}^n \lambda_i = \lambda$$ and variance $$n^{-2}\sum_{i=1}^n \lambda_i = n^{-1}\lambda$$.
According to Cantelli's inequality, $$P(S-\lambda>t) \le \frac {n^{-1}\lambda}{n^{-1}\lambda + t^2}$$
To get $$P(S-\lambda>t)\leq n^{-\tau}$$, we need $$\frac {n^{-1}\lambda}{n^{-1}\lambda + t^2} = n^{-\tau}$$
So $$t=\sqrt{\frac {\lambda(n^{\tau}-1)}n}$$
• Could we maybe calculate a harder bound using the following? $$P(S - \lambda > t) = P(n S > n(t+\lambda)) = 1- F_\lambda(n(t+\lambda)) = 1 - \sum_{i=1}^{\lfloor n(t+\lambda) \rfloor} \frac{\lambda^i}{i!} \leq n^{-\tau}$$ where $F_\lambda(x)$ is the cumulative distribution of the Poisson distribution with rate parameter $\lambda$ (also expressed by the regularized Gamma function) – Martijn Weterings Nov 4 '18 at 8:01