## Would this ever end? (infinities)

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

ian
Posts: 706
Joined: Fri Mar 07, 2008 3:55 pm UTC
Location: Sealand

### Would this ever end? (infinities)

Code: Select all

if x=0 END    else       flip a coin       if heads -> x=x+10       if tails -> x=x-1

would it ever end? at any point a result of x tails in a row will end the program/function, but the chances of this happening become smaller at a greater rate (i hope that makes sense).

my intuition says it should both end, and also x should tend towards infinity, so which is it? or is it somehow both, with x tending towards infinity but then suddenly dropping to zero?

jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

### Re: Would this ever end? (infinities)

ian wrote:my intuition says it should both end, and also x should tend towards infinity, so which is it? or is it somehow both, with x tending towards infinity but then suddenly dropping to zero?

There's a positive probability of both of those outcomes, though the probability of the program not terminating is far larger than that of terminating.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

ian
Posts: 706
Joined: Fri Mar 07, 2008 3:55 pm UTC
Location: Sealand

### Re: Would this ever end? (infinities)

yes, sorry i should have been more precise about my question. i realise at any point the program can terminate, but am i right in thinking the probability of it terminating goes towards zero and the probability of it not terminating goes towards one as more loops are added (for a non-terminated-already run)? and does this mean we can say if we sum the probabilities of it terminating at any point over all points it will be less than 50%, so on average the program will not terminate, that is sometimes it will run for infinity? or does that last little bit not really make sense, as the chance of it terminating is always greater than zero, so over an infinite amount of time it still should?
Last edited by ian on Thu Apr 07, 2011 4:09 pm UTC, edited 1 time in total.

Jyrki
Posts: 117
Joined: Mon Dec 06, 2010 12:27 pm UTC
Location: Rusko, Finland

### Re: Would this ever end? (infinities)

I'm feeling grumpy, so...

Since this is a program I say that it is certain to terminate. After all, the integer range is finite. If it's 16-bit integers, then after 32767 we loop down to -32768. Therefore the program gets a fresh chance to hit zero after about every 65536/9 iterations. With 32-bit integers it will take a little longer

ian
Posts: 706
Joined: Fri Mar 07, 2008 3:55 pm UTC
Location: Sealand

### Re: Would this ever end? (infinities)

Jyrki wrote:I'm feeling grumpy, so...

Since this is a program I say that it is certain to terminate. After all, the integer range is finite. If it's 16-bit integers, then after 32767 we loop down to -32768. Therefore the program gets a fresh chance to hit zero after about every 65536/9 iterations. With 32-bit integers it will take a little longer

I take it your name is pronounced 'Jerky'? :p

skullturf
Posts: 556
Joined: Thu Dec 07, 2006 8:37 pm UTC
Location: Chicago
Contact:

### Re: Would this ever end? (infinities)

Finding the exact probability that it terminates (assuming we're at "step 0") is an interesting exercise.

Certainly, there is a nonzero probability that it terminates, because it's possible to start with a run of 10 tails. The probability of that is small, but is definitely NOT zero -- in fact, it's exactly 1/1024 (= 1/2^10).

But then there are other (rarer) ways for the program to terminate. For instance, there might be one head and nine tails in the first ten tosses. That would put the total at 11. There's a nonzero probability that you then get tails eleven times in a row.

--------

To try to deal with ian's second question:

At "step 0", the probability of termination is greater than 1/1024. (I haven't worked out the exact probability -- see above).

I think something along the following lines will probably be true: if we're given that we're at step k and the program hasn't terminated, what is the probability it will eventually terminate? I'm guessing that gets smaller as k increases.

eta oin shrdlu
Posts: 450
Joined: Sat Jan 19, 2008 4:25 am UTC

### Re: Would this ever end? (infinities)

You can recast this problem as a linear recurrence relation to find the exact probability of termination.
Spoiler:
Let P(n) be the probability that the program terminates, starting from x=n. Clearly P(0)=1; the iteration step gives the eleventh-order recurrence$$P(n)=\frac12[P(n-1)+P(n+10)]$$(for all n>0). Assuming unbounded integer sizes, we also want [imath]P(n)\to0[/imath] as [imath]n\to+\infty[/imath].

The general solution to such a recurrence is generically of the form$$P(n)=\sum_k c_k (r_k)^n$$where [imath]r_k[/imath] are the roots of the characteristic polynomial, found by substituting [imath]P(n)=x^n[/imath]. [If the characteristic polynomial has repeated roots the form is slightly more complicated.] Here the characteristic polynomial is the eleventh-degree polynomial [imath]x^{11}-2x+1[/imath]. This has eleven distinct roots, so finding the coefficients seems difficult. But one of the roots is 1, and nine have magnitudes larger than 1, so there's really only one physical root, [imath]r\approx0.500245462[/imath], so$$P(n)=r^n\;\;.$$This makes the termination probability, starting from n=10, roughly 1/1019.

You can also think of this as a biased random walk (at each step the particle moves 4.5 units rightward, then with equal probability moves 5.5 units either left or right).