Show HN: Learn When to Quit

Madden: "Now with no timeouts I think that the Patriots, with this field position they have to just run the clock out, you have to play for overtime now. I don't think you want to force anything here, you don't want to do anything stupid because you have no timeouts and you are backed up."

Summerall: Brady is in the shotgun and he's gonna throw it ..."

https://www.youtube.com/watch?v=GC4qgrUgF9I&feature=youtu.be...

Always trust the stats ;)

Done! Thanks for the tip, by the way.

Yep. The optimal strategy depends only on the relative ordering of elements, not on their magnitudes or any other property. So the strategy is the same for any continuous distribution.

(With a discrete distribution, the possibility of ties slightly affects things. But in this particular game, ties seem to be very improbable, so they can be ignored.)

Consider a two digit number. With this algorithm, half of the numbers generated will be less than 10, and half will be 11-99.

Likewise with the full 100 digits this algorithm has a 1% chance of generating a number less than 10, while the correct proportion would be 1e-100.

The algorithm also does not generate numbers with zero in them (presumably to avoid leading zeroes, but this will skew results somewhat).

I think the correct algorithm would be to generate 100 digits and then remove the leading zeroes.

The distribution chosen here is ~ uniform for the number of digits. (https://github.com/victorqribeiro/googol/blob/master/js/main... )

This is not the same hypothesis as the problem stated in the video. The video talks about the "secretary problem". In this problem you know nothing about the distribution. You just know that the number are ordered.

Here because you know the distribution you can do better by using a strategy which choose to stop depending on the value of the number you have so far. For example if at the 15th pick you get a number with 99 digit, you can safely assume that it is better to stop now (every time you pick you have only a ~1% chance of finding a 99-digit number needed to do better so keeping it means you win (99/100)^(50-16) = 70%, whereas the non-exploitable strategy (i.e. optimal strategy for the secretary problem) 50/e=18 will tell you to keep going and you would lose 70% of the times).

For the secretary problem the theoretical way to sample the number is to set it up as a game where the first player plays the game and the second pick the numbers adversely so that the first doesn't win. A good strategy for the second player is to pick a distribution from a big set of varied distributions, and sample the number from this distribution.