0
$\begingroup$

Say we have the following inequality: $ A < B < C$ where $A, B$ and $C$ are positive integer-valued random variables. Assume that $A$ is concentrated in $O(m)$ values with high probability and $C$ is concentrated in $O(n)$ values whp.

Then, does it follow that B is concentrated in $O(m) + O(n) + \mathbb{E}[C-A]$ values with high probability? Can we improve this?

Thanks!

1 Answers 1

1

If $A$ is concentrated on $(a-m,a+m)$ with probability at least $1-u$ and $C$ is concentrated on $(c-n,c+n)$ with probability at least $1-v$, then $A\lt B\lt C$ implies that $B$ is concentrated on $(a-m,c+n)$ with probability at least $1-u-v$. And there exists $b$ such that $(a-m,c+n)=(b-k,b+k)$ with $k=\frac12(c-a)+\frac12(m+n)$.

The result you ask for is a priori problematic, on the other hand, since there is no guarantee that a random variable concentrates most efficiently around its expectation.