Skip to content

Algorithms to Live By

Introduction

Long before algorithms were ever used by machines, they were used by people. - Algorithm (Origin ~ al-Khwarizmi, persial mathematician)

Optimal Stopping

When to Stop Looking.

The Apartment Hunter's Dilemma

  • Imagine you are searching for an apartment.
  • The booming techg sector and tight zoning laws limiting new construction have conspired to make the city just as expensive as any other big city.
  • New listings go up and come down in minutes.
  • This creates a new problem, you can take the apartment you are currently looking at, forsaking all others, or you can walk away, never to return.
  • How do you make a satisfying decision for an apartment to choose?
Getting a Baseline
  • You will need a baseline to judge the current apartment.
  • To get the baseline you will need to go through a certain amount of apartments to get an estimate i.e. our baseline.
  • The more information you gather, the better you will know the right opportunity when you see it - but the more likely you are to have already passed it by.
  • So what do you do? How do you make informed choices when the very act of informing it jeopardizes the outcome?
Looking and Leaping
  • How long to look for and when to leap at an option.
  • The Answer : 37%
    • If you want the best odds of getting the best apartment, spend 37% of your apartment hunt without committing, exploring options.
    • After the 37% of research is done, now you form a baseline based on what you have already seen.
    • Now, be ready to commit to the first place that beats whatever you have already seen.

The Secretary Problem

  • "In any optimal stopping problem, the crucial dilemma is not which option to pick, but how many options to even consider."
  • Problem Statement
    • Imagine you are interviewing a set of applicants for the position of a secretary.
    • Your goal is to maximise the chance of hiring the single best applicant in the pool.
    • You interview applicants in random order, one at a time.
    • You can decide to offer job to an applicant at any point and they are guaranteed to accept, terminating the search.
    • If you pass over an applicant, they are gone forever.
  • Similar to the 'Apartment Hunter's dilemma'
Intuition / Thoughts
  • "In your search for a secretary, there are two ways you can fail: stopping early and stopping late"
    • Stopping early leaves the best applicant left undiscovered
    • Stopping late ends up in you holding out for a better applicant that does not exist.
  • If your aim is to find the best applicant, it's clear that as you go through interviews, you shouldn't consider hiring someone who is not the best so far.
  • Simply being best till now is not enough, the first candidate will always win then.
  • the rate at which we encounter “best yet” applicants will go down as we proceed in our interviews."

    - the second applicant has a 50/50 chance of being the best we’ve yet seen, but the fifth applicant only has a 1-in-5 chance of being the best so far