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:Weird Guy in Trench Coat

Hello, and welcome to my look at 538’s Riddler. Last week I managed to get the correct answer using a Monte Carlo, and Go’s really nice NormFloat64 function. Commenters squareandrare, mathisallaround, and guyshavit all shared voodoo mathy ways to get the answer, which I appreciated, including the chi-squared distribution. Thanks for reading and commenting!

This week’s Riddler concerns talking to strange men in trench coats.

A man in a trench coat approaches you and pulls an envelope from his pocket. He tells you that it contains a sum of money in bills, anywhere from $1 up to $1,000. He says that if you can guess the exact amount, you can keep the money. After each of your guesses he will tell you if your guess is too high, or too low. But! You only get nine tries. What should your first guess be to maximize your expected winnings?

Obviously if a man in a trench coat offers you money the answer is to run. But let’s answer the question anyway. My immediate first guess for this was $744, which was wrong. But only because I’m pretty sure the answer is $745.

How did I get this number? Well, the guessing game where someone tells you whether your guess is higher or lower is a classic example of a binary search, which is one of the most important algorithms in computer science. With 9 guesses, we know that we can guarantee coverage of 511 (2^9 – 1) values. That leaves 489 values for which we are going to not be able to guess the right answer. Sad!

Now the question is, which values do we want to cover? Well, without any knowledge to the contrary we should assume that all values between $1 and $1000 are equally likely, assuming our trench-coated friend is trustworthy (and aren’t they all?). So since there is just as much chance that there is $1000 in the envelope as $1, we might as well make sure we cover the top 511 values.

Put another way, imagine the man in the trench coat offers you only one guess. What should you do? (Run.) Well, you have just as much chance of being right by guessing $1000 as $1, so guess $1000 and hope for the best. Your expected value (EV) is the odds of being right times the payout, so if you guess $1000, your EV is $1. If you guess $1, your EV is $.001, which is… less.

So covering the top 511 values would be everything from $490 to $1000. The middle value between those two numbers is $745. I wrote some code to show this, and then ran 1000 simulations for each amount of money that is in the envelope. Here it is in Go:

package main
// Jon Wiesman, somedisagree.com

import "fmt"

func binSearchRecursive(min, max, value, guesses int) bool {

	if guesses == 0 {
		return false
	}
	if min > max {
		return false
	}

	guess := (min + max) / 2
	if guess == value {
		return true
	}

	if guess < value {
		return binSearchRecursive(guess+1, max, value, guesses-1)
	} else {
		return binSearchRecursive(min, guess-1, value, guesses-1)
	}

	return false
}

func binSearchIterative(min, max, value, guesses int) bool {
	for ; guesses > 0; guesses-- {
		if min > max {
			return false
		}

		guess := (min + max) / 2
		if guess == value {
			return true
		}

		if guess < value {
			min = guess + 1
		} else {
			max = guess - 1
		}

	}
	return false
}

func DoTrialRecursively(min, max int) {
	trials := 1000
	found := 0
	totalEarned := 0

	for i := 1; i <= 1000; i++ {
		if binSearchRecursive(min, max, i, 9) {
			found++
			totalEarned += i
		}
	}

	fmt.Printf("Recursively, with first value = %d, %d/%d success, total earned = %d\n", (min+max)/2, found, trials, totalEarned)
}

func DoTrialIteratively(min, max int) {
	trials := 1000
	found := 0
	totalEarned := 0

	for i := 1; i <= 1000; i++ {
		if binSearchIterative(min, max, i, 9) {
			found++
			totalEarned += i
		}
	}

	fmt.Printf("Iteratively, with first value = %d, %d/%d success, total earned = %d\n", (min+max)/2, found, trials, totalEarned)
}

func main() {
	DoTrialIteratively(489, 1000)
	DoTrialIteratively(490, 1000)
	DoTrialRecursively(490, 1000)
	DoTrialRecursively(491, 1000)

}

 

And here’s a link to the Go playground for this code where you can play with the numbers and run it in your browser. Doing so gives this output:

Iteratively, with first value = 744, 511/1000 success, total earned = 380184
Iteratively, with first value = 745, 511/1000 success, total earned = 380695
Recursively, with first value = 745, 511/1000 success, total earned = 380695
Recursively, with first value = 745, 510/1000 success, total earned = 380205

So your EV if you start with a first guess of $745 is $380.695, and you’ve got a 51.1% chance of making some money. Pretty good deal. (You should still run.)

My binary search function differs from most binary searches in one small way. Here, I pass in the number of guesses and decrement it with each recursive call. When it reaches 0, I return false. I used recursion here first because it’s easiest for me to write but iteration might be easier for non CS people to follow so I wrote it iteratively as well. Both work.

If you call either function with min and max at $1 and $1000, respectively, giving a first guess of $500, you will still succeed 511 times but your expected value would only be $255.175. This is because the 489 missed values would be evenly distributed instead of all at the bottom. Try it.

So, that’s my answer: $745. I believe it is right unless there is some method to guarantee more than 511 found values with only 9 guesses. As always, I’m always willing to admit I am wrong so if I am, I’d love to know.

Thanks for reading.

 

The 538 Riddler: Free Throw Grannies

Hello, and welcome to this week’s look at the 538 Riddler. Last week concerned optimal strategy for a (very) simple game show, and happily my answer was correct. This week’s Riddler concerns free throws again.

Consider the following simplified model of free throws. Imagine the rim to be a circle (which we’ll call C) that has a radius of 1, and is centered at the origin (the point (0,0)). Let V be a random point in the plane, with coordinates X and Y, and where X and Y are independent normal random variables, with means equal to zero and each having equal variance — think of this as the point where your free throw winds up, in the rim’s plane. If V is in the circle, your shot goes in. Finally, suppose that the variance is chosen such that the probability that V is in C is exactly 75 percent (roughly the NBA free-throw average).

But suppose you switch it up, and go granny-style, which in this universe eliminates any possible left-right error in your free throws. What’s the probability you make your shot now? (Put another way, calculate the probability that |Y| < 1.)

So I’ve been doing all these Riddler exercises in C++ but this week I thought I’d mix it up and give the Go language a shot. I’ve never written anything in Go but a friend of mine sent me this text a while back:

text_from_sean

As you can see, I have an exciting social life. So anyway I’ve been wanting to try it out for a while and I figured this blog would be a good opportunity. I’ve been doing the Go tutorials that you can find here.

Another benefit of doing the code (when possible) in Go is that I can link to a version of my code that you can run yourself in the browser, and then make changes to see the impact of those changes. I’m not sure that anyone was copying my C++ code into a compiler, creating a project, building, then running it. But this way running the code is literally just a click away.

Okay, so I thought this week’s Riddler was pretty straightforward from a “getting an answer” point of view. (Which probably means I’m totally wrong.) If I simulate a normalized random distribution of 2D points with some variance such that 75% of those points fall inside a circle with radius 1, then what would be the probability of falling in the circle if the x-component was always 0?

Luckily, Go has a really nice NormFloat64 function that generates normalized random numbers with a standard deviation of 1. With such variance, about 40% of random points will be inside the circle, using the good old Pythagorean Theorem. If I understand the problem correctly all I need to do is find the standard deviation that will result in 75% of points falling inside the circle. Then, I can calculate the magnitude of points where the x-component is 0, and find how frequently they fall in the circle.

So the big task here was to find the right value for the deviation factor. I did this with trial and error and came up with 0.60054. I’m sure there’s a math way to find this value (or a better value) and I look forward to seeing it (Attn: Alex!). Once you start generating x- and y-components, find their magnitude using Sqrt(x*x + y*y) and see if it is below 1. If it is, then that’s a made shot. Also, check to see what would happen if the x-component is 0. You can do that as Sqrt(0*0 + y*y) or Sqrt(y*y) or Abs(y).

Here’s the code in Go:

// 538 Riddler: Should You Shoot Free Throws Underhand?
// http://fivethirtyeight.com/features/should-you-shoot-free-throws-underhand/
// Jon Wiesman, somedisagree.com
package main

import (
	"fmt"
	"math"
	"math/rand"
)

func main() {

	overhand := 0
	granny := 0

	trials := 1000000
	r := rand.New(rand.NewSource(int64(538)))

	dev := 0.60054
	
	for i := 0; i < trials; i++ {
		x := r.NormFloat64() * dev
		y := r.NormFloat64() * dev

		d := math.Sqrt(x*x + y*y)
		g := math.Abs(y)

		if d < 1 {
			overhand++
		}
		if g < 1 {
			granny++
		}
	}

	fmt.Printf("Overhand = %f%%\n", float64(overhand)*100.0/float64(trials))
	fmt.Printf("Granny = %f%%\n", float64(granny)*100.0/float64(trials))
}

 

And here’s a link that will take you to a Go playground where you can run that code and see these results:

Overhand = 75.000800%
Granny = 90.439500%

Try it! You can also play around with different random seed values (I used 538, natch) and see what happens. I think the actual make percentage for Granny-style is more like 90.41%, depending on random seed and number of trials.

Thanks for reading!