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
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.
Comments?
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.
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 , is the amount won at time . As far as I can guess from the following of the post, we start with . 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 , this amounts to considering the probability that this random sequence (starting at 0) will exit the set into . If we define the (possibly infinite) hitting times for any , then this can be written , and it equals 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 where stands for the starting point (which was 0 before). Then , and you have (by decomposing according to the first step), so that is seen to be linear. This gives the value of .
--
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 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 in place of the and in your 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.