Suppose X is a discrete random variable with $\mathbb{E}[X] = \mu$, such that $\mathbb{E}[(X - \mu)^k] = \Theta(\mu^{k-1})$ for every $k \geq 2$. What (if anything) can be said about the concentration of $X$ around its mean?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ Can't you use a standard Chernoff-type argument to get that $\Pr[X-\mu\geq a]\leq \exp(\Theta(t\mu)-ta)$? Or a higher-order Chebyshev to get that for any $p\in\mathbb{N}$, $\Pr[|X-\mu|>\lambda] \leq \frac{1}{\mu}\Theta((\mu/\lambda)^p)$. In either setting, you get concentration for $\lambda > \mu$ (perhaps with a constant implicit in $\Theta(\mu^{k-1})$ as well). $\endgroup$– Mark Schultz-WuCommented Sep 21, 2021 at 16:29
-
$\begingroup$ I could, but in both cases the bound that I get is too weak for my purposes. I would like to bound $Pr[X - \mu \geq a]$ for $a = \epsilon \cdot \mu$, for $\epsilon$ tending to zero. The Chernoff-type bound gives nothing in this range, and Chebyshev's inequality gives a bound of $1/\mu$, which is too weak (and follows from the standard Chebyshev without needing higher moments). $\endgroup$– Lior GishbolinerCommented Sep 21, 2021 at 17:41
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
Suppose $X$ is a discrete random variable with $EX=\mu$ such that $E(X-\mu)^k=\Theta(\mu^{k-1})$ for every $k \ge2$.
According to the general convention, $f(n)=\Theta(g(n))$ means that there exist positive constants $c_1$, $c_2$, and $n_0$ such that $0 ≤ c_1g(n) ≤ f(n) ≤ c_2g(n)$ for all $n ≥ n_0$.
So, the highlighted condition makes sense only if $\mu\in[0,\infty)$.
To avoid trivialities, assume that $\mu>0$. Then the highlighted condition means exactly that $P(0\le X\le2\mu)=1$ and $P(X=0)<P(X=2\mu)$.
So, essentially nothing can be said in general about the concentration of $X$ around its mean.
answered Sep 21, 2021 at 17:03
-
$\begingroup$ I don't quite understand. If for example $P(X = 2\mu) = 1/3$, $P(X = \mu/2) = 2/3$, then the conditions you wrote are satisfied, but $E[(X - \mu)^k] = \Theta(\mu^k)$ for every $k \geq 2$. I use the same definition of the $\Theta$-notation as you wrote, only that $c_1,c_2$ are not allowed to depend on $\mu$ (but may depend on $k$). $\endgroup$ Commented Sep 21, 2021 at 17:36
-
$\begingroup$ @LiorGishboliner : To avoid wasting time and efforts of those who would try to help you, you should have said in your post that you were using a very non-standard notion of $\Theta$. Moreover, you should have defined your $\Theta$ quite rigorously, with all the quantifiers ($\exists$ and $\forall$) in proper places, just as is done in the standard definition of $\Theta$; as a researcher in mathematics, you should certainly be able to do that. From your comment, it is unclear what you want. However, it seems that taking a specific $\mu$ (say $\mu=3$) will take care of your concerns. $\endgroup$ Commented Sep 21, 2021 at 19:59