The 538 Riddler:New Casino Game

Welcome to my weekly look at 538’s The Riddler. Happily my answer to last week’s riddle proved to be correct once again, and I was happy to see some commenters who came to the same conclusions. Thanks for reading and commenting.

Due to a lack of time with Easter and all, I’m not very confident of my answer to this week’s Riddler, but I’ll let you decide. Here’s the riddle:

Suppose a casino invents a new game that you must pay $250 to play. The game works like this: The casino draws random numbers between 0 and 1, from a uniform distribution. It adds them together until their sum is greater than 1, at which time it stops drawing new numbers. You get a payout of $100 each time a new number is drawn.

For example, suppose the casino draws 0.4 and then 0.7. Since the sum is greater than 1, it will stop after these two draws, and you receive $200. If instead it draws 0.2, 0.3, 0.3, and then 0.6, it will stop after the fourth draw and you will receive $400. Given the $250 entrance fee, should you play the game?

Specifically, what is the expected value of your winnings?

Okay, when I read that part it seemed like this was going to be a no-brainer, but then Ollie added:

[Editor’s note: You know how sometimes your boss/teacher asks you not to bring your laptop to a meeting/class, and you’re all like, “Jeez, how am I gonna tweet during the meeting/class, then?” Well, I’m going to pull rank and ask that you don’t bring laptops to this Riddler. Next week I will highlight — nay, celebrate! — the elegant, pencil-and-paper solutions over the brutal, cold, silicon ones. We’re all on the honor system with one another, right? RIGHT?]

No computers! Pencil and paper? Egads. Okay, so I did a little bit of working this out and I came up with an answer I thought might be right. First of all, I assumed that you are guaranteed to see at least 2 numbers, because with all the real numbers between 0 and 1, the chances of getting 1 exactly are one over infinity, or zero. So the minimum amount you are going to lose in this game is $50. And it seems to me that the chances of seeing a third number are 50%, since the average value of the first number will be 0.5 and the chances that the second number will be greater than 0.5 is… 0.5, or 50%.

Okay, so right away we see that there’s a 50% chance we lose $50 (-$250 + $200), and a 50% chance that we win $50 (-$250 + $300), with the possibility of more money to come. This is a wonderful casino game; I would very much like to find the casino that offers it. A game like this might explain how somebody could bankrupt a casino. (Sad!)

So we have a 50% chance of seeing only 2 numbers and losing $50. What are the chances of seeing only 3 numbers? Well, I figure if 2 random numbers are below 1, then there’s a 2/3 chance that the 3rd number will break the ceiling. So 2/3 of what is remaining (1/2) is 1/3. So 1/2 the time we see 2 and only 2 numbers and 1/3 of the time we see 3 and only 3 numbers, and now we have 1/6 (1/2 – 1/3) remaining.

Chance of only 2 numbers: 1/2. 1 – 1/2 = 1/2 remaining.
* 2/3  =
Chance of only 3 numbers: 1/3. 1/2 – 1/3 = 1/6 remaining.
* 3/4 =
Chance of only 4 numbers: 1/6 * 3/4 = 1/8. 1/6 – 1/8 = 1/24 remaining.
* 4/5 =
Chance of only 5 numbers: 1/24 * 4/5 = 1/30. 1/24 – 1/30 = 1/120 remaining.
* 5/6 =
Chance of only 6 numbers: 1/120 * 5/6 = 1/144.

And so on.

So to get the Expected Value (EV) we can take the odds of each payout * its value and get:

$-50/2 + $50/3 + $150/8 + $250/30 + $350/144 = $21.18

Plus some increasingly smaller numbers for seeing 7, 8, 9, 10? numbers.

Ok, now that we got our EV answer, let’s cheat! (If you don’t want to see whether a computer confirms or disproves my EV answer, stop reading here.)

I wrote some code in Go (are you sick of Go yet, because I am not.)

package main

import (
	"fmt"
	"math/rand"
)

func doFloatTrial() int {
	total := 0.0
	numbers := 0
	
	for {
		numbers++
		total += rand.Float64()
		if total >= 1.0 {
			break;
		}
	}
	return numbers
}


func main() {

	trials := 1000000
	
	var results []int
	
	cash := 0.0
	
	for i := 0; i < trials; i++ {
		cash -= 250.0
		numbers := doFloatTrial()
		cash += 100.0 * float64(numbers)
		for a := len(results); a <= numbers; a++ {
			results = append(results, 0)
		}	
		results[numbers]++
	}

	fmt.Printf("EV = %.3f\n", cash / float64(trials));
	for i := 0; i < len(results); i++ {
		fmt.Printf("Results[%d] = %d (%.2f) \n", i, results[i], float64(trials)/float64(results[i]))
	}

}

 

And here’s the output:

EV = 21.826
Results[0] = 0 (+Inf) 
Results[1] = 0 (+Inf) 
Results[2] = 499604 (2.00) 
Results[3] = 334041 (2.99) 
Results[4] = 124717 (8.02) 
Results[5] = 33341 (29.99) 
Results[6] = 6939 (144.11) 
Results[7] = 1157 (864.30) 
Results[8] = 184 (5434.78) 
Results[9] = 15 (66666.67) 
Results[10] = 2 (500000.00)

Hurray! Our EV from the code is $21.83 and we can see that the odds of drawing each count of numbers is (with variance) what we had calculated by hand. Math! Follow this link to run the code yourself in your browser.

Thanks for reading. I’m not 100% sure of this one so I look forward to better approaches to this problem in the comments.

The 538 Riddler: Air Travel Nightmare

So last week’s Riddler was a good news/bad news situation. The bad news is that I was wrong, although I did illustrate the correct answer in a follow-up post. The good news is that I still managed to get a shout-out from Ollie in this week’s Riddler, even earning the honorary title of FotR, which I hope means Friend of the Riddler.

Anyway, this week’s Riddler concerns the worst person alive and a full airplane.

There’s an airplane with 100 seats, and there are 100 ticketed passengers each with an assigned seat. They line up to board in some random order. However, the first person to board is the worst person alive, and just sits in a random seat, without even looking at his boarding pass. Each subsequent passenger sits in his or her own assigned seat if it’s empty, but sits in a random open seat if the assigned seat is occupied. What is the probability that you, the hundredth passenger to board, finds your seat unoccupied?

So the answer is 1/2, half, 50%, however you want to say it. And this is true for the last passenger no matter how many passengers are on a (full) plane. I actually worked this out before writing any code (but don’t worry, I still wrote the code!) It’s trivial to show for the case where there are only two passengers: there are two seats, and the person in front of you is the worst person alive. He either takes his seat, or yours, randomly. Fifty percent, done.

For three people (1. Worst Person Alive, 2. Rando Calrissian, and 3. You) and three seats, we can still do it in our heads. WPA takes one of three seats, so right away you have a 1/3 chance of not getting your seat. But there is also a 1/3 chance that he takes Rando’s seat, in which case Rando will randomly take one of the two remaining seats, yours or WPA’s assigned seat. One-third times one-half is 1/6, so there is a 1/6 chance you will find Rando sitting in your seat, and a 1/3 chance WPA will be sitting there. So 1/3 + 1/6 = 1/2. Boom, done.

Once I saw that the probability remained at 50% for three passengers, I suspected that it would be 50% for any number of passengers. I wrote a Monte Carlo to show that.

// AirplaneSeating.cpp : Defines the entry point for the console application.
// www.somedisagree.com, Jon Wiesman

#include "stdafx.h"
#include <vector>

#define SEAT_COUNT 100
#define EVIL_COUNT 1
#define AVAILABLE -1

class Plane
{
    std::vector<int>    m_seats;
    int                 m_available;

public:
    Plane(int seats)
    {
        m_seats.resize(seats);
        for(int i = 0; i < seats; i++)
            m_seats[i] = AVAILABLE;
        m_available = seats;
    }

    void    ClaimSeat(int seat, int passenger) 
    {
        m_seats[seat] = passenger;
        m_available--;
    }

    int     FindUnclaimedSeat() const
    {
        if(m_available == 0)
            return -1;
        int nth = rand() % m_available;

        int empty = 0;
        for(size_t i = 0; i < m_seats.size(); i++)
        {
            if(IsSeatAvailable(i))
            {
                empty++;
                if(empty > nth)
                    return i;
            }
        }
        return -1;
    }

    bool    IsSeatAvailable(size_t seat) const
    {
        return (seat >= 0 && seat < m_seats.size() && m_seats[seat] == AVAILABLE);
    }

    void    GetSeat(int passenger, bool evil)
    {
        if(evil || !IsSeatAvailable(passenger))
        {
            int seat = FindUnclaimedSeat();
            ClaimSeat(seat, passenger);
        }
        else
        {
            ClaimSeat(passenger, passenger);
        }
    }

    void    SimulateBoarding(size_t evilCount)
    {
        for(size_t i = 0; i < m_seats.size(); i++)
        {
            GetSeat(i, (i < evilCount));
        }
    }

    void    CompileStats(std::vector<int> &stats, int &wrongSeats)
    {
        for(size_t i = 0; i < m_seats.size(); i++)
        {
            if(m_seats[i] == i)
                stats[i]++;
            else
                wrongSeats++;
        }
    }
};

int _tmain(int argc, _TCHAR* argv[])
{
    std::vector<int> stats;
    int wrongSeats = 0;
    stats.resize(SEAT_COUNT);

    int trials = 100000;

    for(int i = 0; i < trials; i++)
    {
        Plane plane(SEAT_COUNT);

        plane.SimulateBoarding(EVIL_COUNT);
        plane.CompileStats(stats, wrongSeats);
    }

    printf("After %d trials with %d evil passengers:\n", trials, EVIL_COUNT);
    for(int i = 0; i < SEAT_COUNT; i++)
    {
        printf("Passenger %d seated properly %.2f%% of time\n", i, 100.0 * (double)stats[i]/(double)trials);
    }
    printf("Average of %.2f wrongfully seated passengers\n", (double)wrongSeats / (double)trials);

	return 0;
}

 

This code (download) is pretty simple. The Plane class keeps an array of seats and who (which passenger) is seated in each seat. It also keeps the number of empty seats at any time to make it easier to quickly choose a random seat. (For the purpose of this simulation it was convenient to say that the passenger index and seat assignment are the same.)

The constructor initializes the seat array to all available and sets the available count to the seat count. SimulateBoarding tells each passenger to find a seat. Finding a seat is easy. If you’re not evil and your seat is available, sit down. Otherwise, find a random available seat. Either way, call ClaimSeat to sit down and decrease the available member variable. A CompileStats function will increment the number of correct passenger-seat assignments and keep a running count of wrong ones. Finally we run this simulation 100,000 times and print out the results.

After 100000 trials with 1 evil passengers:
Passenger 0 seated properly 1.00% of time
Passenger 1 seated properly 99.03% of time
Passenger 2 seated properly 99.00% of time
Passenger 3 seated properly 99.00% of time
Passenger 4 seated properly 99.01% of time
Passenger 5 seated properly 98.93% of time
Passenger 6 seated properly 98.97% of time
Passenger 7 seated properly 98.95% of time
Passenger 8 seated properly 98.92% of time
Passenger 9 seated properly 98.98% of time
Passenger 10 seated properly 98.87% of time
.....
Passenger 90 seated properly 90.86% of time
Passenger 91 seated properly 90.03% of time
Passenger 92 seated properly 88.83% of time
Passenger 93 seated properly 87.42% of time
Passenger 94 seated properly 85.39% of time
Passenger 95 seated properly 83.11% of time
Passenger 96 seated properly 79.98% of time
Passenger 97 seated properly 74.74% of time
Passenger 98 seated properly 66.45% of time
Passenger 99 seated properly 49.95% of time
Average of 5.19 wrongfully seated passengers

So I ran this code really just to confirm that my guess of 50% would be correct. However, I saw something which kind of jogged my memory. The average number of wrongfully seated passengers out of 100 was 5.19. This was the average number of traffic jams with 100 cars from two weeks ago! (The exclamation point at the end of the last sentence might be the nerdiest exclamation point ever.) It turns out that the number of wrongfully seated passengers follows a Harmonic Series.

What this means is that the odds of anyone getting a wrong seat follows this pattern, starting from the last passenger to board: 1/2 + 1/3 + 1/4 + … You can see from the output that the chances of each passenger not getting their seat is indeed following that pattern, with a little Monte Carlo variance thrown in.

“But wait,” you say, probably not, but let’s pretend you do, “a Harmonic Series starts with one and you don’t have a one in there.” Oh but I do. But it comes at the end. Remember that in our simulation, Worst Person Alive boards first and therefore has a 99/100 chance of sitting in the wrong seat. The next person to board, let’s call him Rando Paul, has a 1/100 chance of finding WPA in  his seat. 99/100 + 1/100 = 1. The next person then has a 1/99 chance and on down to 1/2 for the last passenger. So the average number of wrongly seated passengers for N passengers with the Worst Person Alive seating first boils down to 1 + 1/2 + 1/3 + … + 1 / (N – 1).

Traffic jams and airline travel: unexpected sources of harmony. Thanks for reading!