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!

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

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.