3 ms·

If you randomly draw z numbers from a bucket of numbers from 0 to 10000 times x, the gaps will differ because there is no mechanism that would make some number

If you randomly draw z numbers from a bucket of numbers from 0 to 10000 times x, the gaps will differ because there is no mechanism that would make some number with close neighbors less or more likely to be drawn than any other remaining number. It’s only once your supply of numbers runs low that differences will start to equalize, reaching 1 when you have exhausted your supply. Besides, the author isn’t really making an argument. They are giving you actual data showing the differences to the next lowest number. It’s hard to argue with that.

bawolff 4y ago
Right, they said the absolute worst case outlier was a gap about 100x smaller than average. Which i guess depends on your views, but i would say that's not bad. > the gaps will differ because there is no mechanism that would make some number with close neighbors less or more likely to be drawn than any other remaining number. When a new article is inserted, there is a higher probability it will be inserted in a large gap than a small gap, so it should balance out. I suppose you're right,i am responding to an implied criticism to the randomness method that the author didn't make. They just offered it as explanation.
- IfOnlyYouKnew 4y ago
  > When a new article is inserted, there is a higher probability it will be inserted in a large gap than a small gap, so it should balance out. That’s a good point and I’m not entirely sure why it (appears to) not work that way. Maybe it’s because that interval has a higher likelihood, but there is no preference for numbers towards the middle, that would dissect it into (roughly) equal parts?
  - bawolff 4y ago
    I think it is working. The worst case was 50x less likely than the average. That sounds like a lot when stated like that, but its really not when taken in the context of ~6.5 million articles. More interesting question would be what is the standard deviation (of gap size), not what is the worst outlier
    - mormegil 4y ago
      When this topic came up the last time, I plotted the probability distribution. It was far from 50x, the range was several orders of magnitude, which seems to be the correct behavior. See https://gist.github.com/mormegil-cz/84d0cc34eb5f1234be8966f7c5498d9c https://gist.github.com/mormegil-cz/84d0cc34eb5f1234be8966f7...
- SiempreViernes 4y ago
  The gap size is simply the difference between two (presumably) uniform random numbers, which is a distribution you can just look up. Differences around zero is actually preferred: https://mathworld.wolfram.com/UniformDifferenceDistribution.html https://mathworld.wolfram.com/UniformDifferenceDistribution....
  - tgb 4y ago
    That’s only the case if there are only two articles. In general you’d be looking at the difference of two order statistics (of the uniform distribution). You could probably approximate this quite well as a Poisson process though (since there are so many articles) and so have exponentially distributed gap size.
- dfan 4y ago
  Think of it this way. The article presents a random-gap list with only five entries, and it looks terrible; the most common page occurs 9 times as often as the least common. Now think about a random-gap list with five million entries. With that many entries, will the gaps balance out? In the best case, five of them end up in the range from 0 to 1 millionth, five of them end up in the range from 1 millionth to 2 millionths, etc. But we've already seen what it looks like to have five uniform random numbers in a range (whether it's big or small doesn't matter); the gaps tend to be really varied. So we're going to get this sort of imbalance between gap sizes (viewed as a ratio) no matter how many entries we insert. One other thought experiment: the article mentioned a page with a gap size of one billionth. How many pages will it take for that to balance out so that page doesn't have an unusually small gap any more? How many pages does Wikipedia have? (This is similar to the reason that infinite space packed with marbles has the same packing density as infinite space packed with bowling balls.)

bawolff 4y ago

Right, they said the absolute worst case outlier was a gap about 100x smaller than average. Which i guess depends on your views, but i would say that's not bad. > the gaps will differ because there is no mechanism that would make some number with close neighbors less or more likely to be drawn than any other remaining number. When a new article is inserted, there is a higher probability it will be inserted in a large gap than a small gap, so it should balance out. I suppose you're right,i am responding to an implied criticism to the randomness method that the author didn't make. They just offered it as explanation.

IfOnlyYouKnew 4y ago
> When a new article is inserted, there is a higher probability it will be inserted in a large gap than a small gap, so it should balance out. That’s a good point and I’m not entirely sure why it (appears to) not work that way. Maybe it’s because that interval has a higher likelihood, but there is no preference for numbers towards the middle, that would dissect it into (roughly) equal parts?
- bawolff 4y ago
  I think it is working. The worst case was 50x less likely than the average. That sounds like a lot when stated like that, but its really not when taken in the context of ~6.5 million articles. More interesting question would be what is the standard deviation (of gap size), not what is the worst outlier
  - mormegil 4y ago
    When this topic came up the last time, I plotted the probability distribution. It was far from 50x, the range was several orders of magnitude, which seems to be the correct behavior. See https://gist.github.com/mormegil-cz/84d0cc34eb5f1234be8966f7c5498d9c https://gist.github.com/mormegil-cz/84d0cc34eb5f1234be8966f7...
SiempreViernes 4y ago
The gap size is simply the difference between two (presumably) uniform random numbers, which is a distribution you can just look up. Differences around zero is actually preferred: https://mathworld.wolfram.com/UniformDifferenceDistribution.html https://mathworld.wolfram.com/UniformDifferenceDistribution....
- tgb 4y ago
  That’s only the case if there are only two articles. In general you’d be looking at the difference of two order statistics (of the uniform distribution). You could probably approximate this quite well as a Poisson process though (since there are so many articles) and so have exponentially distributed gap size.
dfan 4y ago
Think of it this way. The article presents a random-gap list with only five entries, and it looks terrible; the most common page occurs 9 times as often as the least common. Now think about a random-gap list with five million entries. With that many entries, will the gaps balance out? In the best case, five of them end up in the range from 0 to 1 millionth, five of them end up in the range from 1 millionth to 2 millionths, etc. But we've already seen what it looks like to have five uniform random numbers in a range (whether it's big or small doesn't matter); the gaps tend to be really varied. So we're going to get this sort of imbalance between gap sizes (viewed as a ratio) no matter how many entries we insert. One other thought experiment: the article mentioned a page with a gap size of one billionth. How many pages will it take for that to balance out so that page doesn't have an unusually small gap any more? How many pages does Wikipedia have? (This is similar to the reason that infinite space packed with marbles has the same packing density as infinite space packed with bowling balls.)