# On the use of Chebyshev's inequality for obtaining asymptotic estimate in a proof

For the full context of the problem please refer to the proof of Prediction $$3$$ in the note: https://terrytao.wordpress.com/2015/01/04/254a-supplement-4-probabilistic-models-and-heuristics-for-the-primes-optional/.

We have a sequence of non-negative random variables $$X_n$$ that have mean zero and are independent, each of size $$O(\log x) = O(x^{o(1)})$$. Fix some natural number $$x$$, it can be seen that

$$\displaystyle \mathop{\bf E} (\sum_{2 < n \leq x} X_n)^k = O( x^{k/2+o(1)})$$

for any fixed natural number $${k}$$. The argument then follows with:

From Chebyshev’s inequality this implies that $${\sum_{2 < n \leq x} X_n = O( x^{1/2+\varepsilon})}$$ with probability $${1-O( x^{-k\varepsilon + o(1)})}$$.

Question: With the given bound, a direct application of Chebyshev's inequality gives $$\displaystyle {\bf P}(|\sum_{2 < n \leq x} X_n - O(x^{1/2 + o(1)})| \geq t) \leq \frac{O(x^{1+o(1)})}{t^2}$$ for some threshold $$t > 0$$. I wonder what value of $$t$$ is being inserted here and how the given claim follows as it does.

Edit: It turns out that here we are using Chebyshev’s inequality in what is called the “measure-theoretic” form in https://en.wikipedia.org/wiki/Chebyshev%27s_inequality#Measure-theoretic_statement in order to get more decay in the t parameter (by taking the “p” parameter to be large, here we call it k); the $$p=2$$ case of Chebyshev’s inequality is too weak for this application.

• What is the "size" of a rv? Commented Apr 23 at 2:23
• @VezenBU: The largest of its absolute value. Commented Apr 23 at 4:28

Fix $$k\in\mathbb N$$. Chebyshev's inequality tells us that for any integrable and non-negative random variable $$X$$, and $$t>0$$, $$\mathbb P(X\ge t)\le \frac{\mathbb E[X^k]}{t^k}.\tag1$$ So now let $$X:=\sum_{2 < n \leq x} X_n$$ and $$t:=x^{1/2+\varepsilon}$$. We are given that $$\mathbb E[X^k]=O( x^{k/2+o(1)})$$, so that applying $$(1)$$ above yields \begin{align} \mathbb P(X\ge t)&:=\mathbb P\left(\sum_{2 < n \leq x} X_n\ge x^{1/2+\varepsilon}\right)\\ &\le\frac{O( x^{k/2+o(1)})}{x^{k/2+k\varepsilon}}\\ &= O(x^{-k\varepsilon+o(1)}) \end{align} The above inequality tells us that with probability $$1-O(x^{-k\varepsilon+o(1)})$$, the quantity $$\sum_{2 < n \leq x} X_n$$ is bounded by $$x^{1/2+\varepsilon}$$, which in particular implies that
[...] $${\sum_{2 < n \leq x} X_n = O( x^{1/2+\varepsilon})}$$ with probability $$1-O(x^{-k\varepsilon+o(1)})$$.