Although I was absolutely terrible in my theoretical computer science classes, I did manage to pick up some neat little tricks. I always enjoy seeing them crop up in meatspace, oftentimes in very unexpected applications.

Probability theory is exteremely important in computer science. As a student, I was somewhat surprised by this. After all, computers are extremely precise – they follow the instructions you give them (aka code) exactly, every time. So why is probability theory, which explores the world of chance, important for machines of precision? As it turns out, there are several sets of problems for which probability is extremely useful. For example, there is a class of problems that are so complex that they are impossible to solve, even for computers. Instead, comptuers must take their best guess. Probability is useful for running cost-benefit analyses on potential solutions.

Another “flavor” of problem concerns resource contention. Anytime you have more demand than availability for a resource, probabilty can help. For example, pobability allows Google to distribute millions of requests among a series of computers such that no one computer melts under the pressure.

One classic problem is the “balls in bins” problem which is a generalization of a certain case of discrete probability1. I like to think of it like the game of Plinko from the Price is Right.

the game of Plinko

In this game, you put chips into the top of the board. They bounce off the pegs randomly before landing a bucket at the bottom of the board. As it turns out, with some fancy math, for any given number of chips we can actually calculate (with a high degree of confidence) the maximum number of Plinko chips that will land in any one slot.

This is really useful! If you’re a computer programmer and you know that your comptuers all have 16GB of memory, you can use this formulation to essentially guarantee that none of your computers will run out of space.

It turns out this formalization isn’t useful just for computer programmers, but in the real world as well. I just got back from spending some time in Colombia (thanks, coronoavirus!). In the largest cities, the traffic and smog is got bad that they instituted a novel program to reduce traffic. It’s called “pico y placa”, literally peak (hour) and (license) plate in English. It is a series of restrictions that determines what days you can drive your car based on the last digit on your license plate. In this scenario, there are more cars than there is space on the road. Resource contention! The cars are our bins and the days of the week are our buckets. Pretty neat!

Here’s another more timely example. Right now, there is a pretty dire shortage of surgical masks. In South Korea, they’ve instituted a program where everyone will be able to buy a mask for an affordable price – but only one a specific day each week. Your specific “mask day” is determined by the last digit of your birth year.

So in the future, no matter what your business or occupation is, whenever you hear “limited resources” think of “balls and bins”!

  1. If you’d like to learn more of the theory behind balls and bins, I’d recommend the course notes (and associated lectures) from CS 70 at UC Berkeley: 1, 2 ↩