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
20 21 22 23 24
25 26 27 28 29 30 31

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.

Thu, 09 Oct 2003

Whitney Numbers

This was cool. I've been working on a problem at work and at one point we needed to find the maximum number of ways of dividing an /n/-dimensional space into k partitions. It's easy enough to figure this out for the one- and two-dimensional case, and pretty mind-bending for the three-dimensional case, but what about the generalization?

So we go to the Online Encyclopedia of Integer Sequences, type in (get this) 2, 4, 8 (the first three entries for the 3-d case) and lo and behold, we get:

Cool or what? (A complete fluke as their sequence is the table read by anti-diagonals... wtf?)

So anyways, the solution is

W(n,k)=if k=0 or n=0 then 1 else W(n,k-1)+W(n-1,k-1), or
W(n,k)=Sum(binomial(k,i), i=0..n)

if you were curious (so order exponential, unfortunately for us).

Posted at 13:38 | /math | (leave a comment) | permalink

Gambler's Ruin Solution

My language exchange partner and I were going over the Gambler's Ruin problem yesterday (he is a big random walk guy and yes, this is the type of stuff we end up talking about in the English portion) and we came up with a solution remarkably similar to this one I found today:

No random walks involved, just straight recurrence solving. Interesting that there's a hidden q != p assumption in there (which we didn't notice and had us scratching our heads as to why everything collapsed to 0/0 in the q = p case.)

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

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


Tempt not a desperate man. -- William Shakespeare, "Romeo and Juliet"