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.
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.
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.