{{ message }}

Instantly share code, notes, and snippets.

StewSchrieff/1_probability.py

Last active Jan 14, 2020
Riddler (Find Your Favorite Song) 2019-12-06
 def get_chance_of_better_than_next_on_next_roll(num): # this is a sliding scale return (42 - num - 1) / 100 def get_prob(num): if num == 41: return 0 prob = get_chance_of_better_than_next_on_next_roll(num) return prob + ((1 - prob) * get_prob(num +1)) if __name__ == '__main__': for x in range(41): print(f'The prob of beating Nexting is: {round(get_prob(x), 4)} for starting value of {x}')
 The prob of beating Nexting is: 1.0 for starting value of 0 The prob of beating Nexting is: 0.9999 for starting value of 1 The prob of beating Nexting is: 0.9999 for starting value of 2 The prob of beating Nexting is: 0.9998 for starting value of 3 The prob of beating Nexting is: 0.9997 for starting value of 4 The prob of beating Nexting is: 0.9995 for starting value of 5 The prob of beating Nexting is: 0.9993 for starting value of 6 The prob of beating Nexting is: 0.9989 for starting value of 7 The prob of beating Nexting is: 0.9983 for starting value of 8 The prob of beating Nexting is: 0.9974 for starting value of 9 The prob of beating Nexting is: 0.9962 for starting value of 10 The prob of beating Nexting is: 0.9945 for starting value of 11 The prob of beating Nexting is: 0.9922 for starting value of 12 The prob of beating Nexting is: 0.989 for starting value of 13 The prob of beating Nexting is: 0.9848 for starting value of 14 The prob of beating Nexting is: 0.9791 for starting value of 15 The prob of beating Nexting is: 0.9718 for starting value of 16 The prob of beating Nexting is: 0.9624 for starting value of 17 The prob of beating Nexting is: 0.9505 for starting value of 18 The prob of beating Nexting is: 0.9357 for starting value of 19 The prob of beating Nexting is: 0.9176 for starting value of 20 The prob of beating Nexting is: 0.8957 for starting value of 21 The prob of beating Nexting is: 0.8696 for starting value of 22 The prob of beating Nexting is: 0.839 for starting value of 23 The prob of beating Nexting is: 0.8037 for starting value of 24 The prob of beating Nexting is: 0.7635 for starting value of 25 The prob of beating Nexting is: 0.7184 for starting value of 26 The prob of beating Nexting is: 0.6687 for starting value of 27 The prob of beating Nexting is: 0.6148 for starting value of 28 The prob of beating Nexting is: 0.5572 for starting value of 29 The prob of beating Nexting is: 0.4968 for starting value of 30 The prob of beating Nexting is: 0.4347 for starting value of 31 The prob of beating Nexting is: 0.3718 for starting value of 32 The prob of beating Nexting is: 0.3097 for starting value of 33 The prob of beating Nexting is: 0.2497 for starting value of 34 The prob of beating Nexting is: 0.1932 for starting value of 35 The prob of beating Nexting is: 0.1417 for starting value of 36 The prob of beating Nexting is: 0.0965 for starting value of 37 The prob of beating Nexting is: 0.0589 for starting value of 38 The prob of beating Nexting is: 0.0298 for starting value of 39 The prob of beating Nexting is: 0.01 for starting value of 40

Let's make a few observations:

1. You should never be clicking next and then clicking random. If you are going to click random, you need to do it before you click next.
2. This implies that the general strategy should be to click random until you get "close enough" to click next until you get to 42.

Let's investigate how close is close enough where you can start clicking next.

By using probability.py, we use a recursive function to accurately describe the probability that you will fare better by clicking Random, instead of clicking next every time. This formula was reasoned out by the following intuition (loosely based on my memory of an inductive proof):

• If your starting number is 42, you obviously are finished, and never should click random
• If your starting number is 41, you obviously should click next, and never click random. Clicking random will, at best match the number of moves it takes to click next and get to 42
• If your starting number is 40, then you can start to think about clicking random.
• It's possible that you click random and get 42. This is the only scenario in which you will get to 42 more efficiently than by clicking next twice.
• We know that, by the binomial distribution where p = 0.01, k = 1, n = 1, that this probability is 1%.
• That's not very likely to happen, so it's in our long term, average, best interest to click next twice, rather than risk it.
• If your starting number is 39, then you again can think about clicking random.
• Using the same logic, there are 2 outcomes of clicking random (41, 42) that will guarantee that you use less moves than clicking next
• If you random into 40, then you will use the same number of moves, so you should have just clicked next.
• We can model the probability that clicking random is better by adding this probability of your next roll guaranteeing a better result (2%) to the probability of not rolling a better result (98%) multiplied by the probability of getting a better result when you would have been at 40 (1%)
• this results in a probability of performing better than next being 2.98%.
• Hey that's a better chance! But still not good enough to warrant clicking random.
• By continuing this pattern, we can calc the probability for every number between 0 and 42.
• This is shown above (probability_output.txt).

The main point of the above file is to find the "tolerance" on which it stops becoming worth it to click "Random". By reading the probabilities, we can see that it is better on average to click random until you roll a 30, at which point it becomes slightly better to click next until you get to 42.

 import random def perform_game(track, tolerance): # print(f'Starting game on track: {track}.') winning_track = 42 lower_bound = winning_track - tolerance # print(lower_bound) moves = 0 while track != winning_track: if track >= lower_bound and track < winning_track: # Press Next track += 1 if track == 101: # Account for going over 100 track = 1 else: # Press random track = random.randint(1,101) moves += 1 # print(f'Finished game that took: {moves} moves.') return moves if __name__ == '__main__': current_track = 30 target = 42 distance = target - current_track for tolerance in range(12,16): moves = [] size = 1000001 for _ in range(size): moves.append(perform_game(random.randint(1,101), tolerance)) sum = 0 for x in moves: sum += x print(f'The final average is: {sum / (size - 1)} moves for lower bound: {42 - tolerance}')
 The final average is: 12.758916 moves for lower bound: 30 The final average is: 12.716598 moves for lower bound: 29 The final average is: 12.732438 moves for lower bound: 28 The final average is: 12.80545 moves for lower bound: 27

According to our Monte Carlo simulation, the average number of moves required to get to track 42 is 12.717 moves using the ideal strategy of clicking random until you are within 29-42.

What's interesting in the above Monte Carlo simulation is that I don't exactly get the same results as I expected.

According to our original calculation of when it becomes better, on average, to click next, you should start clicking next when you are between 30-42. According to our Simulation, you have a lower expected number of moves if you set the lower bound to be 29 instead of 30.

Perhaps this can be explained by the true lower bound should be between 29 and 30, however we are dealing with discrete track numbers, rather than continuous. It's possible the random variance introduced in the simulation causes this fine line to be misinterpreted.

Could there be any other explanation? Perhaps I'm mis-counting somewhere in the code...

StewSchrieff commented Dec 6, 2019

 Here's the link to the Riddler problem I'm trying to work out: https://fivethirtyeight.com/features/how-fast-can-you-skip-to-your-favorite-song/