Hope this is not repetition. (To the best of my search, I couldn't relate it precisely to anything before .... though, some may be related).To start with X(0)=0Toss a fair coin. Heads: X(n+1)=X(n) +1, Tails: X(n+1)= X(n) -1 n=0,1,2,3..... (n refers to the number of the toss, in sequence)What is the probability that X(n) reaches 9, before reaching -3?

This was an exercise on my first year probability course as an undergraduate...

.10%?

1/4

QuoteOriginally posted by: zarnywhoopThis was an exercise on my first year probability course as an undergraduate...eh, you did doob's lemma as a freshman? which school did you go to?

gambler's ruin problem

dont need doob surely, just condition upon first move, formulate difference equation, etc...

well yeah but my post sounded better that way ... I think"you learned conditional probabilities in freshman year?" just doesn't have the same ring to it, no?

In retrospect, it was a sitter .... but I can't pretend I got the answer after few hours of getting into a nasty loop.I finally got it this way -> Prob of reaching 3, before reaching -3 = 0.5 (by symmetry)Given that you are at 3, Prob of reaching 9, before reaching -3 is also 0.5 (again, by symmetry).So, the multiplication gives, 0.5*0.5=0.25 (as given by Karafka).Looking up "Gambler's ruin problem" at mathworld (as shawnchu told), gave an easier formula: n1/(n1+n2) .... I need to read up Doob's lemma, though.---------------------------------------------------------------------------------------------The source of this was a simplified version of an interview question: What's the probability of a reaching 9, before -3 by a variable following GBM? Just that, I feel that I simplified it too much.Anyway, twisting the original easy question, let's introduce a drift on the discrete-process X in a particular directionSo, if Heads, X(n+1)=X(n)+1.5if Tails, X(n+1)=X(n)-0.5(i) Now what's the probability of reaching 9, before -3(ii) What's the expected value of N, which is no. of tosses after which the "game" ends (... consider this process a game!).(iii) And finally, the real interview question -> what's the probability if, the drift is a function of the current value of X i.e. if Heads, X(n+1) = X(n)*1.25 + 1 if Tails, X(n+1) = X(n)*1.25 -1Hope, this upgraded teaser doesn't turn out to a sitter, as well. (Atleast I can't calculate the answers offhand on these ... but will be elated, if get them before I see them posted here edit: needed to fix some values, above. I know even the upgraded teaser is different from the original interview problem (since, the random variable has binomial distribution ... not normal. But I think it shouldn't hurt the essence of what they wanted to know). I fancy, if we were to use a normally distributed continuous random variable, the answer would be interesting in context of knock-in / knock-out options.With that I start getting a feeling, it's hardly a teaser but direct application of theory ... (which I need to ready up !). If so, those looking for the tease can ignore this. (Sorry, you had to read this very long post )

QuoteOriginally posted by: hongyiQuoteOriginally posted by: zarnywhoopThis was an exercise on my first year probability course as an undergraduate...eh, you did doob's lemma as a freshman? which school did you go to?No, but we did gambler's ruin. Cambridge

For part (i)...f(x) = .5*f(x+1.5) + .5f(x-.5), f(-3)=0, f(9) = 1, f(0) = ?standard gambler's ruin stuff gives...y^x = .5*y^(x+1.5) + .5*y^(x-.5)y^.5 = .5*y^2 + .5...0= y^4 + 2*y^2 - 4*y + 1One real solution is 1, let a be the other one (equal to .2955977... irrational)f(x) = A*1^x + B*a^x = A + B*a^xf(-3) = 0 = A + B*a^-3f(9) = 1 = A + B*a^9...A = -1/(a^12 - 1), B = (a^3)/(a^12 - 1) =>f(x) = -1/(a^12 - 1) + (a^3)*(a^x)/(a^12 - 1) =>f(0) ~= .975 (plugging in for a)

QuoteOriginally posted by: kwsFor part (i)...f(x) = .5*f(x+1.5) + .5f(x-.5), f(-3)=0, f(9) = 1, f(0) = ?standard gambler's ruin stuff gives...y^x = .5*y^(x+1.5) + .5*y^(x-.5)y^.5 = .5*y^2 + .5...0= y^4 + 2*y^2 - 4*y + 1One real solution is 1, let a be the other one (equal to .2955977... irrational)f(x) = A*1^x + B*a^x = A + B*a^xf(-3) = 0 = A + B*a^-3f(9) = 1 = A + B*a^9...A = -1/(a^12 - 1), B = (a^3)/(a^12 - 1) =>f(x) = -1/(a^12 - 1) + (a^3)*(a^x)/(a^12 - 1) =>f(0) ~= .975 (plugging in for a)Having determined part (i), part (ii) can be determined easily by using optional stopping --E(X_tau) = E(drift)*E(tau) = (0.5*1.5 - 0.5*0.5)*E(tau)Also, E(X_tau) = 9*P(gain) - 3*P(ruin), where P(gain) = f(9) in kws's post.Equating the two gives the E(tau).I have no idea on how to solve the third part. The recurrence relation is easy to get, but I'm unable to solve it. I can see that a solution of the form y^x does not satisfy the recurrence, so am not even sure if it follows geometric motion.Bhutes, could you please give the problem in the form that you were asked. Considering the continuous version of part (iii), it seems that the process in question followsdS_t = 1.25*S_t*dt + sigma*dW_t, is this a correct interpretation?Thanks.

I overheard the question from someone ... and he later corrected it to: What's the probability of reaching 9, before -3 by a variable following BM (not GBM).That's all I have ... for the question asked.----------------------------------------------------------------------------My upgraded teaser ... actually went tangentially away from the interview question.(If I were sticking to just modifying the interview problem ... I shouldn't have bothered with the drift. BM has no drift. That said, processes with drift could be solved separately, if they interest someone). As for it being not geometric, I agree. I should made randomness, to be proportional to the current value of X (not the drift). I think then if could be called geometric. Do you agree?My current interpretation of the interview question is:dS_t = sigma*dW_t (Assumed drift=0)I think the probability of the above BM process reaching 9, before -3 is also 0.25 (I rely on the same symmetry argument to reach that answer .... which should hold since dW follows a symmetric distribution i.e. normal and there is no drift).If you want to solve a process with a drift, I would think, it should modeled like this:dS_t = 1.25*S_t*dt + S_t*sigma*dW_t (or even a zero-drift i.e. GBM: dS_t = S_t*sigma*dW_t )The part(iii) below doesn't make the randomness proportional to X(n) ... but that looks realistic only with a binomial distribution (... a hypothetical game could be designed as per part(iii) ). But for a real-life continuous variable case, it would be absurd, if drift is increasing, while sigma remains rock constant. In that case, at t--> infinity, the process will approach a non-stochastic process.

Bhutes, Don't know if you are aware, there's a nice way to compute the probability of a general diffusion of the hitting one of two distinct points - via what is effectively a reparameterisation of the diffusion in terms what's called speed and scale. This only works in the case of a one-dimensional diffusion, though. You can find discussions of this in both Revuz & Yor and Karatzas & Shreve. HTH

Quick solution is expected return from strategy = 0.Possible outcomes are +9 and -3 if game is played until one is hit.So +9 x P -3 x (1-P) =0 where P is probability of hitting 9 before -3.Solution is P=1/4.