All stick and no carrot, since ought-three.
燕草如碧絲，秦桑低綠枝。 當君懷歸日，是妾斷腸時。 春風不相識，何事入羅幃？
Recent search referers:
Thu, 09 Oct 2003
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)
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).
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.)Sun, 14 Sep 2003
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:
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.)
Tempt not a desperate man. -- William Shakespeare, "Romeo and Juliet"