Show HN: Learn When to Quit(github.com)
github.com
Show HN: Learn When to Quit
https://github.com/victorqribeiro/googol
47 comments
This is the Secretary Problem.
https://en.wikipedia.org/wiki/Secretary_problem
https://en.wikipedia.org/wiki/Secretary_problem
Sometimes when I’m bored and out walking, I play this game with cars. I pretend I’m allowed to keep any one of the next ten cars that go past, but I need to accept or reject it the moment I see it.
If the second car is a Volvo do I pick it, or hold out waiting for a Mercedes? If I pick that Mercedes, am I going to regret it in thirty seconds when a Rolls rolls past? Am I going to get stuck with an old Hyundai due to my inability to settle?
If the second car is a Volvo do I pick it, or hold out waiting for a Mercedes? If I pick that Mercedes, am I going to regret it in thirty seconds when a Rolls rolls past? Am I going to get stuck with an old Hyundai due to my inability to settle?
Wouldn't this be different since we know the maximum number and the distribution?
The solution wouldn't be to still skip 1/e if you got something like googol - 1 on the first try.
The solution wouldn't be to still skip 1/e if you got something like googol - 1 on the first try.
The distribution of numbers is not uniform across the 0..googol here. The implementation first chooses the length of the number, then fills in the digits. This makes it biased towards smaller numbers.
Does it still have the same optimal strategy as for uniform generation?
Does it still have the same optimal strategy as for uniform generation?
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.
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.
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.)
(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.)
It isn't optimal for known distributions. If you're sampling from a normal distribution with known parameters, and the first of 100 samples is 5 standard deviations above the mean, you take it.
>"The implementation first chooses the length of the number, then fills in the digits. This makes it biased towards smaller numbers."
Why?
Why?
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.
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.
Semi-relevant: https://en.wikipedia.org/wiki/Benford%27s_law
Also relevant (and in my mind, the underlying explanation for Benford's Law):
https://en.m.wikipedia.org/wiki/Jeffreys_prior
https://en.m.wikipedia.org/wiki/Jeffreys_prior
Just getting into bayesian inference and this sent me down a rabbit hole, thanks :)
Damn...
People, I just ran this simple script on my terminal using Node and I got a pretty uniform result.
{ '0': 9917, '1': 10015, '2': 9957, '3': 10107, '4': 10019, '5': 10037, '6': 10120, '7': 9914, '8': 10042, '9': 9872 }
a = {}
for(let i = 0; i < 100000; i++){
let n = Math.floor(Math.random() * 10);
if( n in a )
a[n] += 1
else
a[n] = 1
}
{ '0': 9917, '1': 10015, '2': 9957, '3': 10107, '4': 10019, '5': 10037, '6': 10120, '7': 9914, '8': 10042, '9': 9872 }
> real-life sets of numerical data
Today you learned: Node’s random number generator isn’t selecting from a real-life set of numerical data
Today you learned: Node’s random number generator isn’t selecting from a real-life set of numerical data
yeah, I just mixed two informations. I thought the other person said my algorithm would be biased towards small numbers cause I use the JS random function to pick the number of decimal places for the number
Yep, sorry, didn't mean to say this directly applied, just a neat concept that's somewhat related.
Sure but that’s not the algorithm you used in the repo.
Consider using a monospace font. It is difficult to tell how large one number is relative to another when each digit has a different width
I have written a small analysis of that same problem using simple Python code, a couple of years ago:
https://cjauvin.blogspot.com/2012/12/find-true-love-on-datin...
https://cjauvin.blogspot.com/2012/12/find-true-love-on-datin...
Nice work
All of these huge numbers are basically un-comparable ergonomically to me. Why not make the distribution 1-10k instead?
Agreed.
Also, there is really no reason to have multiple boxes you have to click. You could just have a single "next" button along with a counter to show how many choices you have left before you run out.
Also, there is really no reason to have multiple boxes you have to click. You could just have a single "next" button along with a counter to show how many choices you have left before you run out.
Yeah that confused me too.
'Next' button along with '# samples left' display would be much clearer.
Also, if the largest drawn so far were highlighted, manual play would be easier.
'Next' button along with '# samples left' display would be much clearer.
Also, if the largest drawn so far were highlighted, manual play would be easier.
I just did "Computer" 50 times and tallied the results.
Win = 32% Lose = 68%
But here's the thing, the goal should not be to win, but to get ONE OF the highest numbers with reliability.
Now here's where Optimal Stopping Theory is not optimal.
42% of the time you lose by getting to the end. Meaning you drew all 50 cards and ended with likely a very small card.
The goal of this algorithm should be that you almost never get to drawing the 50th card. You always stop before then and end with a high number.
Therefore, I wouldn't consider this algorithm optimal. Likely you should draw fewer cards in the beginning.
Win = 32% Lose = 68%
But here's the thing, the goal should not be to win, but to get ONE OF the highest numbers with reliability.
Now here's where Optimal Stopping Theory is not optimal.
42% of the time you lose by getting to the end. Meaning you drew all 50 cards and ended with likely a very small card.
The goal of this algorithm should be that you almost never get to drawing the 50th card. You always stop before then and end with a high number.
Therefore, I wouldn't consider this algorithm optimal. Likely you should draw fewer cards in the beginning.
How does this change when you're heavily punished for ending up with a much lower number (e.g., in finding a partner, biz deal, etc)?
Among a set of losing plays, I presume it's 50/50 on whether you turn over every card (and end up with the last one). So a third of the time you end up in the optimal case, another third you end up doing pretty well, and another third you're subject to absolutely random chance. Guess this is an argument for satisficing vs optimizing in most real world applications.
Among a set of losing plays, I presume it's 50/50 on whether you turn over every card (and end up with the last one). So a third of the time you end up in the optimal case, another third you end up doing pretty well, and another third you're subject to absolutely random chance. Guess this is an argument for satisficing vs optimizing in most real world applications.
You're right, this algorithm optimizes for "1 point for picking the best option, 0 for anything else", not knowing the distribution.
If you do know the distribution, and have some objective function, and samples are "free", you get a different model that you can solve inductively backwards from the case of "the last sample".
A different model is that your objective function is still on order, but it gives some points for "closer to best". Maybe you score minus n for picking the nth best sample. In that case the model need not have a known distribution (It's different if you do or don't.) And the strategy us different: if the 99th sample out of 100 is the second best you've seen so far, you should take it. (Which can't possibly be optimal in the original model.)
If you do know the distribution, and have some objective function, and samples are "free", you get a different model that you can solve inductively backwards from the case of "the last sample".
A different model is that your objective function is still on order, but it gives some points for "closer to best". Maybe you score minus n for picking the nth best sample. In that case the model need not have a known distribution (It's different if you do or don't.) And the strategy us different: if the 99th sample out of 100 is the second best you've seen so far, you should take it. (Which can't possibly be optimal in the original model.)
The conditions of this "game" are that you must decide then and there which option to choose. In the game, you do not have the luxury of viewing all of the data before you make your choice. Real life can be different (as was mentioned in the video re: Kepler's wife).
There is a huge problem with the "optimal stopping strategy" presented in the YouTube video: "sample the first 37% of the options, and then choose the first subsequent option that is better than the best option found in the sample."
By definition, there is a 37% chance of the best option being in your initial sample. You would then futilely browse through all the other options, without ever picking anything.
Ie, if you applied this strategy to "finding the love of your life", as the video suggests, there is a 37% chance of you dying completely alone. That doesn't seem like a very optimal strategy to me.
By definition, there is a 37% chance of the best option being in your initial sample. You would then futilely browse through all the other options, without ever picking anything.
Ie, if you applied this strategy to "finding the love of your life", as the video suggests, there is a 37% chance of you dying completely alone. That doesn't seem like a very optimal strategy to me.
I haven't seen the video but if they are talking about the secretary problem the caveat is that you can't go back to the previous options. You can do that when trying to a find a partner... sometimes.
> Ie, if you applied this strategy to "finding the love of your life", as the video suggests, there is a 37% chance of you dying completely alone. That doesn't seem like a very optimal strategy to me.
I don't think that's correct. You'd set a period of time such as 1 year or 3 years or 5 years or something during which time you will go on n amount of dates total, out of which you reject the first 37%. Then you use that as a basis for the remaining time of that period of time. If you haven't found anyone better by the last date of that time, and you have chemistry with them, you choose that last person to be the love of your life.
And if you don't have chemistry with the last person or you end up breaking up with that person, then you go on dates until you find the next person you have chemistry with and you choose them to be the love of your life.
So it's not like dying completely alone is a probable outcome that would result from the optimal stopping strategy itself.
I don't think that's correct. You'd set a period of time such as 1 year or 3 years or 5 years or something during which time you will go on n amount of dates total, out of which you reject the first 37%. Then you use that as a basis for the remaining time of that period of time. If you haven't found anyone better by the last date of that time, and you have chemistry with them, you choose that last person to be the love of your life.
And if you don't have chemistry with the last person or you end up breaking up with that person, then you go on dates until you find the next person you have chemistry with and you choose them to be the love of your life.
So it's not like dying completely alone is a probable outcome that would result from the optimal stopping strategy itself.
Very interesting, especially the video :pray:
(actual game does not look at all like the screenshot on mac/chrome)
(actual game does not look at all like the screenshot on mac/chrome)
[deleted]
Comma's would be friendlier than decimal groupings for North American users; also right-aligning would be nice.
The `.` separation confused me briefly too, being from another country that uses `,`.
But you know what, if I were the author I would have used `,` without bothering to localise to `.` (for some toy demo thing like this anyway) so I'm OK with OP doing the same to me.
But you know what, if I were the author I would have used `,` without bothering to localise to `.` (for some toy demo thing like this anyway) so I'm OK with OP doing the same to me.
right-aligning suggestion taken. =)
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 ;)