limsup and liminf for a sequence of sets - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T14:32:58Z http://mathoverflow.net/feeds/question/12462 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/12462/limsup-and-liminf-for-a-sequence-of-sets limsup and liminf for a sequence of sets cappadonza 2010-01-20T23:10:04Z 2010-02-13T22:11:32Z <p>how does limsup and liminf for a sequence of sets, apply to probability theory. any real world examples would be much appreciated</p> http://mathoverflow.net/questions/12462/limsup-and-liminf-for-a-sequence-of-sets/12465#12465 Answer by Johannes Hahn for limsup and liminf for a sequence of sets Johannes Hahn 2010-01-20T23:36:08Z 2010-02-13T21:21:45Z <p>What about something like $A_1\subseteq A_2\subseteq A_3\subseteq\ldots \implies \limsup A_n=\liminf A_n=\bigcup\limits_n A_n$ ?</p> <p>If these sets are measurable sets in a (finite) measure space $(\mathcal{A},\mu)$, then $\liminf\limits_{m\to\infty} \mu(A_m) \geq \mu(\liminf A_m)$ (and $\limsup\limits_{m\to\infty} \mu(A_m) \leq \mu(\limsup A_m)$). Is that "application" enough?</p> <p>EDIT: The <a href="http://en.wikipedia.org/wiki/Borel-Cantelli%5Flemma" rel="nofollow">Borelâ€“Cantelli lemma</a> is another application.</p> http://mathoverflow.net/questions/12462/limsup-and-liminf-for-a-sequence-of-sets/12485#12485 Answer by Matus Telgarsky for limsup and liminf for a sequence of sets Matus Telgarsky 2010-01-21T02:27:07Z 2010-01-21T02:34:12Z <p>As Johannes stated, the Borel-Cantelli lemmas (there are two) are the primary way in which these quantities (referred to as "infinitely often" and "almost always") appear.</p> <p>The most common use is to prove things about limits of random variables. To see why this is the case, suppose you can show that, for any $\epsilon > 0$, $$P([|X_n| > \epsilon]\textrm{ i.o.}) = 0.$$ (To show this with the first Borel-Cantelli lemma, you would establish $\sum_n P([|X_n| > \epsilon]) &lt; \infty$.) From here, it follows that $P([\lim X_n = 0]) = 1$, because $$P([\lim X_n = 0]) = P(\cap_i \cup_N \cap_{n\geq N} [|X_n| > 1/i]) =: P(A)$$ by definition of limit, but $$P(A^c) =1-P(\cup_i \cap_N \cup_{n\geq N} [|X_n| \leq 1/i]) \geq 1- \sum_i P([|X_n| > \epsilon]\textrm{ i.o.}) = 1,$$ where the union bound (subadditivity) and definition of infinitely often were employed. Note that i worked out a bunch of symbols to make sure the math was correct, but you can see it in words: if, for every $\epsilon >0$, you have the property that probability of infinitely many of your random variables exceeding $\epsilon$ is zero, then it is intuitive that the limit of this sequence is 0 with probability 1.</p> <p>To get a feel for more details (and the relationship to specific probabilistic quantities), maybe try using this technique to prove certain limiting properties of certain sequences of random variables (any probability textbook will have many, for instance the excellent book by Resnick).</p> <p>I'll also add that you can prove a weakened form of the SLLN (weakened means you need some extra assumptions on which moments are finite) using Chebyshev's inequality and the limiting technique above. As you can guess, Chebyshev allows you to say something of the form $\sum_n P([|X_n| > \epsilon) &lt; \infty$, where $X_n$ is something fancier as needed for the SLLN (a normalized sum).</p> http://mathoverflow.net/questions/12462/limsup-and-liminf-for-a-sequence-of-sets/12497#12497 Answer by has2 for limsup and liminf for a sequence of sets has2 2010-01-21T04:39:45Z 2010-01-21T06:03:06Z <p>For a sequence of subsets $A_n$ of a set $X$, the $\limsup A_n$ $= \cap_{N=1}^\infty ( \cup_{n\ge N} A_n )$ and $\liminf A_n$ $= \cup_{N=1}^\infty (\cap_{n \ge N} A_n)$.</p> <p>If $x \in \limsup A_n$ then $x$ is in all of the $\cup_{n\ge N} A_n$, which means no matter how large you pick $N$ you will find an $A_n$ with $n>N$ of which $x$ is a member. Thus members of $\limsup A_n$ are those elements of $X$ that are members of infinitely many of the $A_n$'s. If $A_n$ are thought of as events (in the sense of probability) $\limsup A_n$ will be another event. It corresponds exactly to the occurance of infinitely many of the $A_n$'s. This is why $\limsup A_n$ is sometimes written $x \in A_n$ infinitely often.</p> <p>Similarly, if $x\in \liminf A_n$ then $x$ is in one of $\cap_{n\ge N} A_n$, which means $x \in A_n$ for all $n > N$. Thus, for $x$ to be in the $\liminf$, it must be in all of the $A_n$, with finitely many exceptions. This is how the phrase "ultimately all of them" comes up.</p> <p>Both of these operations, similar to their counterparts in metric spaces, concern the tail of the sequence ${A_n}$. I.e., neither changes if an initial portion of the sequence is truncated. As a previous response pointed out, often the sets $A_n$ are defined to track the deviation of a sequence of random variables from a candidate limit by setting $A_n = \{x: |Y_n(x) -Y(x)| \ge \epsilon\}$. The members of $\limsup A_n$ then represents those sequences that every now and then deviate $\epsilon$ away from $Y(x)$, which is solely determined by the tail of the sequence $Y_n$.</p> <p>Here is a conceptual game that can be partially understood using these concepts: We have a deck of cards, on the face of each card an integer is printed; thus the cards are ${1,2,3...}.$ At the nth round of this game, the first $n^2$ cards are taken, they are shuffled. You pick one of them. If your pick is 1, you win that round. Let $A_n$ denote the event that you win the nth round. The complement $A_n^c$ of $A_n$ will represent that you lose the $n^{th}$ round. The event $\limsup A_n$ represents those scenarios in which you win infinitely many rounds. The complement of this event is $\liminf A_n^c$, and this represents those scenarios in which you ultimately lose all of the rounds. By the Borel Cantelli Lemma $P(\limsup A_n)$ $=0$ or equivalently $P(\liminf A_n^c)=1$. Thus, a player of this game will deterministically experience that there comes a time, after which he never wins.</p> http://mathoverflow.net/questions/12462/limsup-and-liminf-for-a-sequence-of-sets/15216#15216 Answer by Tom LaGatta for limsup and liminf for a sequence of sets Tom LaGatta 2010-02-13T22:11:32Z 2010-02-13T22:11:32Z <p>Here's another simple example, in a similar vein as has2's above. Let $X_n$ be a sequence of independent, identically-distributed exponential variables, i.e., $$\mathbb P(X_n > u) = e^{-\lambda u},$$ for some real $\lambda > 0$. Let $E_n$ be the event that $X_n > n$, and let $E = \limsup E_n$, that is, the event $E$ occurs if there's an infinite (random) subsequence $n_k$ such that $X_{n_k} > n_k$.</p> <p>We compute $$\sum \mathbb P(E_n) = \sum e^{-\lambda n} &lt; \infty,$$ thus by the Borel-Cantelli lemma, $E$ has probability zero. With probability one, there exists a (random) number $N$ such that for all $n \ge N$, $X_n \le n$.</p> <p>Let's analyze this graphically. Make a plot with the horizontal axis representing time $n$, and the vertical axis $x = X_n$. Draw the line $x = n$. For small times $n$, these random points might jump above the line $x = n$. But the argument above shows that there is some (random) time $N$ after which the points $X_n$ all lie below the line $x = n$.</p>