<gladhobo@teksavvy.com> wrote:
Begin with some arbitrarily large positive integer and repeatedly subtract a randomly chosen integer from zero to nine. What is the probability that you will land on zero?
From: Charles Greathouse <charles.greathouse@case.edu> Well, you can determine the probability for 1 through 9 directly, to wit 1 1/9 2 10/81 3 100/729 4 1000/6561 5 10000/59049 6 100000/531441 7 1000000/4782969 8 10000000/43046721 9 100000000/387420489
Then you can set up the linear recurrence and solve for the coefficients. The coefficient of the power of 1 should give the answer, since all other roots of the characteristic polynomial have absolute value < 0.805 and so are insignificant for the "arbitrarily large" positive integer you start at.
--sounds like a valid plan, but there is a simpler way. Consider hopping thru the integers, randomly chosen hop sizes 0-9. Ignore the 0s. The stepping stones in this walk, have density 9/(1+2+3+4+5+6+7+8+9) = 1/5. Hence the probability that 0 is a stepping stone, is 1/5=20%.