Discussion 2-9

Our new trick today was random numbers (rand, srand). Even so, the main tricky point in our code is still planning the control flow and structure: loops, if statements, etc. We wrote code to answer two problems using simulation.

  1. In betting.cpp we (approximately) computed a probability that would have been really hard to compute by hand. People use this technique all the time in serious applications when the "pen-and-paper" result is impossible to compute. It's also just handy when you don't feel like doing the math!
  2. In computePi.cpp we showed a method for computing several digits of pi without assuming any math knowledge beyond area of a circle being pi*r*r.

Extra challenges

Here are some practice problems you could try to solve using simulation.

  1. In the casino game craps, the two main bets are called Pass and Don't Pass. Which one has a bigger house edge?
  2. Suppose you're going to flip a fair coin until you get 3 heads in a row. On average, how many flips will this take? What if we instead flip until 2 heads in a row, or 4, or 5? Can you guess the pattern? (No need to prove it.) What if you instead flip until the 3 most recent results are HTH?
  3. Suppose you have $100 and you're going to repeatedly bet on the outcome of coin tosses. The coin is weighted: you win with probability 2/3 and lose with probability 1/3. For each flip you pick an integer bet size K; then you win or lose K dollars on that flip. You aren't allowed to bet more money than you currently have. Let's say you're allowed to play up to 50 times or until you run out of money. You want to maximize your expected money at the end (i.e. the average cash-after-50-plays you'll have). Which of these strategies is the best?
    • Bet $10 every time.
    • Bet $50 every time.
    • Bet $100 every time.
    • Bet 10% of current wealth every time. (Rounded to nearest integer)
    • Bet 50% of current wealth every time. (Rounded to nearest integer)
    • Bet 100% of current wealth every time.
    Based on these methods (or any other idea you have), what's the best strategy you can come up with?