Imagine, in an alternate universe known as Algorithmopolis, college applications work a little differently. Instead of applying to colleges that you want to get admitted to, colleges send admission letters to students they would want on campus.
Which is great and all, no supplemental essays to write! Yet, in this parallel universe, let’s say these admission letters are very committal. Once you open your acceptance email, you have to either fully commit or fully reject that school on the spot, never receiving another chance to attend the school upon such rejection.
You know you received 100 acceptance letters, but you have no idea which schools sent acceptances. How do you commit to the best school?
In the world of Computer Science, this is known as an optimal stopping problem. When is the optimal, or best, time to stop reading acceptances and commit to a school?
The classical example in the computer science field is quite similar, in a pool of 100 applicants to be your assistant, at what point should you stop interviewing and commit to the best applicant, given the fact that you must reject or accept an applicant on the spot?
This problem sounds downright impossible at first – you’ll either commit too early to a worse school or reject the best schools in search of something better, or have to settle for a worse school in the end. There are 100 letters you have to sift through, the best acceptance has an equal chance to be the first as it does to be the last (and everything in between).
It turns out the answer is surprisingly simple, in fact, it’s a number: 37%. To describe further, you should spend a little over ⅓ of your time, or in our case acceptance letters, seeing what’s out there and noting down the best school you saw in this period. After this searching phase, anything in the remaining 63% that was better than the best school you’ve seen you should commit to.
Let’s quantify: In our 100 letters, the best solution is to open the first 37, with the intent of rejecting them all. Again, there is no definitively best acceptance letter, you wouldn’t know if your #1 school sent you a letter, you can only compare two schools for the better one.
After looking at these 37 letters, let’s assume the “best” school you saw and had to reject was the University of Illinois at Urbana Champaign, not bad! The average person living in Algorithmopolis would be stressed, they just had to decide to reject or accept an offer to study at UIUC! But you know the Computer Science deities and mathematical odds are ever in your favor. 😉
With this in mind, you swallow your fears and trek on. After all, the odds of receiving a better acceptance letter are high. After 10 letters, nothing. 20- same thing. In the 30s, there are a couple, but nothing worth committing to. Nearing the 50 mark, opening and rejecting every school in your path, you stumble across a letter, not your #1 school but definitely a top 5.
Not bad! The normal person would’ve probably committed to UIUC, but you had patience and a bit of luck. (Not to say UIUC is bad! Let’s just say it was your 6th favorite school).
Now, since you’ve been accepted to a very good school, let me explain why the 37% approach is so effective.
Using probability, let’s work from 1 acceptance letter to the 100 that your scholarly self received. With 1 letter, congrats! Since you (probably) want to go to college, accept the first and only letter! Celebrate with some cake.
With 2 letters, you know the best offer for acceptance has a 50/50 chance of being the first letter you read. Why we exemplify the first letter is important, it shows what we miss out on with each subsequent letter we receive.
Going to 3 letters, the chance of that first letter being the best one yet is ⅓, 4 being ¼, and so forth to 100.
Let’s focus on receiving 3 letters before things get too messy. We can either accept the first letter, it is technically the best one we’ve seen yet. Or, hold out until the last letter, being forced to accept it. Both result in many cases where we have to reject the best offer. Our answers lie in the second letter. Applying our 37% rule (roughly), setting a baseline with the first letter and rejecting the offer, and then choosing to accept anything better that follows is surprisingly effective.
The math is interesting here: this strategy of looking for ⅓ of the time, and committing to any school after, raises your odds of choosing the best acceptance letter to 50%. Look at that! You just turned this 3 acceptance letter problem into a 2 letter problem. (With 2 letters you’ll choose the best letter half of the time).
How do your odds rise to 50%, rather than the 33% of just randomly choosing a letter? With the schools, we can visualize them in the order of reading as 3-2-1, with 1 being the best offer. There are 6 possible scenarios here, and applying our rule of 37%, you’ll commit to the best school half of the time (3-2-1, 2-1-3, and 3-1-2), commit too fast to a worse school ⅙ of the time (1-2-3), and be forced to choose the third school ⅓ of the time (1-2-3, 1-3-2).
Look at that! With a little bit of logic, computer science, and wit, you’ve gotten into the best college, given the terrible college application process in Algorithmopolis. Now to worry about moving in….
Inspired by “Algorithms to Live By” (Brian Christian) and Ted-Ex riddle videos.