At work I recently came upon an interesting problem: Upon a new user request we have to make a live decision, but making that live decision involves a lot of data. The described solution does not work for our real use case, but I think it can still be a useful approach in other scenarios. Let’s look at the problem in abstract terms. It’s a common approach in computer science to focus on the key problem.

Let’s assume we have a huge urn with differently colored marbles inside. The number of colors we can use is fixed (for example green, blue, red, yellow). We have no control over the addition and removal of marbles. New marbles can be added at any time, existing marbles can be removed at any time.

Newly arriving marbles are uncolored. When a new marble arrives, we must give it a color and put it into the urn. Our goal is to keep the number of marbles per color equally distributed. How do we choose which color a newly arriving marble should get?

Counting all Marbles in the Urn

The simplest approach (which doesn’t scale well) would be to go through the whole urn and count all marbles. Once all colors were counted, we know which color has the fewest marbles. We’d then color the new marble in that color. To make sure that the world does not change while we’re counting, we’d set up a mutex. But since counting all marbles in the urn is quite slow, the mutex would lock for very long.

As a simple improvement we could say, let’s just do the count every 100 times. It’s not so bad if we’re wrong for a while, is it? And once we do the re-count, we can fix our intermediate mistakes. However, that does not solve the long lock. Every 100 additions, we’d still set up our mutex, go through the whole urn, and keep the lock for quite some time.

Keeping a Record of all Marbles

If we can recognize all additions and all removals of marbles, we could also keep a record of the counts for all colors. Whenever a marble gets added, we add one to the color we choose for that marble. And when a marble gets removed, we deduct one from that color.

In practice, such side records can be annoying, because in error situations they can get out of sync with the real data. We’d then also need some strategy to bring them back in sync.

If we don’t get informed about deletions of marbles, this strategy is not an option at all.

Taking a Sample of Marbles in the Urn

What if we don’t count each and every marble? If we can guarantee that we get a random selection of the marbles, we could just choose a few marbles and look at their colors. That’s basically what election forecasts are doing. They’re not asking each and every voter how they’d vote, but just a small number - usually around 1000.

Sounds like an interesting idea. However, with that approach we’re in the realm of probability theory. And probability means we’re not 100% accurate. Can we make some assertion about the amount of error we’ll likely see?

According to my understanding, we can simplify the problem if we only look at a single color. Let’s say we’ll only look at the green marbles. A marble is either green or not green. We pick a marble, is it green? We pick another marble, is it green? And so on. Now we’re talking about a binomial distribution. A binomial distribution has a parameter \(p\) describing the likelihood with which it yields success, in our case the likelihood of a marble being green.

A Short Detour to Coins

Binomial distributions are often explained using a coin, so let’s think about that for now. A stranger gives us a coin and we want to find out whether it’s a fair coin (lands on heads and tails the same amount of times) or not (heads or tails more likely than the other). What are we going to do? We’ll probably toss the coin a few times and see what happens.

On the first two tosses we get tails. Can we say that the coin is unfair? Probably not, even with a fair coin there is a 25% chance to get tails two times when we toss it two times. But how often do we have to toss it to get a rough understanding of the fairness of the coin? To be more precise: The coin is a fair coin if we can say (with high enough certainty) that the parameter \(p\) for the binomial distribution of the coin is 0.5.

That’s where confidence intervals come into play. Confidence intervals of binomial distributions have their own Wikipedia page, so they seem a bit complex. But for my use case I didn’t have to dive into all the details.

The gist of it is that a confidence interval tells you (up to a defined certainty) in which range the real parameter \(p\) of a binomial distribution lies, if all you can do is take a few samples and look at them.

So, back to our coin. If we toss it a few times, we could use one of the confidence interval formulas to calculate the band inside which the real parameter \(p\) probably lies. If that band includes 0.5 we can call the coin fair. If the band does not include 0.5, we’d call the coin unfair.

One important point to remember is that the confidence interval only gives you the real answer up to some certainty. Common values are 95% certainty or 99% certainty. What if you want 100% certainty? Then you’re back to counting all items. In theory, you could choose 100% certainty for the confidence interval, but then you’d just get a confidence interval spanning all possible values from 0 to 1 (yes, the parameter \(p\) is definitely somewhere between 0 and 1, but that does not help us).

Let’s make an example. Let’s assume we have a very unfair coin, it only lands on heads 1% of the time. We toss it 100 times and get 50 heads and 50 tails. Is this possible? Certainly! “How?”, you’re asking, “it should only land on heads 1% of the time”. We’ve only observed 100 tosses. Maybe the next 4900 tosses all yield tails. Then over 5000 tosses the coin behaved exactly as expected, 1% heads. We were just unlucky that all the heads were within the first few tosses. Possible, but very unlikely.

Confidence Intervals for Distribution of Marbles

We can use this for our urn of marbles. Inside the huge urn of marbles, there’s a certain amount of green marbles. We do not know how many green marbles there are. But we can take a sample and check how many of those are green. We can then use the confidence interval formulas to find out what the real amount of green marbles inside the urn probably is.

“Why all the fuss?”, you might be asking, “if inside a sample of 1000 randomly selected marbles, 300 are green, then there are probably 30% green marbles in the urn”. The nice thing about the confidence interval is that it lets us calibrate the error. The question is, how many marbles should we choose from the urn? Ten, one hundred, one thousand, one million?

Thanks to the confidence interval formulas we can find out what amount of error we’ll likely get if we take a sample of only ten marbles (huge error) or one million marbles (very small error, but far too much work).

The error term of the Wald Interval is:

\[\frac{z_\alpha}{\sqrt{n}} \sqrt{\hat{p}(1 - \hat{p})}\]

\(z_\alpha\) itself is another term to be calculated, but for the common situation where we want 95% certainty, it is \(z_\alpha = 1.96\). \(\hat{p}\) is the observed likelihood from our samples. If we have four different colors, we’d assume that \(p\) and thus usually also \(\hat{p}\) is probably around 0.25. If I’m not wrong, the worst case scenario for the error is when \(\hat{p}\) is 0.5.

Let’s use that worst case scenario. Then with only 10 samples, the formula gives us

\[\frac{1.96}{\sqrt{10}} \sqrt{0.5 * 0.5} = 0.155\]

Knowing the correct value of \(p\) only with plus/minus 15.5 percentage points does not sound very convincing. We might estimate it at 30%, while in reality it’s 45%. However, the numbers get better quite quickly. At 1000 samples we’re already at an error term of plus/minus 1.5 percentage points.

And another important takeaway: The error term is completely independent of the actual data size. Whether we have a million or a billion marbles in our urn, it does not matter. It always suffices to take a sample of 1000 marbles and we’ll get a quite good estimate.

What about the unlikely situations

But what if the 95% certainty chosen for our confidence interval does not hold true? What if we chose 1000 marbles and our confidence interval says that the amount of green marbles is somewhere between 30% and 33%, but in reality it’s only 1%? This can happen.

I didn’t do a formal analysis on this, but I think for the stated problem this can be ignored. If a new marble arrives and we have to color it, even the cases outside the 95% certainty range are not all completely wild guesses. Most guesses outside the certainty range sit just on the edge, so are okay guesses on their own.

Only in very rare cases would we get a completely wrong guess about the current color distribution. Maybe the amount of green marbles is 1% and yellow marbles are at 40% (and the other colors somewhere in between), but we’re getting a guess of 30% for green marbles, and only 20% for yellow marbles. Then in this very rare situation we’d color the marble in the wrong color - for one single time. And the next thousands of times we’d get more accurate guesses and make the right choice.

Outro

In this blog post we’ve seen how we can use a random sample to estimate data distribution without looking at all the data. By taking a random sample of the data we can reduce the amount of work. Confidence intervals allow us to make an elaborate choice on the number of items we have to select.

One side note: I think in the marbles-in-urn representation, sampling presents itself as a solution quite easily. The real world problems might look a bit different. So keep a close eye on your problems and try to find out to which “standard” problems you can reduce them.

I do not maintain a comments section. If you have any questions or comments regarding my posts, please do not hesitate to send me an e-mail to blog@stefan-koch.name.