# The limit of random variable is not defined

Tags:
1. Nov 16, 2015

### Mike.B

Let $X_i$ are i.i.d. and take -1 and +1 with probability 1/2 each. How to prove $\lim_{n\rightarrow\infty}{\sum_{i=1}^{n}{X_i} }$does not exsits (even infinite limit) almost surely.
My work:
I use cauchy sequence to prove it does not converge to a real number.
But I do not how to prove it does not converge to infinity. Can some one give hints?

Last edited: Nov 16, 2015
2. Nov 16, 2015

### andrewkirk

Denote $\sum_{k=1}^j X_k$ by $S_j$

Then If the sum $S_j$ converges in probability to infinity then
$$\forall M>0\ \forall \epsilon>0:\ \exists N>0 \textrm{ such that } j\geq N\Rightarrow Pr(S_j>M)>1-\epsilon\ \ \ \ \ (1)$$

For this not to be the case we negate the previous line to obtain:

$$\exists M>0\ \exists \epsilon>0:\ \forall N>0: \exists j\geq N\Rightarrow Pr(S_j>M)<1-\epsilon\ \ \ \ \ (2)$$

That's what has to be proved. One way to do that (not necessarily the quickest) is to use the central limit theorem. Note that $S_j=2B_j-j$ where $B_j$ is binomial with parameters $j,0.5$, which has mean $\frac{j}{2}$ and variance $\frac{j}{4}$. The Central Limit Theorem tells us that $B_j$ converges in probability to a random variable with distribution $N(\frac{j}{2},\frac{j}{4})$, so that $S_j$ converges in probability to a RV $Z_j$ with distn $N(0,j)$.

It's easy enough to prove that the sequence of RVs $(Z_j)_{j=1}^\infty$ satisfies (2). You then just need to put that together with the convergence in probability of $S_j$ to $Z_j$ to get the required result.

Last edited: Nov 16, 2015
3. Nov 16, 2015

### Mike.B

$\sum_{j=1}^n X_j$ by $S_j$?

4. Nov 16, 2015

### andrewkirk

Make that $S_n$. I'll correct it above.

5. Nov 16, 2015

### Mike.B

What is the relation between almost surely and in probability? How to use here?

Last edited: Nov 16, 2015
6. Nov 17, 2015

### andrewkirk

That's correct. Almost surely is a stronger type of convergence than in probability.

7. Nov 17, 2015

### Mike.B

I have difficulty about combining the final results, is there any inequality involved?

Last edited: Nov 17, 2015
8. Nov 17, 2015

### Mike.B

I got you about (2) [<1/2]

9. Nov 17, 2015

### andrewkirk

Hmm. On reflection, making the connection from the convergence in distribution to a normal, to a conclusion that the set of points $\omega\in\Omega$ for which $\lim_{j\to\infty}S_j(\omega)=\infty$ has zero measure is not as straightforward as I initially thought. I will think more about it when I get a decent slab of free time.

10. Nov 18, 2015

### WWGD

Isn't this a random walk based, say at 0 , in the Real line? I don't know how to describe convergence in a random walk.

11. Nov 18, 2015

### andrewkirk

Yes. That's how I've been thinking about it.

The formal statement of the problem, as I understand it, is a request to prove that $$Pr(\lim_{j\to\infty} S_j=\infty)=0$$

where we interpret $\lim_{j\to\infty}S_j=\infty$ to mean that $\forall M\in\mathbb{N}\ \exists n\in\mathbb{N}\$ such that $j>n\Rightarrow S_j>M$. All the instances of $S_j$ in that statement should really be written $S_j(\omega)$ where $\omega$ is an element of the sample space $\Omega$ of infinite sequences, in order to clarify that the statements are about specific sequences $(S_j(\omega))_{j\in\mathbb{N}}$rather than about the random variables $S_j$.

If we label by $A$ the set of all sequences/walks $S_j$ that have that property, which we call 'diverging to infinity' then we are trying to prove that $Pr(A)=0$.

I'm starting to think that my Normal Approximation suggestion won't help though.

Another possible avenue of attack would be if we could show that $A$is countable. Then we would know it must have measure zero, since the set $\Omega$ of all sequences is uncountable. We can also think about the sequences as binary expansions of real numbers in [0,1] and I'm wondering if any known results about the measure of subsets of that interval might help,

12. Nov 19, 2015

### Samy_A

13. Nov 19, 2015

### Mike.B

14. Nov 19, 2015

### Samy_A

Yes, that's what I meant. Could that work, as $(V=\infty) \cap A =\emptyset$ (I think)?

15. Nov 19, 2015

### Mike.B

Define $B=\{\omega\in \Omega:V(\omega)=\infty\}$? And show $A\cap B$=0\$?

16. Nov 19, 2015

### Samy_A

If $\omega\in A$ then $\forall M\in\mathbb{N}\ \exists n\in\mathbb{N}\$ such that $\forall j>n\Rightarrow S_j(\omega)>M$.
Take $M>0$. Doesn't that imply that $\omega$ can return to 0 at most $n$ times, so $\omega \not\in B$?

Last edited: Nov 19, 2015
17. Nov 19, 2015

### Mike.B

I think You are right!

18. Nov 19, 2015

### WWGD

Isn't it also possible to use a recursion in this case , whose solution gives a closed form for the general probability?

19. Nov 19, 2015

### Mike.B

What do you mean by "recursion"?

20. Nov 19, 2015

### WWGD

21. Nov 19, 2015

### Mike.B

Can you tell me more?

22. Nov 19, 2015

### WWGD

Sure, give me some time and I will be back a bit later with more on it.

23. Nov 20, 2015

### WWGD

Consider the recursion $P(n,x) =[P(n-1,x-1)+P(n-1, x+1)]/2 , P(0,0)=1 , P(0,x)=0 ; x \neq 0$ , where $n$ is the step number in the walk and $P(n,x)$ is the probability of being at $x$ at step $n$ on the Real line at step $n$, and $x$ is any Natural number.

Last edited: Nov 20, 2015
24. Nov 20, 2015

### andrewkirk

I tried the link given in post 12 but it was full of broken latex links and hence unusable on the computer I'm at now.
However I found the following http://www.dartmouth.edu/~chance/teaching_aids/books_articles/probability_book/Chapter12.pdf
It proves a number of results, and in Exercise 12.1 on page 6 it proves that $w_*=1$ where
$$w_*\equiv \lim_{n\to\infty} w_n$$
and $w_n$ is the probability that the random walk has returned to the origin no later than step $n$.

We can then proceed as follows
[Edit: I discovered subsequently that this argument is flawed. See post 26 below for corrected version]

$A\subseteq B$ where $B$ is the set of paths that do not return to the origin infinitely often.

$B\subseteq J_n$ where $J_n$ is the set of paths that do not return to the origin in the first $n$ steps. Note that $Pr(J_n)=1-w_n$.

Hence
$$Pr(A)\leq Pr(B)\leq \inf\{Pr(J_n)\ |\ n\in\mathbb{N}\}\leq \inf\{1-w_n\ |\ n\in\mathbb{N}\}=1-\sup\{w_n\ |\ n\in\mathbb{N}\}=1-w_*=0$$

The proof in the link that $w_*=1$ is far from trivial though, involving a generating function and requiring a proof of an interim result, at the bottom of p4 (attributed to Wilf), which is set as an exercise for the reader in Exercise 1. I have not done that exercise.

Last edited: Nov 21, 2015
25. Nov 21, 2015

### Samy_A

I don't understand this step: how do you know that $B\subseteq J_n$?