Chances of reaching infinity

Greebley · 2009-07-12, 22:28

I was wondering if the answer to the following problem was known:

Given a starting number, say 10.
You add 1 or subtract 1 where the chances of adding 1 is higher than subtracting.

Is there a chance of reaching infinity without reaching 0 first (i.e is the probability >0 ) This obviously depends on the chance of add 1 so consider:

case 1)
Chance of adding 1 is fixed. For example, start at 10 and add 1 90% of the time and subtract 1 10% of the time.

case 2)
Chance of subtracting 1 is 1 / ln(n) where n is the current number and adding is ln(n)-1/ln(n).

case 3)
chance of subtracting 1 is 1/n and adding is n-1/n

case 4)
chance of subtracting 1 is 1/2^n and adding 1 is 2^n-1/2^n.

-----
This arises trying to gain some intuition on aloquot sequences and whether they eventually might terminate. I think you could prove the chances of reaching a higher number of digits is greater than reaching less, so with d digits do you reach d+s or d-s digits first - or maybe do you reach 2d before reaching 1/2d?

If case 1 has a non-zero percentage, it would argue for some sequence to not terminate because it does appear the chance of going up is greater. It is not a proof because the numbers aren't random, but it would be a good intuition toward the result becaiuse the numbers act random.

If case 1 and case 4 differ (so case 1 has zero % and case 4 positive, then you could try numbers of a certain number of digits and see if they go up or down first. Try it for steps of 10 digits (20,30,40, etc) and plot it to see where in 1-4 the curve appears to be and try to find out the chance of reaching infinity with that case.

If case 4 has a zero percentage of reaching infinity, then it would give a strong argument against any sequence reaching infinity.

So is the answer known for case 1-4? I would be suprised if case 4 had a zero chance and I really don't know what the answer to case 1 is. BTW I am guessing that the answer for aliquot sequences is around/between 2 or 3 on the chances of increasing.

TimSorbet · 2009-07-12, 22:45

Quote:

Originally Posted by Greebley

Is there a chance of reaching infinity without reaching 0 first (i.e is the probability >0 )

nonsense
Add 1 (or 2 or 10^10^10^n) however many (finite) number of times you like, even without ever subtracting, you can never reach infinity. You could say, "reach 10,000,000" digits or any finite number if you like, but you can never reach infinity.
If the chance of adding is between .5 and 1 (50% and 100%), and the starting value is above 0, you will always tend upwards but eventually hit or go below 0.
Something that might be helpful for the purposes of aliquot sequences would be, for a certain starting value and adding/subtracting chance, how soon you can expect the sequence to terminate (but note that from each index you still "expect" that this new sequence will terminate in x iterations). I don't know how to find this value, but it's probably not too complex, at least for fixed chances.

Note: this is in no way a proof of the conjecture that all aliquot sequences will terminate, only a result of assuming it is purely random.

Or I could be the one talking nonsense.

But I think I've got most of this right...

Also, unless I'm misunderstanding what you're saying, your chances don't add up correctly. e.g. n=5 for case 4:

Quote:

Originally Posted by Greebley

case 4)
chance of subtracting 1 is 1/2^n and adding 1 is 2^n-1/2^n.

1/2^n=1/32=.03125. Therefore the chance of adding should be 1-1/32=31/32=.96875. Your equation gives 2^5-1/2^5=32-1/32=31.96875. Probabilities above 1 aren't even possible...

Greebley · 2009-07-12, 23:19

The expression just needs a set of parenthesis.(2^n-1)/2^n

"reach infinity" is perhaps imprecise, but I mean the opposite of "always reach 0". An infinte sequence can 'reach infinity' in that sense - it never reaches 0. That is what we are doing with the Aliquot seqs. See if they reach 1 (or a cycle) if they never do, then they 'reach infinity' meaning for any number you name, I can find an element of the sequence higher than it.

CRGreathouse · 2009-07-12, 23:25

Quote:

Originally Posted by Mini-Geek

nonsense

It's not nonsense, even if it is specified a bit oddly. The OP asks about the chance that the sequence (a sort of 1D random walk) will not return to 0.

Quote:

Originally Posted by Mini-Geek

If the chance of adding is between .5 and 1 (50% and 100%), and the starting value is above 0, you will always tend upwards but eventually hit or go below 0.

Is that true? That's not what my intuition would have suggested.

retina · 2009-07-13, 00:20

I think this is similar to the gamblers problem when playing in a casino. Even if you play a game where the chance to win is >0.5 for each iteration, then you still should "expect" to eventually lose all of your stake (i.e. you reach zero) simply because the casino has more money than you.

So the answer to the original Q above, is that you will always reach zero, it might take a while but if you wait long enough it is expected to happen with certainty eventually.

axn · 2009-07-13, 01:06

Quote:

Originally Posted by retina

I think this is similar to the gamblers problem when playing in a casino. Even if you play a game where the chance to win is >0.5 for each iteration, then you still should "expect" to eventually lose all of your stake (i.e. you reach zero) simply because the casino has more money than you.

So the answer to the original Q above, is that you will always reach zero, it might take a while but if you wait long enough it is expected to happen with certainty eventually.

Have you done the math on this or are you just going by analogy and gut feel?

TimSorbet · 2009-07-13, 01:42

Quote:

Originally Posted by CRGreathouse

Is that true? That's not what my intuition would have suggested.

Um...actually, I guessed that based on intuition. (similar to retina's reasoning and gambler analogy) See:

Quote:

Originally Posted by Mini-Geek

Or I could be the one talking nonsense.

It seems to me that even if the odds were 1 in a billion to subtract one, and add 1 billion when they add, and you start at a billion, you should still expect to eventually, after some insanely long time (probably measured in millions of universe-lengths with 1 calculation per planck time...or something like that) reach 0. If not, would you expect a 51% chance to add 1, (49% chance to subtract 1), starting at 1, to reach 0? Of course. So where's the cutoff where you say "this is possible, this isn't", and how do you decide that?

Quote:

Originally Posted by Greebley

The expression just needs a set of parenthesis.(2^n-1)/2^n

Oh, ok. It's just redundant then.

Quote:

Originally Posted by Greebley

"reach infinity" is perhaps imprecise, but I mean the opposite of "always reach 0". An infinte sequence can 'reach infinity' in that sense - it never reaches 0. That is what we are doing with the Aliquot seqs. See if they reach 1 (or a cycle) if they never do, then they 'reach infinity' meaning for any number you name, I can find an element of the sequence higher than it.

Ah, yes, obviously. I guess I should've been able to assume that.

bsquared · 2009-07-13, 01:48

All of your cases I think can be modeled as a 1D random walk:
http://mathworld.wolfram.com/RandomW...mensional.html

Where you have given the probabilies p and q of moving left or right on the number line. Clearly, for high enough skew between p and q, there is strong tend to grow without bound. But the variance of the distribution also grows without bound, so although it might be improbable, under this model I think there is always the possibility that the sequence will terminate.

But aliquot sequences are not random walks. The probability of moving up or down depends on previous moves (drivers and guides), and in general there is a state to the system. So it is maybe some kind of countably infinite Markov chain, and if so, is way past my pay grade to analyze.

CRGreathouse · 2009-07-13, 01:57

Quote:

Originally Posted by Mini-Geek

Um...actually, I guessed that based on intuition. (similar to retina's reasoning and gambler analogy)

It seems unlike the gambler's ruin to me, because the bet/step is fixed rather than proportional to maximal holdings.

Quote:

Originally Posted by Mini-Geek

It seems to me that even if the odds were 1 in a billion to subtract one, and add 1 billion when they add, and you start at a billion, you should still expect to eventually, after some insanely long time (probably measured in millions of universe-lengths with 1 calculation per planck time...or something like that) reach 0. If not, would you expect a 51% chance to add 1, (49% chance to subtract 1), starting at 1, to reach 0? Of course. So where's the cutoff where you say "this is possible, this isn't", and how do you decide that?

My intuition would suggest that if moving up had a higher probability than 0.5, the chance of hitting 0 (assuming you start above 0) would be less than 1. I'd be interested to see a proof either way.

axn · 2009-07-13, 03:49

Quote:

Originally Posted by Mini-Geek

would you expect a 51% chance to add 1, (49% chance to subtract 1), starting at 1, to reach 0?

Numerical simulations suggest a 3.9% probability of unbounded growth for this case. So, the answer would be no. Not 100% of the time. (Of course it'd be great if someone could provide a closed-form solution to confirm the sim).

retina · 2009-07-13, 05:36

Actually easy to prove.

At some point, x, you will always have a non-zero chance to reach termination (0) equal to q^x. Where q=1-p of course, and p>0.5.

[edit]Assumes random selection and has no relationship to Aliquot things at all. The Aliquot stuff is not random so has no relevance here.[/edit]

2009-07-12, 22:28	#1
Greebley May 2009 Dedham Massachusetts USA 3·281 Posts	Chances of reaching infinity I was wondering if the answer to the following problem was known: Given a starting number, say 10. You add 1 or subtract 1 where the chances of adding 1 is higher than subtracting. Is there a chance of reaching infinity without reaching 0 first (i.e is the probability >0 ) This obviously depends on the chance of add 1 so consider: case 1) Chance of adding 1 is fixed. For example, start at 10 and add 1 90% of the time and subtract 1 10% of the time. case 2) Chance of subtracting 1 is 1 / ln(n) where n is the current number and adding is ln(n)-1/ln(n). case 3) chance of subtracting 1 is 1/n and adding is n-1/n case 4) chance of subtracting 1 is 1/2^n and adding 1 is 2^n-1/2^n. ----- This arises trying to gain some intuition on aloquot sequences and whether they eventually might terminate. I think you could prove the chances of reaching a higher number of digits is greater than reaching less, so with d digits do you reach d+s or d-s digits first - or maybe do you reach 2d before reaching 1/2d? If case 1 has a non-zero percentage, it would argue for some sequence to not terminate because it does appear the chance of going up is greater. It is not a proof because the numbers aren't random, but it would be a good intuition toward the result becaiuse the numbers act random. If case 1 and case 4 differ (so case 1 has zero % and case 4 positive, then you could try numbers of a certain number of digits and see if they go up or down first. Try it for steps of 10 digits (20,30,40, etc) and plot it to see where in 1-4 the curve appears to be and try to find out the chance of reaching infinity with that case. If case 4 has a zero percentage of reaching infinity, then it would give a strong argument against any sequence reaching infinity. So is the answer known for case 1-4? I would be suprised if case 4 had a zero chance and I really don't know what the answer to case 1 is. BTW I am guessing that the answer for aliquot sequences is around/between 2 or 3 on the chances of increasing.

2009-07-13, 05:36	#11
retina Undefined "The unspeakable one" Jun 2006 My evil lair 6793₁₀ Posts	Actually easy to prove. At some point, x, you will always have a non-zero chance to reach termination (0) equal to q^x. Where q=1-p of course, and p>0.5. [edit]Assumes random selection and has no relationship to Aliquot things at all. The Aliquot stuff is not random so has no relevance here.[/edit] Last fiddled with by retina on 2009-07-13 at 05:41

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
What are the chances that M44 isn't M44?	jasong	Information & Answers	12	2013-10-07 04:45
Infinity, thou art a heartless bitch	chalsall	Game 1 - ♚♛♝♞♜♟ - Shaolin Pirates	15	2013-02-20 20:53
Concept of the Infinity	9021951	Miscellaneous Math	51	2011-11-04 21:43
Infinity times Zero equals Two	AntonVrba	Lounge	4	2010-10-28 20:10
Prove that the limit is infinity..	kakos22	Information & Answers	4	2010-04-18 23:18

2009-07-12, 23:19	#3
Greebley May 2009 Dedham Massachusetts USA 3·281 Posts	The expression just needs a set of parenthesis.(2^n-1)/2^n "reach infinity" is perhaps imprecise, but I mean the opposite of "always reach 0". An infinte sequence can 'reach infinity' in that sense - it never reaches 0. That is what we are doing with the Aliquot seqs. See if they reach 1 (or a cycle) if they never do, then they 'reach infinity' meaning for any number you name, I can find an element of the sequence higher than it.

2009-07-13, 00:20	#5
retina Undefined "The unspeakable one" Jun 2006 My evil lair 6,793 Posts	I think this is similar to the gamblers problem when playing in a casino. Even if you play a game where the chance to win is >0.5 for each iteration, then you still should "expect" to eventually lose all of your stake (i.e. you reach zero) simply because the casino has more money than you. So the answer to the original Q above, is that you will always reach zero, it might take a while but if you wait long enough it is expected to happen with certainty eventually.

2009-07-13, 01:48	#8
bsquared "Ben" Feb 2007 3×5×251 Posts	All of your cases I think can be modeled as a 1D random walk: http://mathworld.wolfram.com/RandomW...mensional.html Where you have given the probabilies p and q of moving left or right on the number line. Clearly, for high enough skew between p and q, there is strong tend to grow without bound. But the variance of the distribution also grows without bound, so although it might be improbable, under this model I think there is always the possibility that the sequence will terminate. But aliquot sequences are not random walks. The probability of moving up or down depends on previous moves (drivers and guides), and in general there is a state to the system. So it is maybe some kind of countably infinite Markov chain, and if so, is way past my pay grade to analyze.