3
$\begingroup$

I have what seems like a simple question, but I am not quite able to prove it. Suppose that $A_n$ is a sequence of random variables, and we know that $A_n$ strongly converges to zero; i.e. almost surely. I am aware that this implies that $A_n$ converges in probability to $0$, but I am wondering about the rate of convergence.

Suppose that I wish to establish that $A_n = \mathcal O_P(f(n))$, where $f(n)$ is some positive, strictly monotonically decreasing function which decays to zero at some rate. My understanding is that strong convergence implies that for any $\epsilon$ there are finitely many $n$ such that $A_n > \epsilon$. But does this condition imply that there is some constant $C_f$, potentially quite large!, such that for $n>>0$, $$\Pr\left(A_n > C_f f(n)\right) \to 0 ?$$

$\endgroup$
  • $\begingroup$ I want to understand, generally, how one can get a "fast" rate of convergence in probability merely from knowing that we have almost-sure convergence. I have stated the "conjecture" that given any decaying function $f$, for $n$ large enough there is some constant such that $P(|A_n| > Cf(n))\to 0$. If this is not true for all $f$, but merely some class of decaying functions, I would love to know about this! In my particular application, not discussed in this question, $f$ is a certain function of $n$. $\endgroup$ – Lepidopterist Mar 21 '18 at 18:14
2
+100
$\begingroup$

Expanding on @saz's comment about the rate of decay, for any function $f(n)$ that you pick, I can find a function $g(n)$ which still decays to $0$, but which does so at a much slower rate. In other words, we want $g(n) >> Cf(n)$ for any constant $C$ and large enough $n$, or, equivalently, $\lim_{n \to \infty} \frac{g(n)}{f(n)} = \infty$. Using this $g(n)$, I can construct a specific counterexample as follows.

Let $\Omega$ be a probability space with only one outcome, $\omega$ (for instance, flipping a trick coin that always comes up heads). Then, let $A_n(\omega) = g(n)$ for all $n$. Saying that $A_n$ converges to $0$ almost surely in this simple probability space is the same as saying that $g(n) \to 0$, which it does. However, $\mathrm{Pr}(A_n > Cf(n))$ is equal to $1$ for an infinite number of $n$, no matter what $C$ is, so $\mathrm{Pr}(A_n > Cf(n)) \not\to 0$.

$\endgroup$
1
$\begingroup$

Given a sequence $(A_n)_{n \in \mathbb{N}}$ converging almost surely to $0$, it is possible to prove the existence of a function $f$ with the desired properties (see below), but without further information on the distribution of the random variables (e.g. tail/moment estimates) we cannot expect to pin down the rate of decay of the function $f$.

Existence of $f$: Since $A_n \to 0$ almost surely, we have, in particular,

$$\mathbb{P} \left( |A_n|> \frac{1}{k} \right) \xrightarrow[]{n \to \infty} 0$$

for any $k \in \mathbb{N}$, and therefore we can choose $n_k \in \mathbb{N}$ such that

$$\mathbb{P} \left( |A_n| > \frac{1}{k} \right) \leq \frac{1}{k} \quad \text{for all $n \geq n_k$.} \tag{1}$$

Without loss of generality we may assume that $0=n_1 < n_2 < \ldots$. If we define

$$f(n) := \frac{1}{k} \qquad \text{for $n \in [n_k,n_{k+1})$, $k \in \mathbb{N}$}$$

then $f>0$ is monotonically decreasing and, by $(1)$,

$$\mathbb{P}(|A_n|>f(n)) \xrightarrow[]{n \to \infty} 0.$$

Remarks:

  • Clearly, $f$ is, in general, not stricly monotone, but you can easily modify the construction to obtain a strictly monone function (e.g. $\tilde{f}(n) := f(n) + 1/n$ does the job).
  • It suffices to have $A_n \to 0$ in probability (the almost sure convergence is not needed for the proof).
$\endgroup$
  • $\begingroup$ I'm aware of the existence of an $f$; i.e. I'm aware that almost sure convergence implies convergence in probability. I'm most interested in the first part of what you wrote. You say what I want is not possible. Do you know a counterexample? Or even better, do you know a characterization of the moment estimates that when combined with almost-sure convergence produce "good" tail bounds? I have access to results showing almost sure convergence of something. How can I make use of those to get rates of convergence in probability? $\endgroup$ – Lepidopterist Mar 21 '18 at 21:46
  • $\begingroup$ @Lepidopterist The sequence can converge arbitrarly slowly to $0$. That is, for any given function $f$ one can easily find a sequence $A_n \to 0$ (almost surely) such that $A_n = O(f(n))$ does not hold. That's what I mean by "we can't expect to determine the rate of decay without further information on $A_n$". For instance if you know how fast the second moments of $A_n$ are decaying, then this gives you (by Markov's inequality) a rate of decay for $f$. $\endgroup$ – saz Mar 22 '18 at 7:39
  • $\begingroup$ I think that you should clarify what exactly you are interested in; you might also consider stating the problem you are actually interested in. $\endgroup$ – saz Mar 22 '18 at 7:40
-1
$\begingroup$

My understanding is that strong convergence implies that for any $\epsilon$ there are finitely many $n$ such that $A_n>\epsilon$.

This is quite simply called convergence, assuming $A_n>0$. Unconditional convergence, if you will. Strong convergence does not necessarily imply unconditional convergence.

"Strong convergence," i.e., convergence with probability one, only implies that "almost surely," i.e., with probability one, there are no more than finitely many $n$ such that $|A_n|>\epsilon$.

Nor is "strong convergence" necessary to establish convergence in probability of the order of magnitude a particular function $f$.


If $A_n = \mathcal O_P(f(n))$, where $f(n)>0,f(n)\longrightarrow 0$, then by definition [Big O in probability notation], there is a constant $C_f>0$, and for every $\epsilon>0$ there exists $N>0$ such that for all $n>N$,

$$ \mathrm{Pr}(|A_n|>C_ff(n)) < \epsilon$$

Moreover, for every such $\epsilon$, there is a least such $N$, which increases monotonically as $\epsilon\longrightarrow 0, \epsilon>0$. Conversely for each such $N$, there is a least such $\epsilon$, which is exactly

$$ \sup_{n>N}\mathrm{Pr}(|A_n|>C_ff(n)) $$

This expression must converge to zero as $N\longrightarrow\infty$, so the answer to your last question is yes.

$\endgroup$
  • $\begingroup$ Note that the OP doesn't assume that $A_n = O(f(n))$; he wants to establish it. $\endgroup$ – saz Mar 22 '18 at 7:41
  • $\begingroup$ Question was edited. It is no longer clear what OP is asking. hackernoon.com/the-decline-of-stack-overflow-7cb69faa575d $\endgroup$ – Justina Colmena Mar 22 '18 at 15:17
  • $\begingroup$ I don't understand what you mean. Yes, the question has been edited, but it's still asking for the same thing. $\endgroup$ – saz Mar 22 '18 at 15:35
  • $\begingroup$ @saz I have reached the firm conclusion that the opportunity for civil discussion on this site -- or for that matter any stackexchange site -- is long past. $\endgroup$ – Justina Colmena Mar 23 '18 at 18:12
  • $\begingroup$ How is @saz 's comment uncivil? He simply points out you are presuming the question as the premise. $\endgroup$ – Hans Mar 27 '18 at 7:57

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.