I would have a proof of the following fact; but it's a bit clunky, and am wondering if one can get a more elegant one (and/or improve the constants). I couldn't find this anywhere, and searching properties of the Skellam distribution didn't help much either.



> 
> Let $X\sim\operatorname{Poi}(\lambda)$ and $Y\sim\operatorname{Poi}(\mu)$ be two independent random variables. Then
> $$
>  \max(|\lambda-\mu|, \frac{1}{40}\min(\sqrt{\lambda+\mu}, \lambda+\mu)) \leq \mathbb E[|X-Y|] \leq\min(|\lambda-\mu|+\sqrt{\lambda+\mu}, \lambda+\mu)
> $$
> 
> 
> 


*Here is the current proof I came up with:*


The upper bound follows from Cauchy–Schwarz, as $\mathbb E[(X-Y)^2] = (\lambda-\mu)^2 + \lambda+\mu$; and by the triangle inequality, as $\mathbb{E}[|X-Y|]\leq \mathbb{E}[X+Y]$. The lower bound $|\lambda-\mu|$ is a direct consequence of Jensen's inequality; we now proceed to establish the second term.


* Consider first the case $\lambda+\mu\geq 1$. We will use Paley–Zygmund, noting that for any $c\in(0,1)$ we have
$$
 \mathbb{E}[|X-Y|] \geq c\sqrt{\mu+\lambda}\cdot\mathbb{P}\{|X-Y|\geq c\sqrt{\mu+\lambda} \}
 $$
and
$$
 \begin{align\*}
 \mathbb{P}\{|X-Y|&\geq c\sqrt{\mu+\lambda}\} \\ &= \mathbb{P}\{(X-Y)^2\geq c^2(\mu+\lambda)\} \\
 &\geq \mathbb{P}\{(X-Y)^2\geq c^2\mathbb{E}[(X-Y)^2]\}\\
 &\geq (1-c^2)^2\frac{\mathbb{E}[(X-Y)^2]^2}{\mathbb{E}[(X-Y)^4]}\\
 &= \frac{ (1-c^2)^2(\lambda+\mu+(\lambda-\mu)^2)^2}{\lambda+\mu+6(\lambda^2+\mu^2)+6(\lambda-\mu)^2(\lambda+\mu)+(\lambda-\mu)^2+(\lambda-\mu)^4}\\
 &\overset{(\dagger)}{\geq} (1-c^2)^2 \frac{(\lambda+\mu)^2+(\lambda-\mu)^4}{(\lambda+\mu)+10(\lambda+\mu)^2+3(\lambda-\mu)^4}\\
 &\overset{(\ddagger)}{\geq} \frac{(1-c^2)^2}{11} 
 \end{align\*}
$$
where $(\dagger)$ is using the AM-GM inequality and $(a-b)^2\leq (a+b)^2$; and $(\ddagger)$ relies on $\lambda+\mu \leq (\lambda+\mu)^2$, which holds since $\lambda+\mu\geq 1$.
Taking $c=1/\sqrt{5}$ concludes the proof of this case, as then $\frac{c(1-c^2)^2}{11} > \frac{1}{40}$.
* If $\lambda+\mu \leq 1$, we will use properties of the modified Bessel function of the first kind $I\_0$ (namely, that it is nondecreasing on $[0,\infty)$, with $e^{-x}I\_0(x) \geq 1-\frac{x}{2}$ for $x\in[0,1]$) to conclude, as
$$
\begin{align}
 \mathbb{E}[|X-Y|] &\geq 
 1 - \mathbb{P}\{|X-Y|=0\} \\
&= 1- e^{-(\lambda+\mu)} I\_0(2\sqrt{\lambda\mu}) \\
&\geq 1- e^{-(\lambda+\mu)} I\_0(\lambda+\mu)
 \geq \frac{\lambda+\mu}{2}
 \end{align}$$
where the first inequality is the AM-GM inequality.



Bounds on the expectation of $|X-Y|$ for $X,Y$ Poisson
$\newcommand{\la}{\lambda}$Let us show that
\begin{equation\*}
 E|Z|\ge J(1)\min[c,\sqrt c\,], \tag{1}
\end{equation\*}
where
\begin{equation\*}
 Z:=X-Y,\quad c:=\la+\mu, 
\end{equation\*}
\begin{equation\*}
 J(x):=\frac2\pi\,\int\_0^\infty\frac{1-\exp\{-x\, (1-\cos t)\}}{t^2}\,dt. 
\end{equation\*}
Mathematica's command NIntegrate[] produces
\begin{equation\*}
 J(1)=0.67390\dots. 
\end{equation\*}
So, the constant factor $J(1)$ is an about 27-times improvement of the corresponding coefficient $\frac1{40}$ in the OP. Moreover, the constant factor $J(1)$ is the best possible.


Inequality (1) is based on the Zolotarev identity
\begin{equation\*}
 E|Z|=\frac2\pi\,\int\_0^\infty\frac{1-\Re Ee^{itZ}}{t^2}\,dt; 
\end{equation\*}
see e.g. formula (3.26) in [this paper](https://link.springer.com/article/10.1007/s10959-016-0709-1) or formula (48) in the corresponding [arXiv preprint](https://arxiv.org/pdf/1603.07365). In our case,
\begin{equation\*}
 \Re Ee^{itZ}=\exp\{-c(1-\cos t)\}\cos((\la-\mu)\sin t)\le\exp\{-c(1-\cos t)\}; 
\end{equation\*}
Moreover, the latter inequality will turn into the equality when $\la=\mu$.


So,
\begin{equation\*}
 E|Z|\ge J(c), \tag{2}
\end{equation\*}
and the latter inequality will turn into the equality when $\la=\mu$.


Note that, for each real $z>0$,
\begin{equation\*}
 \frac{1-e^{-zx}}x=\int\_0^z e^{-xu}\,du
\end{equation\*}
is decreasing in $x$. So, $J(x)/x$ is decreasing in real $x>0$. Moreover, as shown in [this answer](https://mathoverflow.net/a/396573/36721), $J(x)/\sqrt x$ is increasing in real $x>0$. So, $J(c)\ge cJ(1)$ if $c\in(0,1]$ and $J(c)\ge\sqrt c\,J(1)$ if $c\in[1,\infty)$.


Thus, (1) follows from (2). Moreover, (1) turns into the equality when $\la=\mu=1/2$ (so that $c=1$).


