# Limit superior proof

• Jul 26th 2012, 11:27 PM
entropyslave
Limit superior proof
Hi there,

I'm working through a basic proof in a probability theory book, and I'm stuck trying to work out whether one of the statements is a typo, or I'm missing something:

$A_k$ is an arbitrary indexed set

If
$\omega\in\limsup_{n\rightarrow\infty}=\bigcap_{n=1 }^{\infty}\bigcup_{k=n}^{\infty}A_k$
then since for every $n$, $\omega\in\cup_{k\ge{n}}A_k$, for all $n$ there exists some $k_n\ge{n}$ such that $\omega\in{A_k}_n$ and therefore
$\sum_{j=1}^{\infty}1_A_{j}(\omega)\ge\sum_{n}{1_{{ A_k}_n}}(\omega)=\infty$

And at this point I'm confused: it seems to be that by construction, the indicator function in the second sum should always return 1, but the first does not necessarily. Therefore while they are both infinite sums, the first one may be smaller than the second, not the other way around.
• Jul 27th 2012, 12:58 AM
girdav
Re: Limit superior proof
$\omega\in \limsup A_k$ means that the set $\{k\in\Bbb N, \omega\in A_k\}$ is infinite. For example, if $A_{2k}=\{0\}$ and $A_{2k+1}=\{1\}$ then $0\in\limsup_kA_k$. The last two sums are both infinite.
• Jul 27th 2012, 03:07 AM
entropyslave
Re: Limit superior proof

So I don't think my question was clear enough. I absolutely understand that both sums are infinite. However I don't agree with the direction of the inequality between them: if I've understood the construction, the indicator of the second sum should always equal 1, whereas the first sum's indicator, whilst having an infinite number of 1's, can also return zeros. Is my understanding correct and therefore, this aspect of the proof wrong?
• Jul 27th 2012, 03:46 AM
girdav
Re: Limit superior proof
In the sum of the RHS, only the term of index $k_n$, whereas in the RHS, we sum all the terms. Since they are non-negative, we have this inequality.
• Jul 27th 2012, 04:12 AM
entropyslave
Re: Limit superior proof
I'm still not quite sure I understand.

I read the sum on the RHS to mean a sum over all $n$ - since we've stated there exists a ${k_n}\ge{n}$ for every $n$. Thus both sums are over the same domain (i.e. all positive integers).

Moreover, the actual ${k_n}$ index could very well be the same for multiple terms of the (RHS) sum - whatever it takes to ensure that $\omega\in{{A_k}_n}$ for all $n$.

Thus the RHS indicator always returns ones, the LHS may or may not, but since they're over the same domain, the LHS is smaller.

Sorry if I'm being dumb on this - if I've misunderstood the notation, could you point to the specific thing I've misread?

Thanks
• Jul 27th 2012, 07:47 AM
girdav
Re: Limit superior proof
Let $I:=\{k, \omega\in A_k\}\subset \Bbb N$. Then the inequality is $\sum_{k\in \Bbb N}1_{A_k}(\omega)\geq \sum_{k\in I}1_{A_k}(\omega)$.
• Jul 30th 2012, 01:18 AM
entropyslave
Re: Limit superior proof
Hi, sorry I still understand how your explanation resolves this:

Quote:

Originally Posted by girdav
Let $I:=\{k, \omega\in A_k\}\subset \Bbb N$. Then the inequality is $\sum_{k\in \Bbb N}1_{A_k}(\omega)\geq \sum_{k\in I}1_{A_k}(\omega)$.

1. I don't see how $\sum_{n}{1_{{A_k}_n}}(\omega)$ equates to your RHS sum. Doesn't $\sum_{n}$ mean sum over all $n$?
2. Even if my sum is the same as your RHS sum, to me your sum very clearly seems to be an equality: both indicators return an exactly equal number of 1's.
• Jul 30th 2012, 04:04 AM
emakarov
Re: Limit superior proof
Quote:

Originally Posted by entropyslave
Moreover, the actual ${k_n}$ index could very well be the same for multiple terms of the (RHS) sum - whatever it takes to ensure that $\omega\in{{A_k}_n}$ for all $n$.

I agree with the OP because of this fact. Unlike $\sum_{j=1}^{\infty}1_{A_{j}}(\omega)$, the right-hand side $\sum_{n=1}^\infty{1_{ A_{k_n}}}(\omega)$ may contain $1_{A_n}(\omega)$ several times for some values of n. For example, if $\omega\in A_n$ iff $n\equiv0\pmod{3}$, we could take $k_n=3\lceil n/3\rceil$. Then the right-hand side is $1_{A_3}(\omega)+1_{A_3}(\omega)+ 1_{A_3}(\omega)+1_{A_6}(\omega)+ 1_{A_6}(\omega)+1_{A_6}(\omega)+\dots$. Because of this repetition, we can't say that the sequence $k_1$, $k_2$, ... is a subsequence of 1, 2, ...

The comparison would be correct if we defined $k_n$ to be some index such that $\omega\in A_{k_n}$ and $k_n>k_1$, ..., $k_n>k_{n-1}$. Then $k_1$, $k_2$, ... is a subsequence of 1, 2, ..., so $\sum_{j=1}^{\infty}1_{A_{j}}(\omega)\ge\sum_{n=1}^ \infty{1_{A_{k_n}}(\omega)$.

Edit: Changed $k_n=\lceil n/3\rceil$ to $k_n=3\lceil n/3\rceil$.
• Jul 30th 2012, 08:34 AM
entropyslave
Re: Limit superior proof
Quote:

Originally Posted by emakarov
The comparison would be correct if we defined $k_n$ to be some index such that $\omega\in A_{k_n}$ and $k_n>k_1$, ..., $k_n>k_{n-1}$. Then $k_1$, $k_2$, ... is a subsequence of 1, 2, ..., so $\sum_{j=1}^{\infty}1_{A_{j}}(\omega)\ge\sum_{n=1}^ \infty{1_{A_{k_n}}(\omega)$.

Thanks for your message and good example.

As an aside, could you help me understand why your correction example (above) is not simply always an equality? As far as I see it, you've defined the subsequence of $k_n$ to be exactly the indexes that the indicator in the left sum returns 1, and excluded the indices that the left indicator return zero. Thus, (I think) your two sums are equal.
• Jul 30th 2012, 08:58 AM
emakarov
Re: Limit superior proof
Quote:

Originally Posted by entropyslave
As an aside, could you help me understand why your correction example (above) is not simply always an equality? As far as I see it, you've defined the subsequence of $k_n$ to be exactly the indexes that the indicator in the left sum returns 1, and excluded the indices that the left indicator return zero. Thus, (I think) your two sums are equal.

In post #8, $k_n$ is defined simply as some index such that $\omega\in A_{k_n}$ and $k_n$ is greater than all previous $k_j$'s. The sequence $k_n$ doesn't have to cover all indices j such that $\omega\in A_j$. In the situation where $\omega\in A_n$ iff $n\equiv0\pmod{3}$, we can define $k_1 = 30$, $k_2 = 60$, etc.

By the way, I made a mistake defining $k_n=\lceil n/3\rceil$; it should be $3\lceil n/3\rceil$. Then $k_1=k_2=k_3=3$; $k_4=k_5=k_6=6$, etc.
• Jul 30th 2012, 09:11 AM
entropyslave
Re: Limit superior proof
Wonderful, I get it now, thanks. So if you added that $k_1$ was the lowest index, and each $k_n$ was the next highest with $\omega\in{A_k}_n$ we should have equality.

And well spotted, I had indeed missed that mistake.