About the equivalence of two asymptotic probabilistic statements

44 Views Asked by At

Let $g(n)$ be some monotone increasing function of naturals, and let $X_n$ be a sequence of positive random variables. Consider the following two claims:

Claim 1. $\exists f=o(g(n)),\ \mathbb{P}(X_n<f(n))\to 1$.

Claim 2. $\forall\delta>0$, $\mathbb{P}(X_n<\delta g(n))\to 1$.

Are these two claims equivalent?

1

There are 1 best solutions below

1
On

Suppose Claim 1 holds. Fix $\delta > 0$. There exists an $N_1$ large enough such that $\frac{f_n}{g_n}< \delta$ for all $n \geq N_1$. Now fix $\epsilon > 0$. There exists $N_2$ large enough such that $1-\Pr(X_n < f_n) < \epsilon$ for all $n \geq N_2$. Define $N = \max\{N_1, N_2\}$. Since we have $\Pr(X_n < f_n) \leq \Pr(X_n < \delta g_n)$ for all $n \geq N$, we can conclude that $1 - \Pr(X_n < \delta g_n) \leq 1-\Pr(X_n < f_n) < \epsilon$ for all $n \geq N$. Thus Claim 2 holds.

Now suppose Claim 2 holds. Let $\delta_k$ be a sequence monotonically decreasing to zero. For each $\delta_k$ there exists $N_k$ such that for $n \geq N_k$, we have $1-\Pr(X_n < \delta_k g_n) < 2^{-k}$. Pick $N_k$ to form a monotonically increasing sequence and construct $f_n$ as follows:

$$ f_n = \begin{cases} \delta_1g_n \qquad \text{for $n < N_1$}\\ \delta_kg_n \qquad \text{for $N_{k-1}\leq n < N_k$, $k = 2, 3, \cdots$} \end{cases} $$

Then $\frac{f_n}{g_n} \to 0$ and $1-\Pr(X_n<f_n) \to 0$, so Claim 1 holds.