5
$\begingroup$

Do you know of any real world (algorithm, physics, ...) application of the law of large numbers where we need the strong LLN and the weak LLN by itself is not enough to prove that the application is working as expected ?

$\endgroup$
  • $\begingroup$ There are algorithms that provably halt with probability 1 using SLLN but cannot be proven to halt with any positive probability using WLLN. Is that the type of application you're asking for? $\endgroup$ – Brian Moehring Jun 2 at 18:57
  • $\begingroup$ Yes, if there is a "real life" use case for the algorithm $\endgroup$ – Weier Jun 2 at 20:53
  • 1
    $\begingroup$ Suppose we take a random walk starting at point $S_0>0$. Suppose there is a cliff at $0$. Let $\{X_i\}_{i=1}^{\infty}$ be the sequence of (positive or negative) step sizes (independent of $S_0$) and so $S_n=S_0+\sum_{i=1}^n X_i$ is the location after $n$ steps. If $\frac{1}{n}\sum_{i=1}^n X_i\rightarrow 1$ with prob 1, then the probability of ever falling of the cliff goes to zero as $S_0$ is increased. But there are processes $\{X_i\}_{i=1}^{\infty}$ such that $\frac{1}{n}\sum_{i=1}^n X_i\rightarrow 1$ in probability, yet we fall off the cliff with prob 1, regardless of where we start. $\endgroup$ – Michael Jun 3 at 5:55
  • $\begingroup$ @Michael I'm not sure it qualifies as a "real world application" (that's more of an intuitive way to understand a theoretical counter-example). $\endgroup$ – Weier Jun 3 at 18:30
  • 2
    $\begingroup$ @Michael could you give an example for "But there are processes..."? Maybe in a full answer? I think your description above is very much a suitable answer, as it can be seen as a general mathematical background for a real-world problem, so it should be acceptable as an answer in this community. I encourage you to write one! $\endgroup$ – black Jun 18 at 8:40
1
$\begingroup$

This gives details on my comment about systems with random walks and thresholds that we do not want to cross. It shows that if the average stepsize converges to 1 with probability 1, then we can start far enough to the right of the threshold to ensure the probability of ever crossing it is as small as we like. But if the average stepsize converges to 1 in probability (but not with probability 1) there are examples where we (unfortunately) cannot avoid crossing the threshold, no matter how far away from it we start.


Fix $x >0$ as a non-random starting location for the random walk. Let $\{X_i\}_{i=1}^{\infty}$ be a sequence of random variables that represent step sizes. The $\{X_i\}$ variables are possibly dependent and can have different distributions. Define $S_n$ as the location on step $n$:
$$ S_n = x + \sum_{i=1}^n X_i \quad \forall n \in \{1, 2, 3, ...\} $$ Let $C_{x}$ be the event that we eventually cross the 0 threshold, assuming starting location $x$:
$$ C_{x} = \cup_{n=1}^{\infty} \left\{x +\sum_{i=1}^n X_i \leq 0\right\}$$

Claim 1:

If $\lim_{n\rightarrow\infty} \frac{1}{n}\sum_{i=1}^n X_i =1$ with probability 1, then $\lim_{x\rightarrow\infty} P[C_x] = 0$.

Proof: Define $M = \inf_{n\in \{1, 2, 3, ...\}}\left\{\sum_{i=1}^n X_i \right\}$. Then $M\leq X_1$ and it can be shown that $P[M=-\infty]=0$ and $M$ has a valid CDF function $P[M\leq y]$ for all $y \in \mathbb{R}$. For $x \in \mathbb{R}$ we have $$ C_x = \cup_{n=1}^{\infty}\left\{x + \sum_{i=1}^n X_i \leq 0\right\} \subseteq \{x + M \leq 0\} $$ Thus $$P[C_x] \leq P[x+M\leq 0] = P[M\leq -x] $$ Hence $$ \lim_{x\rightarrow\infty} P[C_x] \leq \lim_{x\rightarrow\infty} P[M\leq -x] = 0 \quad \Box$$

Claim 2:

There are processes $\{X_i\}_{i=1}^{\infty}$ that satisfy $\frac{1}{n}\sum_{i=1}^n X_i \rightarrow 1$ in probability (but not with probability 1) such that $P[C_x]=1$ for all $x>0$.

We construct such a process: Define $\{Y_n\}_{n=1}^{\infty}$ as independent random variables that satisfy $$ Y_n = \left\{\begin{array}{ll} 1 &\mbox{with prob $(1-1/n)$}\\ -n & \mbox{with prob $1/n$} \end{array}\right.$$ Then $Y_n\rightarrow 1$ in probability (but not with probability 1) and by Borel-Cantelli we have $Y_n=-n$ infinitely often. Define $\{X_i\}_{i=1}^{\infty}$ as follows: Define $X_1=Y_1$ and $$ X_n = nY_n - (n-1)Y_{n-1} \quad \forall n \in \{2, 3, 4, ...\}$$ It follows that $$ \frac{1}{n}\sum_{i=1}^n X_i = Y_n \quad \forall n \in \{1, 2, 3, ...\}$$ Thus, $\frac{1}{n}\sum_{i=1}^n X_i \rightarrow 1$ in probability (but not with probability 1).

Fix $x>0$. Notice that if $Y_n=-n$ for some particular positive integer $n$, then $x + \sum_{i=1}^n X_i = x-n^2$. If $Y_n=-n$ for infinitely many positive integers $n$, then $x + \sum_{i=1}^n X_i \leq 0$ for infinitely many $n$. But we already know $\{Y_n=-n\}$ occurs infinitely often with probability 1. Thus $P[C_x]=1$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Also, to fully answer the question maybe you could name a real world application using that kind of probabilistic modelling. $\endgroup$ – Weier Jun 19 at 15:37
  • 1
    $\begingroup$ @Weier : Say, we have a gambling strategy and we go broke if our total money goes to zero. Or perhaps the threshold represents a debt where, if crossed, a real-world goon comes out and breaks our leg. $\endgroup$ – Michael Jun 26 at 21:47

Not the answer you're looking for? Browse other questions tagged or ask your own question.