Interesting problem i stumbled upon IRL today.

Start with the number X. at step one, pick a random number (z)
in [0,2x], step two, take that number and pick a random number in
[0,2z]. do this until you pick 0. What is the expected number of
steps until you reach 0 (in terms of x obviously) ( x and all subsequent picks are natural numbers)

10/18/2010 7:13:12 PM

Assuming each draw is from a discrete uniform distribution?

10/18/2010 8:34:45 PM

yes

10/18/2010 8:48:44 PM

My instinct is 1/(4x^2+2x+1), but I'm probably way off base here. The scope of my mathematical knowledge is rather limited and all I can really say is I wouldn't know where to start with the expected value of a converging series.

10/18/2010 8:52:44 PM

what's your thought process there?

EDIT:

We know the solution is not going to be less than one for any value of x > 1, simply because the probability that length > 1 = 1/x. (i.e., the probability you don't randomly pick zero on your first trial)




[Edited on October 18, 2010 at 8:57 PM. Reason : .]

Maybe I wasn't clear, X is a natural number, so my notation [0,2x] means any integer between 0 and 2x.

[Edited on October 18, 2010 at 8:58 PM. Reason : ..]

10/18/2010 8:55:08 PM

Am I oversimplifying/missing things, or is the answer just 2x+1?

[Edited on October 18, 2010 at 10:43 PM. Reason : My approach is to invoke the law of iterated expectations.]

10/18/2010 10:40:49 PM

either you're oversimplifying or your brilliant, I don't see how x^2 + 1 falls out of the law of iterated expectation - how did you apply it anyway?

10/18/2010 11:41:07 PM

Quote :

"what's your thought process there?"

I was tired as shit, sorry about that. I was going by the probability of any number in a given iteration as 2x+1 and for some reason I thought squaring that would yield the convergence series. I can't explain the process, but know that I, too, know that I can be stupid.

Shadowrunner is right in that the probability of any number in each iteration is 2x+1.
The expected value of any number in each iteration is x. (0+x+2x)/3 = x
And (I'm an artard) the expected number of rounds is also 2x+1 Good call on the law of iterated expectations, Shadowrunner!

Good thread, 1985!

10/19/2010 12:21:21 AM

I don't think this is true.

Simulate it : for x = 5, E(L) ~ 8.75.

It looks like f(x) + g(x)*log(x)

10/19/2010 5:14:22 PM

Hmm, I'm simulating it and do get 2x+1. Here's the code I'm running in R; it's not optimized or anything because I just whipped it up in five minutes, but it should get the job done.

x <- 10
iterates <- 10000
seq <- NULL
num_steps <- NULL
for (i in 1:iterates) {
  draw <- floor(runif(1, min=0, max=2*x+1))
  seq <- draw
  while (seq[length(seq)] != 0) {
   draw <- floor(runif(1, min=0, max=2*x+1))
   seq <- c(seq, draw)
  }
  num_steps <- c(num_steps, length(seq))
}
mean(num_steps)

10/19/2010 6:15:15 PM

^

You're not altering the width of the interval at each step. Try this:

x <- 5
iterates <- 10000
seq <- NULL
num_steps <- NULL
for (i in 1:iterates) {
draw <- floor(runif(1, min=0, max=2*x+1))
seq <- draw
while (seq[length(seq)] != 0) {
draw <- floor(runif(1, min=0, max=2*draw+1))
seq <- c(seq, draw)
}
num_steps <- c(num_steps, length(seq))
}
mean(num_steps)

[Edited on October 19, 2010 at 6:38 PM. Reason : (note, it may not always converge)]

10/19/2010 6:37:36 PM

Good spot, that also pokes a hole in my proof.

Back to the whiteboard!

10/19/2010 6:42:00 PM

^ Thanks for enjoying it. I think it's a great problem. What do you do for work Shadowrunner?

10/19/2010 6:49:34 PM

Simulated with 50,000 iterates, X from 1 to 30, and you get the following:



My proof seemed counter-intuitive, so I'm actually glad there was a problem with it. I haven't done this sort of problem in a long time; no surprise that I'm a bit rusty, but a blow to the ego nonetheless.

Definitely looks like it could be log-linear... fitting the above run gives E(L) ~ 4.244 + 2.981*ln(x). Either of those coefficients look approximately meaningful to you?

10/19/2010 7:27:20 PM

I found where my proof went wrong and spent some more time on this tonight. I've concluded that based on what I've done so far, a) there is no "clean" expression for the answer in terms of elementary functions, and b) finding a closed-form solution (if one exists and whatever it may be, elementary functions or no) is beyond my current abilities. Check my work because conditional probabilities are not my mathematical realm of specialty, but I think this is right:



If so, Mathematica tells me that the summation involves the polygamma function and the Euler-Mascheroni constant, or the extension of harmonic numbers to the half-integers. The probability that the number of steps is 3 gets even worse.

What a great example of a simple problem having a complex answer. I'd be interested in knowing how you came across it.

10/20/2010 4:48:56 AM