Summary

Algorithms to live by backed by computer science research. Balance between exploiting current skills and exploring new skills, adding spontaneity to your life and practicing regret minimization. Maximize throughput by maintaining the minimum acceptable level of responsiveness to reduce thrashing. Be intentional about how your brain caches information. When predicting, use Bayes’ rule to apply priors with the correct underlying distributions. Apply Occam’s razor to keep things simple and constraint relaxation to solve hard problems. Live a life of finite patience and infinite mercy with exponential back off (AIMD).

Key Takeaways

• Add randomness, spontaneity to your life

Notes

Introduction

• Algorithm: a finite sequence of steps used to solve a problem
• How to deal with uncertainty and live life

1: Optimal stopping

• Optimal stopping: when to look and when to leap
• Secretary problem: choosing the best option among pool of applicants
• 37% rule: Look at 37% of pool before leaping at next best option
  • 37% chance of being global best
• Assumes known pool size, cannot go back, option will always accept / work out
• If immediate proposals 100% but fallback proposals 50%, look at 61% before leap
• Opportunity cost of looking / waiting
• Eg. parking, looking for gas, restroom
• Optimal stopping doesn’t always work in practice, eg. triple or nothing
• Bias: people tend to stop early (4/5)

2: Explore / exploit

• Exploit explore tradeoff: balance between current skills and trying new skills
• Multi-arm bandit problem: resources allocated over choices with unknown value
• Eg. slot machines, drug discovery
• Can also do with unlimited time but with discount rate (ie. limited time at constant)
• Gittins index: stochastic method solution
• Prefer the unknown
• Regret minimization: Jeff Bezos + internet
• A/B testing
• Bias: people tend to over-explore
• No optimal algorithm when probabilities change (eg. in the real world)
• Be sensitive to how much time you have left

3: Sorting

• Sorting theory: most important use of computer science (eg. Google search)
• Best is O(n•log(n)) no matter what
• Bucket sort O(m•n)
• In practicality, need to consider trade off of time spent sorting versus leveraging sort
• Can apply to sports tournaments
  • Need n•log(n) games to rank fully
• Assumptions:
  • Noisy comparisons (round robin)
  • Involuntary comparisons (online heads-up poker)
  • Race vs fight comparison (1-1 v all)
• Known status results in less conflict: quantify status

4: Caching

• Caching theory: minimizing cache faults by evicting info we won’t need for longest time
• Belady’s anomaly: LIFO cache (LRU)
• Spatial caching from microchip to internet scale (CDN) to distribution (Amazon)
• Reduce friction on multiple levels
• Noguchi filing system: simple stack, not maintaining explicit sort
• Forgetting curve: how we tend to forget
• Mind has essentially infinite capacity but finite amount of time to search
• Cognitive decline is actually just result of storing, having to sift through more info

5: Scheduling

• Scheduling theory: how to schedule known work to known set of machines
• Single-machine scheduling: order is irrelevant, thus goals most important
• Strategies:
  • Min procrastination (due date)
  • Min # overdue tasks (Moore’s)
  • Min # of tasks (small first)
  • Weighted (density of task value)
• Moore’s algorithm: if out of time, discard largest obligation that will be past due
• Pre-crastinating: hastening trivial matters to avoid dreaded highest weight task
• Priority inheritance: to prevent priority inversion, small blocking tasks should be prioritized over medium tasks
• Many scheduling problems are intractable: only 9% have proven optimal algorithm
• Preemption: become tractable again when tasks are interruptible
• Weighted shortest processing time
• Switching costs + thrashing
• Responsiveness vs throughput
• Stay on a task as long as possible while maintaining the minimum level of responsiveness
• Batching / interrupt coalescing

6: Bayes’ rule

• Rule of succession: p = (s + 1) / (n + 2)
• Bayes’ rule: combining preexisting beliefs (priors) with observed evidence
• Copernican principle: odds are you’re “in the middle of it” (eg. Berlin Wall)
  • Bayes’ rule with an informative prior
  • Uninformative prior: don’t know anything about time span
• Power law vs normal distribution vs invariant / Erlang / memory-less distribution
• ↑ know what you’re dealing with to inform estimation using Bayes’ rule
• Bias: generally good at intuiting except when distribution is unknown
• Marshmallow study and trustworthy adults
• Our experiences skew our priors (eg. the news)

7: Overfitting

• Overfitting: what you know vs don’t know
• Overfitting to objective / test metrics rather than true underlying goal / skill
• Occam’s razor: most likely explanation is the most simple explanation
• Regularization: complexity penalty
  • Eg. ML lasso, language, memory
• Keep it simple, don’t get bogged down in the details

8: Relaxation

• Constraint relaxation: make the problem tractable by relaxing constraints
  • Eg. traveling salesman, spanning tree
• Lagrangian relaxation: constraints become penalties to make problem tractable
• Don’t be afraid to break some rules to make the goal more achievable

9: Randomness

• “A statistic can only tell us part of the story, obscuring any underlying homogeneity”
• Bloom filter: approximate to save time
• Randomness / chance is beneficial (SGD)
• Randomness as origin of creativity
• Add randomness, spontaneity to your life

10: Networking

• Exponential back off: solution to sending packets in a busy network
• ↑ “Finite patience and infinite mercy”
• TCP flow control: sawtooth back off (AIMD)
• Peter principle: “every employee tends to rise to his level of incompetence”
  • Employee rises in org until bad at role
  • Solution: AIMD
• Dynamic hierarchy: sawtooth promotion
• Back channeling: active listening helps
• Dropped packets prevents bloated buffers
• ↑ essentialism, selective focus

11: Game theory

• Nash equilibrium: at least one in every two-player game
• Prisoners’ dilemma, tragedy of the commons
• Price of anarchy: difference between dominant strategy and Nash equilibrium
• Government: Need centralization to manage situations w. high price of anarchy
  • ↑ everyone must be on equal terms/ values: religion, rules, enforcement
• Trees as example of cooperation not existing in wild: trunk is a waste
• Dutch vs English vs Vicrey auction

Conclusion

• Computational kindness: lower others’ cognitive burden to reach decisions