Expected number of steps - Gambling and Probability

pocketzeroes · 06-06-2012, 11:06 PM

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?

Sherman · 06-06-2012, 11:12 PM

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.

Sherman · 06-06-2012, 11:24 PM

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

pocketzeroes · 06-06-2012, 11:33 PM

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.

**BruceZ** · 06-07-2012, 12:45 AM

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?

Sherman · 06-07-2012, 09:39 AM

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?

wamplerr · 06-07-2012, 11:32 AM

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?

**BruceZ** · 06-07-2012, 01:17 PM

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.

statmanhal · 06-07-2012, 02:08 PM

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.

Sherman · 06-07-2012, 02:17 PM

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.

**BruceZ** · 06-07-2012, 02:20 PM

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.

pocketzeroes · 06-07-2012, 02:55 PM

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

**BruceZ** · 06-07-2012, 03:19 PM

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.

**BruceZ** · 06-07-2012, 03:51 PM

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.

pocketzeroes · 06-07-2012, 06:19 PM

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.