Thread: Probability that an event happens infinite times

1. Probability that an event happens infinite times

Lets flip a fair coin. If it's head, I get $1 and if its tail I loose$1. Let "k" be the number of trials when I choose to stop. Let S_k be the total sum (amount) till the "kth" trial (inclusive).

Assume given that the probability S_k = "n" (some positive integer) before S_k is "-m" (some negative integer) for the first time = m/(n+m).

Question: What is the probability that Sum, S_k shall hit every integer infinite number of times.
Hint: use borel-cantenelli lemma.

Here is my attempt-
Pr(S_k = n before S_k = -n) = 1/2.
Pr(S_k+1 = 0 before S_k+1 = -n = 1).
These are independent events. Hence, Pr(S_k = n and S_k+1 =0) = 1/2.
This would mean Pr(S_k hits number "n" infinite times) = 1/2*1*1/2*1...
However, using Borel Cantenelli Lemma, I can say that 1/2+1/2 +.. = 1+1+.. = infinity. Hence, Pr(Sum hits "n" infinite times) = 1.
Since, we chose "n" arbitrary, the Pr that sum hits every integer infinitely often is = 1*1*.. = 1.

2. Hello,

what does this "before" mean ? o.O

Also, it's Borel-Cantelli lemma... It may be useful to know the correct name if you need some reference

3. BC lemma- made that typo but no that does help much.

As far as "before" is concerned - you missed it?
Well, it means that optional sampling theorem was used to obtain the probabilities, which are given in the question. It might help to google on the optional sampling theorem for your own edification.

Originally Posted by Moo
Hello,

what does this "before" mean ? o.O

Also, it's Borel-Cantelli lemma... It may be useful to know the correct name if you need some reference

4. Originally Posted by zigzag20
Lets flip a fair coin. If it's head, I get $1 and if its tail I loose$1. Let "k" be the number of trials when I choose to stop. Let S_k be the total sum (amount) till the "kth" trial (inclusive).

Assume given that the probability S_k = "n" (some positive integer) before S_k is "-m" (some negative integer) for the first time = m/(n+m).

Question: What is the probability that Sum, S_k shall hit every integer infinite number of times.
Hint: use borel-cantenelli lemma.

Here is my attempt-
Pr(S_k = n before S_k = -n) = 1/2.
Pr(S_k+1 = 0 before S_k+1 = -n = 1).
These are independent events. Hence, Pr(S_k = n and S_k+1 =0) = 1/2.
This would mean Pr(S_k hits number "n" infinite times) = 1/2*1*1/2*1...
However, using Borel Cantenelli Lemma, I can say that 1/2+1/2 +.. = 1+1+.. = infinity. Hence, Pr(Sum hits "n" infinite times) = 1.
Since, we chose "n" arbitrary, the Pr that sum hits every integer infinitely often is = 1*1*.. = 1.

Considering the way you stated the problem and your computation, Moo's question wasn't a bad one at all. Do you understand what you mean by "Pr(S_k+1 = 0 before S_k+1 = -n) = 1" and "Pr(S_k = n and S_k+1 =0) = 1/2"? What is k? Is it fixed, is it any integer, is it a random time?... And how is it possible that S_k and S_k+1 differ by more than 1? Where does the independence come from? I don't mean to be rude, I would just like to stress the fact that your proof, written as such, is almost impossible to follow and seems quite dubious. If you could try to explain it in a few words, that may help a lot. Both us and you.

To Moo: For any $k\geq 0$, $S_k$ is the amount won at time $k$. As far as I can guess from the following of the post, we start with $S_0=0$. The given property answers the famous Gambler's ruin problem with a fair coin: if you play until you go broke (which eventually happens), what is the probability that, at some time, you have had \$1m?
In terms of the sequence $(S_k)_{k\geq 0}$, this amounts to considering the probability that this random sequence (starting at 0) will exit the set $\{-m+1,\ldots,0,\ldots,n-1\}$ into $n$. If we define the (possibly infinite) hitting times $T_x$ for any $x\in\mathbb{Z}$, then this can be written $P(T_n, and it equals $\frac{m}{m+n}$ for a fair coin. You can use the optional sampling theorem to prove that, but there's a much more elementary way: consider more generally $f(x)=P_x(T_n where $x\in\{-m,\ldots,n\}$ stands for the starting point $S_0$ (which was 0 before). Then $f(n)=1$, $f(-m)=0$ and you have $f(x)=\frac{1}{2}f(x+1)+\frac{1}{2}f(x-1)$ (by decomposing according to the first step), so that $f$ is seen to be linear. This gives the value of $f(0)$.

--
A hint: In order to apply Borel-Cantelli (the way you need it), you must have independent events. For that task, the strong Markov property will come in handy. Indeed, you'll need to decompose the trajectory $(S_k)_{k\geq 0}$ using appropriately chosen stopping times, and say that what happens between these stopping times is independent.

Of course I won't give you a proof right now, but you might find interesting to use the sequences $\pm 2^i,\ i\geq 0,$ in place of the $n$ and $m$ in your property.

5. Originally Posted by zigzag20
Question: What is the probability that Sum, S_k shall hit every integer infinite number of times.
There is also a very nice proof using Kolmogorov's 0-1 law, if you know this property.

6. Originally Posted by Laurent
There is also a very nice proof using Kolmogorov's 0-1 law, if you know this property.
So you read the hint about Borel Cantelli lemma? Isn't that commonly the "touchstone" for the the 0-1 Komogorov law and yes I know that property. I don't intend to be rude, but you start giving lectures without reading the question properly. As far as my proof was concerned, if I was confident about it, I would have not posted it. And "moo"s confusion was not about K+1th event but about the spelling in BC lemma. Apparently, that is the only thing he could even point out. Quite immature, if you ask me.

7. Originally Posted by Laurent
Considering the way you stated the problem and your computation, Moo's question wasn't a bad one at all. Do you understand what you mean by "Pr(S_k+1 = 0 before S_k+1 = -n) = 1" and "Pr(S_k = n and S_k+1 =0) = 1/2"? What is k? Is it fixed, is it any integer, is it a random time?... And how is it possible that S_k and S_k+1 differ by more than 1? Where does the independence come from? I don't mean to be rude, I would just like to stress the fact that your proof, written as such, is almost impossible to follow and seems quite dubious. If you could try to explain it in a few words, that may help a lot. Both us and you.
As much as I appreciated your response, I would like to ask you one thing. If your confusion or as you say moo's confusion is about my problem, then why are you commenting my solution? You just wanted to critique something without much relevance to what moo had posted.

8. I solved the problem.

Close this thread or whatever it takes to mention that I have solved the problem myself.

9. Originally Posted by zigzag20
Close this thread or whatever it takes to mention that I have solved the problem myself.