Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Ask HN: How many times will this loop run on average?

news.ycombinator.com

Post reply on HN
Print view View original

11–12 of 12 posts

Re: Ask HN: How many times will this loop run on average?

#11

Post by hardlianotion »

aalhour wrote: post #10
hardlianotion wrote: post #8

Earlier quoted context omitted.

I edited my response with an apology! Thanks for checking!

No worries, I think your solution coverges with @Someone's above, if I am not mistaken. You're multiplying the probabilities for all values of j up to i for all values of i.

Yes I am and yes I think it does:

edit - actually, the calculations from the other guy are probability calculations, so this is related to the median. I have given you a mean calculation, which should be related to the average. But you already mentioned that they are close ...

Re: Ask HN: How many times will this loop run on average?

#12

Post by Someone »

aalhour wrote: post #9
Someone wrote: post #5

In C (and your Python conversion), the i part is evaluated each time through the loop, not once at start of the loop to determine the limit. So, it’s 1% that the loop ends at i = 1 , if it takes that hurdle 2% that it ends at i = 2 , if it takes that hurdle 3% that it ends at i = 3 , etc. The calculation is easier if you phrase that this way: It’s 99% that the loop continues at i = 1 , if it takes that hurdle 98% of…

I was aware that the Random function call gets evaluated in Python (and C) every time the loop iterates, I just couldn't imagine the probability distribution myself, I had assumed that all numbers are uniformally distributed but didn't cater for the sums. You're a legend! Now I see it. I wrote the following code to check out your argument and it checks out indeed :thumbs-up: def p(n): total = 1 for i in range(1, n):…

> p(12) sits at 50%, of course it will be the mean!

Technically, “the mean is 12” does not follow at all from “p(12) sits at 50%”.

“p(12) sits at 50%” implies the median (https://en.wikipedia.org/wiki/Median) is 12, and that can differ from the mean (https://en.wikipedia.org/wiki/Arithmetic_mean) of the distribution, and the difference can be quite large.

For example, if that list were to continue

  p(13) = 0.44277496045533604
  p(14) = 0.44277496045533604
  p(15) = 0.44277496045533604
  p(16) = 0.44277496045533604
  p(17) = 0.44277496045533604
  p(18) = 0.44277496045533604
  …
  p(1000) = 0.44277496045533604
  P(1001]) = 0
the about 44% that makes it to 13 also will make it to 1000, and the mean value will be a bit more than 442.77496045533604 (the contribution of that 44.2%)

If, on the other hand, it were to continue

  p(13) = 0.44277496045533604
  p(14) = 0.0
No result would be higher than 13, and the mean would be lower than 12.
Post reply on HN