6 ms·

The underlying mathematical driver of the power of two random choices is a pretty amazing fact about the "n balls into n bins" random experiment. If the balls

The underlying mathematical driver of the power of two random choices is a pretty amazing fact about the "n balls into n bins" random experiment. If the balls are thrown independently and uniformly at random, the most loaded bin will have theta(log n) balls in it (almost certainly). If you instead pick two bins uniformly and independently at random for each ball and throw the ball into the bin which has fewer balls in it so far, then the most loaded bin will have theta(loglog n) balls in it, i.e a massive asymptotic improvement.

littlestymaar 3y ago
[flagged]
- ericpauley 3y ago
  Big Theta describes a both and upper and lower asymptotic bound.
  - littlestymaar 3y ago
    TIL; Thanks!
    - OJFord 3y ago
      It's usually what people mean when they use O, really, colloquially anyway. Theta's like you actually identified the right 'magnitude curve'; what big-O actually says is much weaker, it's only an upper bound. You can say something's O(n) when actually it's constant, etc. But generally we don't, if someone says casually it's O(n) they mean 'and also Omega(n)', i.e. it's Theta(n). (Or at least, it is when talking about something specific - how does this function behave, say. If you talk about needing something to happen linearly then that's a fine use of O - of course you're also happy with constant time if linear is ok.) O is short for Omicron btw, lest you think it's O and then we suddenly went Greek for no apparent reason!
      - lcnPylGDnU4H9OF 3y ago
        I was so confused by this when I learned it after first hearing about big-O notation. Like why are we only talking about the upper bound? Isn't the lower bound at least as, if not more, important? (spoiler: yes) I'm glad you wrote this since it reinforces that understanding.
        Dylan16807 3y ago
        > Isn't the lower bound at least as, if not more, important? (spoiler: yes) I can't think of any situations where I care about the lower bound. I mainly care about the upper bound and the average. Beyond that some percentile statistics are good. And by "the" upper bound, I mean a tight upper bound for it to be useful. But you want a tight lower bound too, or it'll just be O(1) and that has no value at all. And many algorithms have quick exit situations that give them a tiny lower bound and make big-theta invalid. (Unless by "lower bound" you actually mean "lowest/tightest upper bound"?)
        OJFord 3y ago
        Yes what you're describing is theta - both an upper and lower bound (within constant factor). Unless we're talking about 'we need to do this within O(...)', it is generally what we mean (as software engineers, not math/CS academics) even when we say O. Because as you point out, it would be stupid to, say, file a bug report that some function is O(n^100) and too slow if it's also O(n^2) - both are correct (any time the latter is) but it's not really helpful to say the former. Theta effectively says you've found the smallest O.
        Dylan16807 3y ago
        > Yes what you're describing is theta - both an upper and lower bound (within constant factor). No, I'm not. A tight upper bound is only sometimes the same thing as theta. Insertion in a vector or a hash table is best case 1, average case 1, worst case n. Quicksort is average case nlogn, worst case n^2. Bubble sort is best case n, average case n^2, worst case n^2. None of those algorithms are bound above and below by the same function. When Theta exists, it does imply that the upper bound is tight. Which is the feature that's actually important. But Theta talks even more about the lower bound, which rarely matters. Theta is not what you're actually looking for the vast majority of the time. I still can't think of a single situation where I care about "lower bound within constant factor". I care about average time, I care about upper bounds, occasionally I want an algorithm where the time is always exactly the same for a particular n. But not asymptotic lower bound. Preventing smartass answers for "upper bound" is a good goal, but the way you do that is not by switching to Theta.
- orlp 3y ago
  On the very page you linked it is explained what the theta means. Ironic.
  - littlestymaar 3y ago
    No need to be snarky. I simply didn't know the notation and that's why I wanted to know if that was a mistake or intentional.
    - orlp 3y ago
      I didn't mean for it to be snarky, I just found it funny.
    - Dylan16807 3y ago
      > I simply didn't know the notation and that's why I wanted to know if that was a mistake or intentional. The problem is that "aren't you confusing" comes across as very snarky. That's WTF is with the downvotes, and getting upset about those downvotes doesn't help.
      - littlestymaar 3y ago
        > The problem is that "aren't you confusing" comes across as very snarky. Does it really? My bad then, English being hard once again… > and getting upset about those downvotes doesn't help. It did actually, the comment isn't at record breaking level anymore ;)
        Dylan16807 3y ago
        > Does it really? My bad then, English being hard once again… So in a situation like this, "are you confusing" sounds somewhat presumptuous, but "aren't you confusing" sounds like you're quite sure you're right and they're wrong. "are you maybe confusing" is probably the best way to use that phrasing, but better still would be "do you mean", so What's “θ” in your comment? Do you mean the letter “O” in “big O notation”[1]? Though ideally when you're linking a page like that you ctrl+F it first.
mjb 3y ago
The balls-into-bins problem comes up often in distribute systems engineering, and so it's super important to have the right intuition. I think a lot of people come in to the space assuming that random balls-into-bins is much more even than it really is (and so underestimating the value of better-than-random placement). Another interesting example is hash-based partitioning of data. It doesn't spread data out nearly as evenly as one might expect! (I wrote a blog post about that too: https://brooker.co.za/blog/2018/01/01/balls-into-bins.html https://brooker.co.za/blog/2018/01/01/balls-into-bins.html)
- nyrikki 3y ago
  I have found remembering that both the law of large numbers and the central limit theorem are dependent on the independent and identically distributed assumption. As an example, many computing systems are Markovian, which is memoryless with an exponential distribution. So the second part of I.I.D. doesn't hold. But may be close enough for your needs.
  - mjb 3y ago
    However, in many real systems the aggregate behavior follows the asymptotic trend of the central limit theorem even though the underlying distributions may not fit the strict requirements.
    - nyrikki 3y ago
      Yes, I always start with the IID, but try watch for evidence that those assumptions need to change. Too many convenient properties are lost once you lose IID to prematurely drop it.

littlestymaar 3y ago

[flagged]

ericpauley 3y ago
Big Theta describes a both and upper and lower asymptotic bound.
- littlestymaar 3y ago
  TIL; Thanks!
  - OJFord 3y ago
    It's usually what people mean when they use O, really, colloquially anyway. Theta's like you actually identified the right 'magnitude curve'; what big-O actually says is much weaker, it's only an upper bound. You can say something's O(n) when actually it's constant, etc. But generally we don't, if someone says casually it's O(n) they mean 'and also Omega(n)', i.e. it's Theta(n). (Or at least, it is when talking about something specific - how does this function behave, say. If you talk about needing something to happen linearly then that's a fine use of O - of course you're also happy with constant time if linear is ok.) O is short for Omicron btw, lest you think it's O and then we suddenly went Greek for no apparent reason!
    - lcnPylGDnU4H9OF 3y ago
      I was so confused by this when I learned it after first hearing about big-O notation. Like why are we only talking about the upper bound? Isn't the lower bound at least as, if not more, important? (spoiler: yes) I'm glad you wrote this since it reinforces that understanding.
      - Dylan16807 3y ago
        > Isn't the lower bound at least as, if not more, important? (spoiler: yes) I can't think of any situations where I care about the lower bound. I mainly care about the upper bound and the average. Beyond that some percentile statistics are good. And by "the" upper bound, I mean a tight upper bound for it to be useful. But you want a tight lower bound too, or it'll just be O(1) and that has no value at all. And many algorithms have quick exit situations that give them a tiny lower bound and make big-theta invalid. (Unless by "lower bound" you actually mean "lowest/tightest upper bound"?)
        OJFord 3y ago
        Yes what you're describing is theta - both an upper and lower bound (within constant factor). Unless we're talking about 'we need to do this within O(...)', it is generally what we mean (as software engineers, not math/CS academics) even when we say O. Because as you point out, it would be stupid to, say, file a bug report that some function is O(n^100) and too slow if it's also O(n^2) - both are correct (any time the latter is) but it's not really helpful to say the former. Theta effectively says you've found the smallest O.
        Dylan16807 3y ago
        > Yes what you're describing is theta - both an upper and lower bound (within constant factor). No, I'm not. A tight upper bound is only sometimes the same thing as theta. Insertion in a vector or a hash table is best case 1, average case 1, worst case n. Quicksort is average case nlogn, worst case n^2. Bubble sort is best case n, average case n^2, worst case n^2. None of those algorithms are bound above and below by the same function. When Theta exists, it does imply that the upper bound is tight. Which is the feature that's actually important. But Theta talks even more about the lower bound, which rarely matters. Theta is not what you're actually looking for the vast majority of the time. I still can't think of a single situation where I care about "lower bound within constant factor". I care about average time, I care about upper bounds, occasionally I want an algorithm where the time is always exactly the same for a particular n. But not asymptotic lower bound. Preventing smartass answers for "upper bound" is a good goal, but the way you do that is not by switching to Theta.
orlp 3y ago
On the very page you linked it is explained what the theta means. Ironic.
- littlestymaar 3y ago
  No need to be snarky. I simply didn't know the notation and that's why I wanted to know if that was a mistake or intentional.
  - orlp 3y ago
    I didn't mean for it to be snarky, I just found it funny.
  - Dylan16807 3y ago
    > I simply didn't know the notation and that's why I wanted to know if that was a mistake or intentional. The problem is that "aren't you confusing" comes across as very snarky. That's WTF is with the downvotes, and getting upset about those downvotes doesn't help.
    - littlestymaar 3y ago
      > The problem is that "aren't you confusing" comes across as very snarky. Does it really? My bad then, English being hard once again… > and getting upset about those downvotes doesn't help. It did actually, the comment isn't at record breaking level anymore ;)
      - Dylan16807 3y ago
        > Does it really? My bad then, English being hard once again… So in a situation like this, "are you confusing" sounds somewhat presumptuous, but "aren't you confusing" sounds like you're quite sure you're right and they're wrong. "are you maybe confusing" is probably the best way to use that phrasing, but better still would be "do you mean", so What's “θ” in your comment? Do you mean the letter “O” in “big O notation”[1]? Though ideally when you're linking a page like that you ctrl+F it first.

mjb 3y ago

The balls-into-bins problem comes up often in distribute systems engineering, and so it's super important to have the right intuition. I think a lot of people come in to the space assuming that random balls-into-bins is much more even than it really is (and so underestimating the value of better-than-random placement). Another interesting example is hash-based partitioning of data. It doesn't spread data out nearly as evenly as one might expect! (I wrote a blog post about that too: https://brooker.co.za/blog/2018/01/01/balls-into-bins.html https://brooker.co.za/blog/2018/01/01/balls-into-bins.html)

nyrikki 3y ago
I have found remembering that both the law of large numbers and the central limit theorem are dependent on the independent and identically distributed assumption. As an example, many computing systems are Markovian, which is memoryless with an exponential distribution. So the second part of I.I.D. doesn't hold. But may be close enough for your needs.
- mjb 3y ago
  However, in many real systems the aggregate behavior follows the asymptotic trend of the central limit theorem even though the underlying distributions may not fit the strict requirements.
  - nyrikki 3y ago
    Yes, I always start with the IID, but try watch for evidence that those assumptions need to change. Too many convenient properties are lost once you lose IID to prematurely drop it.