Two Plus Two Poker Forums Expected number of steps
 Register FAQ Search Today's Posts Mark Forums Read Video Directory TwoPlusTwo.com

 Notices

 Probability Discussions of probability theory

 06-06-2012, 11:06 PM #1 adept   Join Date: Aug 2010 Posts: 888 Expected number of steps Suppose you start with some positive number n. Randomly select one of the following actions with the given probability: (with probability 1/2): Decrease n by 1. (with probability 1/3): Increase n by 1. (with probability 1/6): Don't change n. It's obvious that if you repeat this process, n will tend to decrease with time. How do you figure out the expected number of steps taken until n is reduced to 0?
 06-06-2012, 11:12 PM #2 Carpal \'Tunnel     Join Date: Jun 2005 Location: Psychology Department Posts: 7,430 Re: Expected number of steps 1/2*-1 + 1/3*1 + 1/6*0 = -1/6 That means for each step we expect the value of n to decrease by -1/6. So for every 6 steps we expect n to decrease by 1. So at step n*6 we expect to be at zero.
 06-06-2012, 11:24 PM #3 Carpal \'Tunnel     Join Date: Jun 2005 Location: Psychology Department Posts: 7,430 Re: Expected number of steps A short R function that can be used to confirm with simulation. Code: ```stepcount <- function(n, sims) { res <- rep(NA, sims) for(i in 1:sims) { val <- n cnt <- 0 while(val > 0) { draw <- sample(c(-1, 1, 0), 1, prob=c(1/2, 1/3, 1/6), replace=T) val <- val + draw cnt <- cnt + 1 } res[i] <- cnt } return(mean(res)) }``` Code: ```stepcount(1, 100000) [1] 5.96231 stepcount(2, 100000) [1] 12.0977```
 06-06-2012, 11:33 PM #4 adept   Join Date: Aug 2010 Posts: 888 Re: Expected number of steps Thanks... Haha, I feel kinda dumb now. I was playing around with a more complicated problem and simplified it to this, but still looked at it as being a bit harder than it really is.
06-07-2012, 12:45 AM   #5
Carpal \'Tunnel

Join Date: Sep 2002
Posts: 8,907
Re: Expected number of steps

Quote:
 Originally Posted by Sherman 1/2*-1 + 1/3*1 + 1/6*0 = -1/6 That means for each step we expect the value of n to decrease by -1/6. So for every 6 steps we expect n to decrease by 1. So at step n*6 we expect to be at zero.
So how long would it take if I flip a fair coin and increase by 1 on heads and decrease by 1 on tails?

06-07-2012, 09:39 AM   #6
Carpal \'Tunnel

Join Date: Jun 2005
Location: Psychology Department
Posts: 7,430
Re: Expected number of steps

Quote:
 Originally Posted by BruceZ So how long would it take if I flip a fair coin and increase by 1 on heads and decrease by 1 on tails?
I think you are challenging me to answer this question and not merely making a joke...so I will try (but I will be wrong).

Using the expected value approach I used, one might conclude that the answer is that it would never reach zero. But in reality, the answer is that we expect our value to vary randomly around the starting value and touch every possible value (including 0) as the number of flips approaches infinity.

Clearly the expected number of flips it takes to reach a value of 0 is dependent on the initial value of n. For example, if n is 1 it is much more likely to reach 0 sooner than if n is 100. But both are still expected to reach 0 at some point. I just don't know how to quantify that. I feel like it has something to do with e or 1/e, but I'm not sure. I'd be interesting in your answer Bruce. I think this is as far as I can get (this is what happens when you lack formal mathematical training I think).

edit: Thinking more, is it simply that the answer approaches infinity? That is, if the number of flips it takes the coin to reach zero on a single occasion approaches infinity, then averaging a value that approaches infinity with other values gives us a value of "approaching infinity." No?

Last edited by Sherman; 06-07-2012 at 09:45 AM.

06-07-2012, 11:32 AM   #7

Join Date: Dec 2002
Posts: 833
Re: Expected number of steps

Quote:
 Originally Posted by Sherman edit: Thinking more, is it simply that the answer approaches infinity? That is, if the number of flips it takes the coin to reach zero on a single occasion approaches infinity, then averaging a value that approaches infinity with other values gives us a value of "approaching infinity." No?
That's where I'm leaning. Let f(n) be the expected number of flips before reaching 0 when starting at n.

If you start with n=1, after one flip you are either at 0 or 2.
so f(1) = .5 * 1 + .5 * f(2)

By the same logic:
f(2) = .5 * f(1) + .5 * f(3)
f(3) = .5 * f(2) + .5 * f(4)
f(n) = .5 * f(n-1) + .5 * f(n+1)

If you use substitution over and over, f(1) will have small components of f(1,000,000) and f(1,000,000,000) and so on, meaning the average number of flips will approach infinity.

I haven't actually done the substitutions, so maybe there's some clever way to get a geometric series that does converge?

06-07-2012, 01:17 PM   #8
Carpal \'Tunnel

Join Date: Sep 2002
Posts: 8,907
Re: Expected number of steps

Quote:
 Using the expected value approach I used, one might conclude that the answer is that it would never reach zero.
No, one would conclude that on average it will take an infinite number of flips to reach zero, and that would be correct. The average duration of the game is infinite.

Quote:
 But in reality, the answer is that we expect our value to vary randomly around the starting value and touch every possible value (including 0) as the number of flips approaches infinity.
It will touch every possible value with probability 1. But on average it will take an infinite number of flips to get to any given value.

Quote:
 Clearly the expected number of flips it takes to reach a value of 0 is dependent on the initial value of n.
Nope. It's infinite for any value of n. On average it will take an infinite number of flips just to go from 1 to 0.

Quote:
 For example, if n is 1 it is much more likely to reach 0 sooner than if n is 100.
On average both will require an infinite number of flips. But for any given finite number of flips, it is more likely to reach zero when n is 1 than when n is 100.

Quote:
 I think this is as far as I can get (this is what happens when you lack formal mathematical training I think).
No need; your method arrives at this classic result as a matter of basic arithmetic.

Quote:
 edit: Thinking more, is it simply that the answer approaches infinity? That is, if the number of flips it takes the coin to reach zero on a single occasion approaches infinity, then averaging a value that approaches infinity with other values gives us a value of "approaching infinity." No?
As the number of flips becomes very large, the probability that we haven't reached zero yet becomes very small. But when you multiply these very small probabilities by the very large numbers of flips, and then sum to get an expected value, the sum is infinite.

 06-07-2012, 02:08 PM #9 veteran   Join Date: Jan 2009 Posts: 2,341 Re: Expected number of steps Quote: Clearly the expected number of flips it takes to reach a value of 0 is dependent on the initial value of n. "Nope. It's infinite for any value of n. On average it will take an infinite number of flips just to go from 1 to 0." Infinity can really mess with your mind. This problem reminds me of the theorem that says there are as many total integers as there are even integers. It's one of those - I know it's true but I don't quite believe it.
 06-07-2012, 02:17 PM #10 Carpal \'Tunnel     Join Date: Jun 2005 Location: Psychology Department Posts: 7,430 Re: Expected number of steps Yes. Thanks Bruce & Statmanhal. So (this time) my intuitive answer was correct and I started to over-think it. Then when I over-thought it enough, I got back to the intuitive answer. Sigh.
06-07-2012, 02:20 PM   #11
Carpal \'Tunnel

Join Date: Sep 2002
Posts: 8,907
Re: Expected number of steps

Quote:
 Originally Posted by statmanhal This problem reminds me of the theorem that says there are as many total integers as there are even integers. It's one of those - I know it's true but I don't quite believe it.
That's only because "as many" is defined in a particular way, namely the ability to put them into 1-to-1 correspondence.

There are as many points on the line segment between (0,0,0) and (0,0,1) as there are in all of 3-dimensional space.

 06-07-2012, 02:55 PM #12 adept   Join Date: Aug 2010 Posts: 888 Re: Expected number of steps Some math that I think answers both questions a little bit more conclusively (although I agree that the first argument was correct, I felt like it wasn't completely a mathematically correct way to get the answer)... Suppose: with probability p: increase n by 1 with probability q: decrease n by 1 with probability r: stay at current state p+q+r = 1 Let f(n) be the number of states until we reach 0: I.e., these two equations are satisfied: f(0) = 0 f(n) = 1 + p*f(n+1) + q*f(n-1) + r*f(n) First note that f(1) is the expected number of steps to reduce current n by 1. So: f(n) = f(n-1) + f(1) => f(2) = f(1) + f(1) = 2*f(1) f(3) = f(2) + f(1) = 3*f(1) f(4) = f(3) + f(1) = 4*f(1) etc.. => f(n) = n*f(1) Let: f(1) = c f(n) = n*c For n>0: f(n) = 1 + p*f(n+1) + q*f(n-1) + r*f(n) => nc = 1 + p*c*(n+1) + q*c*(n-1) + r*c*n (pc+qc+rc-c)*n + 1+pc-qc = 0 Since p+q+r=1 => pc+qc+rc-c = 0 => 1 + pc-qc = 0 c = 1/(q-p) ------------------------------------ So the general solution is: f(n) = n/(q-p) => For p=1/3, q=1/2, c=6... I.e., f(n) = 6n (my first question) As p approaches q, c->infinity, f(n)->infinity for n>0 Last edited by pocketzeroes; 06-07-2012 at 03:01 PM.
 06-07-2012, 03:19 PM #13 Carpal \'Tunnel     Join Date: Sep 2002 Posts: 8,907 Re: Expected number of steps That's how a highfalutin textbook would do it, but it isn't necessary. You don't need a difference equation. A simple algebraic equation will do. Let E(n) be the expected number of steps to get to zero from n. Then for the original problem we have E(1) = 1/2*1 + 1/6*[1 + E(1)] + 1/3*[1 + 2*E(1)] E(1) = 6 E(n) = n*E(1) = 6n. For the fair problem we have E(1) = 1/2*1 + 1/2*[1 + 2*E(1)] E(1) = E(1) + 1 which of course can only be satisfied when E(1) is infinite.
 06-07-2012, 03:51 PM #14 Carpal \'Tunnel     Join Date: Sep 2002 Posts: 8,907 Re: Expected number of steps Upon closer examination I see that's the same as what you did. At first glance I thought that you were solving a difference equation directly as you would do for the probability of winning a freezeout. The difference there is that the game ends when either player goes broke. If only 1 player can go broke, then you can use the simple algebraic method to get the risk of ruin.
06-07-2012, 06:19 PM   #15

Join Date: Aug 2010
Posts: 888
Re: Expected number of steps

Quote:
 Originally Posted by BruceZ Upon closer examination I see that's the same as what you did. At first glance I thought that you were solving a difference equation directly as you would do for the probability of winning a freezeout. The difference there is that the game ends when either player goes broke. If only 1 player can go broke, then you can use the simple algebraic method to get the risk of ruin.
Yeah, my first attempt to do this (before I originally posted it) involved solving the difference equation. But I only vaguely remembered how to solve homogenous equations -- this is non-homogenous though and I figured I was missing something... Once you realize that f(n) must be linearly related to n (i.e., f(n)=cn), it's pretty simple.

Anyway, I started trying to figure out an example where the first method doesn't work (when the number of steps taken to get an expected value of n=0 is not the same as the expected number of steps to reach n=0) -- for example, if the probabilities change with respect to n, it won't work.

Here's the simplest problem of this sort I could think of:
With probability (1/2 + 1/n): decrease n by 1
With probability (1/2 - 1/n): increase n by 1

How long does it take, on average, until n = 1?

These problems seem to get pretty difficult fairly quickly, and I gave up before too long... Or suppose, more generally, we have:
With probability p(n): decrease n by 1
With probability 1-p(n): increase n by 1

Assuming p(n)>1/2 for all n, can we prove that the stopping-time is finite?

None of this is very important to me, but I'd still be interested in checking out some books if anybody knows any good ones on these types of problems.

 Thread Tools Display Modes Linear Mode

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is OffTrackbacks are Off Pingbacks are Off Refbacks are Off Forum Rules

All times are GMT -4. The time now is 05:34 AM.

 Contact Us - Two Plus Two Publishing LLC - Privacy Statement - Top