Lecture V - Randomness

Programming: Everyday Decision-Making Algorithms

Author
Affiliation

Dr. Tobias Vlćek

Kühne Logistics University Hamburg - Winter 2024

Understanding Randomness

Randomness

Question: What comes to your mind when you think of randomness?

. . .

Casino

Lottery

Shuffling cards

Algorithms

Cryptography

Genetic mutations

Why Randomness Matters

Question: What’s the opposite of randomness?

. . .

  • Determinism
  • Predictability
  • Consistency

. . .

  • Boredom?

Discovery by Randomness

Question: How would you test if a pair of dice is fair?

. . .

  • Send the dice to a lab to check weight and balance

. . .

  • Roll the dice many times
  • Check if the outcomes are uniformly distributed
  • Compare observed frequencies to expected frequencies

Dice Rolls

Using Randomness

  • Randomness is a fundamental aspect of the world
  • It can be used for discovery
  • Randomness is used to model uncertainty
  • It is used to explore solutions and avoid bias

. . .

Important

Even in computer science, randomness is not just about generating random numbers!

Randomness in the World

Randomness and Everyday Life

Question: Where do you encounter randomness in daily life?

Social Life

  • Dating apps use randomized matching within preferences
  • Random encounters that lead to friendships
  • Random opportunities leading to career changes
  • Breaking ties through coin tosses

Entertainment Industry

  • Pokémon’s “random” encounters are weighted by rarity
  • Loot systems: Rare items have controlled drop rates
  • Chess AI introduces randomness to feel more human-like
  • Spotify’s shuffle is deliberately less random to feel natural
  • TikTok uses controlled randomization to optimize discovery

Cryptography

  • Coin miners solve cryptographic puzzles using guesses
  • PW generators balance randomness and memorability
  • correct-horse-battery-staple is secure
  • Tr0ub4dor&3 is less secure despite looking complex
  • Modern encryption uses random numbers

Data Science

  • Weather forecasting uses randomness for uncertainty
  • Stock algorithms add randomness to avoid patterns
  • Self-driving cars add randomness for natural-feeling
  • Random sampling in research for unbiased results

. . .

Note

Randomness is everywhere around us!

Randomness and Computer Science

Randomness in Computer Science

  • Fundamental concept in computer science
  • Helps solve “hard” problems efficiently
  • Often faster than deterministic approaches
  • Trade-off: Optimal vs. “Good Enough” solutions

. . .

Important

Sometimes a quick “good enough” solution is better than waiting for the perfect one.

Types of Randomness

Question: Difference between true and pseudo-randomness?

. . .

True Randomness

  • Physical phenomena
  • Atmospheric noise
  • Radioactive decay
  • Quantum effects

Pseudo-randomness

  • Deterministic algorithms
  • Seed-based generation
  • Repeatable sequences
  • Good enough for most uses

Limits of Computation

Question: How many possible combinations exist in a shuffled deck of cards?

import math
print(math.factorial(52))
80658175170943878571660636856403766975289505440883277824000000000000

. . .

Important

Computing and evaluating all possible combinations is not feasible!

Addressing Computational Limits

Question: Anybody ever heard of “Monte Carlo methods”?

. . .

  • Developed in the 1940s for nuclear weapons research
  • Nuclear fission chain reactions were too complex
  • Helped to evaluate the probabilities of different outcomes
  • Named after Monaco’s famous casino

. . .

Question: How could we estimate π?

Estimating π

Decision Making

Travel Itinerary

Question: How and in which order would you visit 10 cities by plane with minimal total distance?

import math
print(math.factorial(10))
3628800

. . .

Question: What could be a strategy?

Brute Force

  • Try every possibility
  • Total possible routes: 10! = 3,628,800
  • Guaranteed to find best solution
  • If each check takes 1ms: 1 hour to check all routes

. . .

Question: What could be the problem with this approach?

Time and Space Requirements

  • For 20 cities: 20! = 2.4 quintillion routes
  • Would take 77 billion years at 1ms per check!
  • Time complexity grows factorially
  • Memory requirements increase with problem size

. . .

Important

Not feasible for real-world problems!

Greedy Algorithm

  • Example: Always picking shortest next flight
  • Make locally optimal choices at each step
  • Never backtracks or reconsiders past decisions
  • Fast execution & simple to implement
  • Can perform poorly on complex problems

Hill Climbing

  • Iteratively improve solution by making small changes
  • Like climbing in fog, can only see immediate surroundings
  • Don’t know if higher peaks exist elsewhere
  • Can get stuck in local optima
  • No guarantee of finding global best optima

. . .

Question: How would you escape a local optimum?

Simulated Annealing

  • Make random changes and accept improvements
  • Sometimes accept worse solutions
  • Gradually become more selective

. . .

Question: Why accept worse solutions sometimes?

. . .

  • Randomness helps to escape local optima
  • Balances exploration vs. exploitation

Simulated Annealing Animation

Traveling Salesman

Randomness and Society

Thought Experiment

What’s more important for a society?

. . .

Freedom

  • Individual choice
  • Personal responsibility
  • Market-driven

Equality

  • Shared resources
  • Social safety nets
  • Regulated systems

. . .

Question: Any problem with this question?

Veil of Ignorance

You might randomly be:

  • Any gender identity and economic status
  • Any health condition and intelligence level
  • Any cultural background and religious belief

. . .

Question: If you didn’t know who you’d be born as, what kind of society would you design?

Key Considerations

  • Individual stories: Powerful but potentially misleading
  • Statistics: Comprehensive but can miss nuance
  • Hidden diversity: Important subgroups may be overlooked
  • Small policy changes can have cascading effects

. . .

Important

But that’s not all! We also need to measure success and failure!

Measuring Success

  • Mean happiness: Average well-being
  • Total happiness: Utilitarian approach
  • Median happiness: Focus on the middle class
  • Minimum happiness: Protecting the most vulnerable

. . .

Question: What could be the problem with these measures?

Idea: Random Sampling

  • Randomly select a subset of the population
  • Gather diverse perspectives from the sample
  • Better understand needs of population
  • Reduce selection bias and improve accuracy

. . .

Question: What is a selection bias?

Selection Bias

Definition: Selection bias occurs when the sample data you’re analyzing isn’t truly representative of the population you’re trying to study.

. . .

Famous Example

During WWII, engineers studied returning planes to determine where to add armor. Initially, they focused on areas with most bullet holes. Abraham Wald pointed out they should instead armor the areas with no bullet holes - those were the critical areas where planes didn’t survive to return!

Promoting Fairness

Question: How can randomness promote fairness?

. . .

  • Random allocation of patients in clinical trials
  • Random audits for tax compliance
  • Random assignment of cases to judges
  • Random order of candidates on voting ballots

Uncertainty

Quick Poll

Question: Which would you prefer?

  • 100% chance of winning 50 EUR
  • 50% chance of winning 120 EUR

. . .

Tip

Answer depends on your risk aversion!

Decisions Under Uncertainty

Question: When should we embrace vs. reduce randomness?

. . .

Embrace When:

  • Exploring new solutions
  • Avoiding bias
  • Breaking deadlocks
  • Testing systems

Reduce When:

  • Safety-critical systems
  • Financial transactions
  • Medical procedures
  • Legal proceedings

Takeaways

“Good Enough” Solutions

  • Perfect is enemy of good
    • Remember Monte Carlo methods: approximations work
    • Complete analysis often impossible
    • Perfect information is rare

. . .

Tip

Many real-world problems benefit from embracing uncertainty rather than fighting it!

Opportunity Costs

  • Consider opportunity costs
    • Quick approximations enable faster decisions
    • Balance accuracy vs. computation time
    • Random sampling vs. complete enumeration

. . .

Tip

Many problems benefit from fast, good-enough solutions rather than perfect ones.

The End

Note

That’s it for today’s lecture!
We’ve covered the basics of randomness and its applications. In the upcoming tutorials, we’ll learn how to use LLMs to generate code with randomness.

Literature

Interesting literature to start

  • Christian, B., & Griffiths, T. (2016). Algorithms to live by: the computer science of human decisions. First international edition. New York, Henry Holt and Company.1

Books on Programming

  • Downey, A. B. (2024). Think Python: How to think like a computer scientist (Third edition). O’Reilly. Here
  • Elter, S. (2021). Schrödinger programmiert Python: Das etwas andere Fachbuch (1. Auflage). Rheinwerk Verlag.

. . .

Note

Think Python is a great book to start with. It’s available online for free. Schrödinger Programmiert Python is a great alternative for German students, as it is a very playful introduction to programming with lots of examples.

More Literature

For more interesting literature, take a look at the literature list of this course.

Footnotes

  1. The main inspiration for this lecture. Nils and I have read it and discussed it in depth, always wanting to translate it into a course.↩︎