Chances of reaching infinity - Page 2

CRGreathouse · 2009-07-13, 06:44

Quote:

Originally Posted by retina

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.

How does that prove anything here? I agree with the statement "at a given point x there is a nonzero probability of termination" but don't see why that would imply that the chance of eventual termination is 100%.

For example, was that true, a biased (p > 0.5) 1-D random walk would be recurrent, and I don't believe it is.

retina · 2009-07-13, 06:56

Quote:

Originally Posted by CRGreathouse

How does that prove anything here? I agree with the statement "at a given point x there is a nonzero probability of termination" but don't see why that would imply that the chance of eventual termination is 100%.

I would expect that for there to be a guarantee that you never reach zero then the chance of reaching zero also has to be zero. But since there is always a positive chance to reach zero then, given enough time, you will reach zero. How could you never reach zero unless the actual chance to get there is also zero?

I think the key point is the "given enough time". Clearly this could be considerable and for practical purposes people would ignore such large time periods, but mathematically you can't dismiss it so easily.

10metreh · 2009-07-13, 07:18

Sorry if I've misunderstood something, but are you saying that a random walk which goes up with a probability of 1 - epsilon (make epsilon as close to 0 as you want) and down with a probability of epsilon is certain to reach 0 at some point? If so, give me a proof. Not a Fischbach-style argument, a proof.

retina · 2009-07-13, 07:35

I think that trying to prove the opposite (that there is zero chance to terminate) has already been shown to be false, it is always epsilon^x, which is never zero.

Greebley · 2009-07-13, 11:41

If the chance of reaching x goes to 0 as x goes to infinity, then there is a 'zero percent chance of reaching infinity' (using the inexact language in the problem). It is only when the limit is above zero do you say that there is 'a chance of reaching infinity'.

Agree that aliquot sequences aren't fully random, but what does appear to be random is what comes after a sequence ends. Since drivers don't appear to last all the way down or up and the next driver is random, then they do in a sense act randomly - just on a larger scale than one step. So while not a proof, it does offer intuition to the problem.

Given the numerical simulation from axn, it would appear that the answer is yes, you can have unbounded sequences provided the chance of going up is always greater than going down which argues against the Catalan Conjecture. There would have to be some kind of structure to the sequences that forces them down to 1 or cycles, or some other aspect to them I am not considering here.

R.D. Silverman · 2009-07-13, 11:46

Quote:

Originally Posted by retina

I think that trying to prove the opposite (that there is zero chance to terminate) has already been shown to be false, it is always epsilon^x, which is never zero.

See Feller. It is perhaps the "bible" on probability theory.

A one-dimensional random walk with probabilities p and (1-p) will always return
to the origin infinitely often. It goes to oo with probability 0, but
can drift arbitrarily far from the origin. That is to say, for any real M
the random walk will cross M infinitely often.

10metreh · 2009-07-13, 12:52

Quote:

Originally Posted by R.D. Silverman

See Feller. It is perhaps the "bible" on probability theory.

A one-dimensional random walk with probabilities p and (1-p) will always return
to the origin infinitely often. It goes to oo with probability 0, but
can drift arbitrarily far from the origin. That is to say, for any real M
the random walk will cross M infinitely often.

Are you saying that, if the probability of going up is $1-\epsilon$ and the probability of going down is $\epsilon$ , where $\epsilon$ is made as small as possible without reaching 0, then even though almost all steps will be up, the walk will eventually return to 0?

Greebley · 2009-07-13, 14:13

In the wikipedia article they state that a simple random walk is one with an equal chance of going in either direction, but it doesn't state anything about a walk that is biased in one direction. I am not even sure what a non-equal chance 'random walk' would be called - is it even a random walk? This makes it hard to search for. I will look up Feller's book if I get the chance, but I don't go by the local library at all these days - I don't have a lot of time to read it seems.

R.D. Silverman · 2009-07-13, 14:33

Quote:

Originally Posted by Greebley

In the wikipedia article they state that a simple random walk is one with an equal chance of going in either direction, but it doesn't state anything about a walk that is biased in one direction. I am not even sure what a non-equal chance 'random walk' would be called - is it even a random walk? This makes it hard to search for. I will look up Feller's book if I get the chance, but I don't go by the local library at all these days - I don't have a lot of time to read it seems.

For those who think the result is counter-intuitive:

Suppose the random walk is at point M>0 at some point in time.
The probability that it will return to 0 without ever taking a right
step is just epsilon^M. This may be small, but it is non-zero.
The probability is even larger if one allows some right steps
along the way. This may be modelled as a Markov process.
The transition matrix is simple because the probability of moving left
(or right) is fixed at each step. The process is also Ergodic.

The value of epsilon DOES NOT MATTER as long as it is non-zero.

10metreh · 2009-07-13, 15:47

Quote:

Originally Posted by R.D. Silverman

For those who think the result is counter-intuitive:

Suppose the random walk is at point M>0 at some point in time.
The probability that it will return to 0 without ever taking a right
step is just epsilon^M. This may be small, but it is non-zero.
The probability is even larger if one allows some right steps
along the way. This may be modelled as a Markov process.
The transition matrix is simple because the probability of moving left
(or right) is fixed at each step. The process is also Ergodic.

The value of epsilon DOES NOT MATTER as long as it is non-zero.

So, in short, all random walks eventually return to zero? So how did axn's calculations go wrong?

wblipp · 2009-07-13, 15:53

It's been a few decades since I last read Feller, but I think the probability of ever returning to zero is less than 1 when the upward step probability is greater than the downward step. Here's the analysis as I recall it:

Let "x" be the probability of ever reaching to zero from one. At the next step you reach zero with probability p and you reach two with probability 1-p. If you reach zero, you are done. If you reach two, then to reach zero you must at some point reach one, and then reach zero from one. But reaching one from two is the same as reaching zero from one - so that probability is x. Hence the probability of ever reaching zero from two is x². Putting these observations together leads to the equation

x = p + (1-p)*x²

This equation has solutions x=1 and x=p/(1-p). When downward steps predominate, x=1 is the only solution that is a probability. When upward steps predominate both are probabilities, so it requires a bit more work to show which solution is the correct probability. I think that works by setting up the equation for "never returns to zero from one" as "first goes to two" and then either "never returns to one from two" or "returns to one from two but never returns to zero from one."

WIlliam

2009-07-13, 07:18	#14
10metreh Nov 2008 2·3³·43 Posts	Sorry if I've misunderstood something, but are you saying that a random walk which goes up with a probability of 1 - epsilon (make epsilon as close to 0 as you want) and down with a probability of epsilon is certain to reach 0 at some point? If so, give me a proof. Not a Fischbach-style argument, a proof. Last fiddled with by 10metreh on 2009-07-13 at 07:19

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-13, 07:35	#15
retina Undefined "The unspeakable one" Jun 2006 My evil lair 14124₈ Posts	I think that trying to prove the opposite (that there is zero chance to terminate) has already been shown to be false, it is always epsilon^x, which is never zero.

2009-07-13, 11:41	#16
Greebley May 2009 Dedham Massachusetts USA 843₁₀ Posts	If the chance of reaching x goes to 0 as x goes to infinity, then there is a 'zero percent chance of reaching infinity' (using the inexact language in the problem). It is only when the limit is above zero do you say that there is 'a chance of reaching infinity'. Agree that aliquot sequences aren't fully random, but what does appear to be random is what comes after a sequence ends. Since drivers don't appear to last all the way down or up and the next driver is random, then they do in a sense act randomly - just on a larger scale than one step. So while not a proof, it does offer intuition to the problem. Given the numerical simulation from axn, it would appear that the answer is yes, you can have unbounded sequences provided the chance of going up is always greater than going down which argues against the Catalan Conjecture. There would have to be some kind of structure to the sequences that forces them down to 1 or cycles, or some other aspect to them I am not considering here.

2009-07-13, 14:13	#19
Greebley May 2009 Dedham Massachusetts USA 3·281 Posts	In the wikipedia article they state that a simple random walk is one with an equal chance of going in either direction, but it doesn't state anything about a walk that is biased in one direction. I am not even sure what a non-equal chance 'random walk' would be called - is it even a random walk? This makes it hard to search for. I will look up Feller's book if I get the chance, but I don't go by the local library at all these days - I don't have a lot of time to read it seems.

2009-07-13, 15:53	#22
wblipp "William" May 2003 New Haven 2·7·13² Posts	It's been a few decades since I last read Feller, but I think the probability of ever returning to zero is less than 1 when the upward step probability is greater than the downward step. Here's the analysis as I recall it: Let "x" be the probability of ever reaching to zero from one. At the next step you reach zero with probability p and you reach two with probability 1-p. If you reach zero, you are done. If you reach two, then to reach zero you must at some point reach one, and then reach zero from one. But reaching one from two is the same as reaching zero from one - so that probability is x. Hence the probability of ever reaching zero from two is x². Putting these observations together leads to the equation x = p + (1-p)*x² This equation has solutions x=1 and x=p/(1-p). When downward steps predominate, x=1 is the only solution that is a probability. When upward steps predominate both are probabilities, so it requires a bit more work to show which solution is the correct probability. I think that works by setting up the equation for "never returns to zero from one" as "first goes to two" and then either "never returns to one from two" or "returns to one from two but never returns to zero from one." WIlliam