Admistrivia

• Readings: Chapter 3 up to page 166
• Homework due thursday
• Questions from the homework?

Chapter III.5.3: Random walk

Recall random walk definition

• Big matrix! (q = move left, p = move right, r = stay put)

Random walk ruin probability

• First step analysis generates recursion
• That is all there is to the theory--now just solve it
• Good guessing is the traditional way of generating a solution!
• But there is an alternative: Martingales!
  • Create a martingale that matches the first step analysis
  • If a bettor were betting--what would make it fold back on itself?
  • Eg: The bettor wins $1 (with prob p) or loses $(p/q) (with probability q). He wins $1. What should his next bet be to land him right back where he was? Win $(q/p) vs lose $1.
  • Let the state count the number of net winning bets of the bettor.
  • Label states by bet amount: (q/p)^i
  • Check that it is a martingale (don't forget the boundary!)
• Now that we have a martingale what do we do with it?
  • Where will X_T be for large T? (Markov chains tell us it will be at one of the absorbing states)
  • What is the expected value of X_T? (Martingales tell us it is X₀)
  • Solve the resulting equation and we are done!
• Maybe guessing the solution isn't so bad after all
• (q/p)ⁱ - (q/p)ⁿ)/(1 - (q/p)ⁿ)

Understanding the equation itself

Graph

• plot fall off for the 3 cases: p < q, p > q, p = q.

Large n

• What if n is really really large?
• Easy to compute limit.

Success runs processes

• "double or nothing"
• Failure goes back to beginning
• Called renewal process