The All-Thing

All stick and no carrot, since ought-three.


行宮 (元稹)


| web page

Other views:
RSS 1.0
RSS 0.91
Plain (good for lynx)

Past posts:

Sun Mon Tue Wed Thu Fri Sat

Recent comments:
Re: Re: Gateway ECDT by William
Re: Gateway ECDT by Greg
Re: Re: Linux Media Jukebox/PVR by William
Re: Linux Media Jukebox/PVR by fiona!

Recent search referers:
chinese bittorrent
"burrows wheeler transform"
bittorrent pr0n (x2)
hot to spell thing in chinese
"Gateway 200x" review burner
torrent pr0n (x2)
Expert Judgement on Markers to Deter Inadvertent Human Intrusion into the Waste Isolation Pilot Plant
seven samurai torrent
dueling banjos sheet music
download XIII crack (x2)
xiii torrent
no cd XIII (x2)
Torrent xbox
crack no cd XIII
pr0n torrent (x2)

William's Aggregated Feeds

Creative Commons License
This work is licensed under a Creative Commons License.

Sun, 14 Sep 2003

Gambler's Ruin

Could anyone who knows a little about random walks lend me a hand? I've been thinking about the Gambler's Ruin, trying to figure out why the probabilities of winning are what they are. I believe it is equivalent to the following random walk problem:

Given a finite one-dimensional ladder with n rungs r_0 .. r_n, starting at rung s, at each each time t the probability of going up one rung is p, and that of going down one rung 1-p. The game ends when you reach the top or the bottom rung, so what is the probability of hitting the top of the ladder, as a function of n and s?

I can write the recurrence:

 P(R_0 = s) = 1
 P(R_0 = r) = 0 \forall r \neq s
 P(R_t = x) = p * P(R_{t-1} = x-1) + (1-p) * P(R_{t-1} = x+1)

where R_t is the rung you're at at time t, which might be helpful, but I'm also not clear how to solve it. In general this seems like a pretty basic random walk question, so... little help, please?

(In terms of the Gambler's Ruin problem, tacit in the above formulation is the assumption that, in flipping the coin, you first choose a pile with equal probability, and then flip a coin from that pile—as opposed to picking a coin to flip independently of which pile it's in. The Mathworld page doesn't specify how the coin to be flipped is chosen, but it seems like it matters, so that's my simplifying assumption.)

Posted at 18:30 | /math | (leave a comment) | permalink


Wagner's music is better than it sounds. -- Mark Twain