Upper bound for difference of Poisson random variables Let $X, Y$ be random variables with Poisson$(\lambda)$ and Poisson$(2\lambda)$ distributions, respectively.Then
(i) If we assume that $X, Y$ are independent, $$\mathbb{P}(X \geq Y) \leq e^{-(3-\sqrt8)\lambda}.$$
(ii) Now, assume that $X, Y$ are not independent, then there exist $A, c >0$,  both not depending on $\lambda$, such that $$\mathbb{P}(X \geq Y) \leq Ae^{-c\lambda}.$$ 
I have no idea how to solve this problems. I try setting $Z = X - Y$, but I do not know how to find the upper bound, and how that $e^{-(3 - \sqrt8)\lambda}$ comes from.

Note:
$X$ has a Poisson$(\lambda)$ distribution if, for any integer $j\geq 0$, $$\mathbb{P}(X = j) = \frac{\lambda^je^{-j}}{j!}.$$
 A: For the first one, for any $t>0$, $$P(X\geq Y)=P(tX\geq tY)=P(t(X-Y)\geq0)=P(e^{t(X-Y)}\geq1)\leq E(e^{tX})E(e^{-tY})$$ by Markov inequality and independence. Noticing that $E(e^{tX})$ is the moment generating function of $X$ (and noticing the same about $Y$), and substituting the forms of the moment general function, we get a bound that is equal to $e^{-3\lambda+\lambda(e^t+2e^{-t})}$ so we finally have: $$P(X\geq Y)\leq e^{-3\lambda+\lambda(e^t+2e^{-t})}$$ The LHS is independent of $t$, so the inequality is true for every $t>0$, so in particular $$P(X\geq Y)\leq \inf_{t>0}\exp(-3\lambda+\lambda(e^t+2e^{-t}))=\exp(-3\lambda+\lambda\inf_{t>0}(e^t+2e^{-t}))$$ Using calculus, determine the infimum, which occurs for $t=\frac12\log(2)$, and conclude.
For the second one, $$P(X\geq Y)=P(e^{X-Y}\geq 1)\leq E(e^{X-Y})\leq \sqrt{E(e^{2X})E(e^{-2Y})}$$
by Markov inequality and Cauchy-Schwarz inequality. Now can you finish?
A: For the first part, (i):
$$
\mathbb{P}\{X \geq Y\}\} = \mathbb{E}[\mathbb{1}_{\{X \geq Y\}}] 
= \mathbb{E}[\mathbb{E}[\mathbb{1}_{\{X \geq Y\}}\mid Y] ]. 
$$
Dealing with the inner conditional expectation first,
$$
\mathbb{E}[\mathbb{1}_{\{X \geq Y\}}\mid Y]
= e^{-\lambda} \sum_{k=0}^\infty \mathbb{1}_{\{k \geq Y\}} \frac{\lambda^k}{k!}
= e^{-\lambda} \sum_{k=Y}^\infty \frac{\lambda^k}{k!}.
$$ 
Now, the outer expectation:
$$\begin{align}
\mathbb{E}[\mathbb{E}[\mathbb{1}_{\{X \geq Y\}}\mid Y] ]
&= \mathbb{E}\left[ e^{-\lambda} \sum_{k=0}^\infty \mathbb{1}_{\{k \geq Y\}} \frac{\lambda^k}{k!} \right]
= e^{-\lambda} \sum_{k=0}^\infty  \frac{\lambda^k}{k!} \mathbb{E}\left[\mathbb{1}_{\{k \geq Y\}} \right]\\
&= e^{-\lambda} \sum_{k=0}^\infty  \frac{\lambda^k}{k!} \mathbb{P}\{Y \leq k\}
= e^{-\lambda} \sum_{k=0}^\infty  \frac{\lambda^k}{k!} e^{-2\lambda}\sum_{\ell=0}^k \frac{2^\ell\lambda^\ell}{\ell!} \\
&= e^{-3\lambda} \sum_{k=0}^\infty \sum_{\ell=0}^k   \frac{2^\ell\lambda^{k+\ell}}{k!\ell!} \tag{$\dagger$}.
\end{align}$$

It remains to compute this ugly expression:
$$\begin{align}
\sum_{k=0}^\infty \sum_{\ell=0}^k   \frac{2^\ell\lambda^{k+\ell}}{k!\ell!} 
&= 
\sum_{k=0}^\infty \sum_{n=0}^{2k}   \frac{2^{n-k}\lambda^{n}}{(n-k)!k!} 
= \sum_{k=0}^\infty \sum_{n=0}^{2k}  \frac{\lambda^n}{n!} \binom{n}{k} 2^{n-k} \\
&= 
\sum_{n=0}^\infty \sum_{k=\lceil n/2\rceil}^{n}  \frac{\lambda^n}{n!} \binom{n}{k} 2^{n-k} \\
&= 
\sum_{n=0}^\infty \frac{2^n \lambda^n}{n!} \sum_{k=\lceil n/2\rceil}^{n}  \binom{n}{k} 2^{-k}
\end{align}
$$
so to conclude, it it sufficient to show that
$$
\sum_{k=\lceil n/2\rceil}^{n}  \binom{n}{k} 2^{-k} \leq \sqrt{2}^n \tag{$\ddagger$}
$$
as this will imply
$$\begin{align}
\sum_{k=0}^\infty \sum_{\ell=0}^k   \frac{2^\ell\lambda^{k+\ell}}{k!\ell!} 
&\leq 
\sum_{n=0}^\infty \frac{2^n\sqrt{2}^n \lambda^n}{n!} 
= e^{2\sqrt{2}\lambda} = e^{\sqrt{8}\lambda}
\end{align}
$$ 
and therefore 
$$\begin{align}
\mathbb{E}[\mathbb{E}[\mathbb{1}_{\{X \geq Y\}}\mid Y] ]
&\leq e^{-3\lambda} e^{\sqrt{8}\lambda} = e^{-(3-\sqrt{8})\lambda} 
\end{align}$$
by ($\dagger$).

Proving ($\ddagger$):
But this is the case since, for any $k\geq \frac{n}{2}$, we have $\frac{1}{2^k} \leq \frac{1}{\sqrt{2}^n}$, so that
$$
\sum_{k=\lceil n/2\rceil}^{n}  \binom{n}{k} 2^{-k}
\leq 
\frac{1}{\sqrt{2}^n} \sum_{k=\lceil n/2\rceil}^{n}  \binom{n}{k}
= \frac{2^n}{\sqrt{2}^n} = \sqrt{2}^n.
$$

Part 2:
Without any assumption on how $X$ and $Y$ are correlated, one can still write
$$
\mathbb{P}\{ X \geq Y \}  = 1 - \mathbb{P}\{ X < Y \}
$$
and
$$
\mathbb{P}\{ X < Y \}  \geq \mathbb{P}(\{ X \leq \frac{5}{4}\lambda \}\cap \{ Y \geq \frac{3}{2}\lambda \}).
$$
Now, using standard concentration inequalities about Poisson r.v.'s (see e.g. these tail bounds), we get that, for $a\geq0$,
$$\begin{align}
\mathbb{P}\{X > \lambda + a\lambda \} &\leq e^{-\lambda((a+1)\ln(a+1)-a))} \\
\mathbb{P}\{Y < 2\lambda - a\lambda \} &\leq e^{-\lambda\left(a - 2(1-\frac{a}{2})\ln(1-\frac{a}{2}))\right)}
\end{align}$$
which, for $a=\frac{1}{4}$, gives (by a union bound) $\mathbb{P}(\{ X \leq \frac{5}{4}\lambda \}\cap \{ Y \geq \frac{3}{2}\lambda \}) \geq 1 - 2e^{-c\lambda}$ for some absolute constant $c > 0$. This gives the desired result:
$$
\mathbb{P}\{ X \geq Y \}  \leq  2e^{-c\lambda}.
$$
A: For the first problem, i would try this way (but i'm not sure it will work though ;) :
$\mathbb{P}(X \geq Y) = \sum_{k \geq 0} \mathbb{P}(X \geq k, Y=k) = e^{-3\lambda}\sum_{k \geq 0} \sum_{i=k}^{\infty} \frac{\lambda^{i+k}2^k}{i! k!}$.
