On 1/5, I read a post from Yifeng Ruan on best stopping problem. It’s a coincidence that I was planning to purchase a reselling ticket (I was not lucky enough to get a direct selling Taylor Swift ticket) as a birthday gift and this best stopping solution fit perfectly. In the next 1 month, I practiced with my real use case to see if it works…

Background: What is the $1/e$ law?

The idea is from a wechat post by Yifeng Ruan, who shared contents from Brian Christian's book Algorithms to Live By, cited below:

Today I would like to share its first chapter, "The Best Time to Stop": When can I stop looking?
 
There are many "search-decision processes" in daily life, and if you examine all the options, it will take a long time and you may miss the opportunity, and the one you meet later may not be as good as the one before. Is it possible to determine a point in time, at a certain stage to stop looking, when the probability of finding the right candidate is the greatest?
 
This is known mathematically as the "secretary problem"
 
A company is looking for a secretary and has 100 candidates, who are interviewed in turn. After each interview, a decision must be made immediately whether to hire or not. In other words, you cannot interview all of them and then go back and decide which one to hire; once you give up on the current candidate, you have to choose from the ones who come after you.
 
This setup is reasonable and symbolizes the various opportunities we encounter in life. When an opportunity comes, it is fleeting and you must decide immediately whether to take it or not; to miss it is to miss it. You gave up an opportunity three months ago, it is impossible to pick it up again three months later.
 
You can think about how many people should be interviewed at this point.
 
If you hire too early, you may miss better candidates behind you; if you hire too late, you may mistakenly let go of qualified candidates in front of you.
 
Mathematicians have had ample discussions on this issue. After calculation, the method with the highest probability of success is called the "1/e rule". e is the base of the natural logarithm, which is equal to 2.718, then 1/e is equal to 37%, so it is also called the "37% rule".
 
The "37% rule" means that the search phase should be stopped at 37%. The first 37 of 100 applicants are interviewed first, and thereafter, as long as they meet a better one, they are hired immediately and not further interviewed. In other words, the first 37 interviewees, no matter how good, will not be accepted, they are only used to determine the criteria for acceptance.
 
If the most suitable candidate is in the first 37%, it will be missed as a cost that has to be paid in the "search phase". The final selection will be the next best choice, which is not as good as the previous candidates.
 
This rule is very practical, and in daily life, as long as it is in line with the "search-decision process" scenario, the 37% rule can be applied.
 
(1) When dating, suppose there are 10 blind dates, then the first 3 to 4 can be used as a search stage, and later, as long as you meet a better person than the previous one, you can agree.
 
(2) When renting an apartment, assume that there is a month of house hunting time, then 37﹪ of 30 days is 11 days. After 11 days of searching, you need to make a move. As soon as you find an apartment that is more desirable than the previous one, don't hesitate to rent it.
 
(3) When reading a book, assume it has 100 pages. If you read 37 pages and haven't found anything of interest, then you can give up.
 
(4) A 10-episode TV series, the 4th episode is the best time to abandon the show.
 
(5) A 10-minute video, after watching 3 minutes and 42 seconds, if you still don't think it's good, you can turn it off.
 
(6) A young man wants to find the direction of his life and determine what he wants to do in the future from the age of 18 to 24, a total of 7 years. Then, he has 2.59 years (7 * 0.37) of free time to try. In other words, by the second semester of his junior year, he should initially set his direction, and later on, he should not change his career direction unless he encounters something more attractive.

Practice: My real use case for ticket purchasing

My goal is to purchase 2 reselling Taylor Swift tickets for a birthday gift on 2/9. From 1/6 to 2/9, I have 33 days and plan to use the first 12 days to put down the lowest prices of tickets by zones. And from day 13 to the last day, purchase ticket whenever the price is lower than the best price between day 1 and day 12.

Retrospective

Apparently, the 1/e best stopping law works! Dig a bit deeper into why:
$$\displaystyle {\begin{aligned}P(r)&=\sum _{i=1}^{n}P\left({\text{applicant }}i{\text{ is selected}}\cap {\text{applicant }}i{\text{ is the best}}\right)\\&=\sum _{i=1}^{n}P\left({\text{applicant }}i{\text{ is selected}}|{\text{applicant }}i{\text{ is the best}}\right)\cdot P\left({\text{applicant }}i{\text{ is the best}}\right)\\&=\left[\sum _{i=1}^{r-1}0+\sum _{i=r}^{n}P\left(\left.{\begin{array}{l}{\text{the best of the first }}i-1{\text{ applicants}}\\{\text{is in the first }}r-1{\text{ applicants}}\end{array}}\right|{\text{applicant }}i{\text{ is the best}}\right)\right]\cdot {\frac {1}{n}}\\&=\left[\sum _{i=r}^{n}{\frac {r-1}{i-1}}\right]\cdot {\frac {1}{n}}\\&={\frac {r-1}{n}}\sum _{i=r}^{n}{\frac {1}{i-1}}\end{aligned}}$$

Letting $n$ tend to infinity, writing $x$ as the limit of $(r−1)/n$, using $t$ for $(i−1)/n$ and $dt$ for $1/n$, the sum can be approximated by the integral

$$P(x)=x \int_{x}^{1}\frac{1}{t}\,dt = -x \ln(x)\ $$
Taking the derivative of $P(x)$:
$$ P'(x)=-x' \ln(x)\ - x\ln'(x)\ = -lnx - x \cdot \frac{1}{t} $$
Set it to $0$, we find that the optimal $x$ is equal to $1/e$. Thus, the optimal cutoff tends to $n/e$ as $n$ increases, and the best applicant is selected with probability $1/e$.

And an interesting post I found - someone in 19th used this law to find best finance…: Students aboard blind date notes. And more related best stopping problems can be found in Wikipedia.

1 月 5 号的时候，读到阮一峰的一篇公众号介绍最佳停止问题。刚好我在想着要买泰勒斯威夫特的演唱会门票（直接抢直售票以泰勒的火爆程度肯定是不现实的…） 做送人的生日礼物。接下来的一个月，我直接按照最佳停止方法走看能不能买到最合适价格的门票吧。

背景：什么是 $1/e$ 法则?

以下内容来自科技爱好者周刊（第238期）：停止寻找的最佳时间，他分享了布赖恩·克里斯蒂安的书《Algorithms to Live By》（生活中的算法）：

今天我想分享它的第一章 《最佳停止时间》：什么时候可以停止寻找？
 
日常生活有很多“寻找-决策过程”，如果考察所有选项，要花费很长时间，可能还会错失机会，后面遇到的未必有前面的好。能否确定一个时间点，到了某个阶段就停下来，不再寻找了，这时找到合适候选人的概率最大？
 
这在数学上称为“秘书问题”。
 
某公司招聘一名秘书，有100名候选人，依次面试。每面试完一个人，就必须立刻决定是否录取。也就是说，不能面试完所有人，再回过头决定录取哪一个，一旦放弃当前候选人，就只有从后面的面试者中选择。
 
这个设定是合理的，象征我们在生活中遇到的各种机会。机会来临时，转瞬即逝，必须立刻决定是否抓住它，错过就是错过了。你在三个月前放弃了一个机会，不可能三个月后再捡起来。
 
大家可以想一想，这时应该面试多少人？
 
如果录用得太早，可能错过后面更好的候选人；如果录用得太晚，可能错误放走前面的合格人选。
 
数学家对这个问题，已经有了充分的讨论。经过计算，成功概率最大的方法，叫做“1/e 法则”[4]。e 是自然对数的底数，约等于2.718，那么 1/e 就约等于37%，所以它又称“37%法则”。
 
“37%法则”的意思就是，寻找阶段进行到37%就要停止。 100个应聘者，先面试前37个，此后的面试只要遇到一个更优秀的，就立刻录取，不再继续面试了。换句话说，前37个面试者无论多么优秀，都不会录取，他们只是用来确定录取的标准。
 
如果最合适的候选者偏偏在前面37%里面，那就只能错过了，作为“寻找阶段”不得不付出的成本。最终录取的将是不如前面候选人的次优选择。
 
这个法则很实用，日常生活中，只要符合“寻找-决策过程”的场景，都可以适用37%法则。
 
（1）相亲时，假定有10个相亲对象，那么前3～4个可以作为寻找阶段，后面只要遇到一个比前面更好的人，就可以同意了。
 
（2）租房时，假定有一个月的找房子时间，那么30天的37﹪也就是11天。在找了11天之后，你就要出手了。只要发现比先前更令人心动的房子，就不要犹豫，马上租下来。
 
（3）读书时，假定这本书有100页，如果读了37页，还没有发现感兴趣的内容，那就可以放弃了。
 
（4）一个10集的电视剧，第4集是最佳弃剧时间。
 
（5）一个10分钟的视频，看了3分42秒，如果还是觉得不好看，就可以关掉了。
 
（6）一个年轻人想在18岁到24岁，一共7年时间里找到人生方向，确定未来想做什么。那么，他有2.59年（7 * 0.37）的时间自由尝试。也就是说，到了大三下学期就应该初步定下自己的方向，后面除非遇到更有吸引力的事情，否则就不应该转换事业方向。

实践：开始按照最佳停止方法买票

1.6 - 2.9 用前 12 天每天记录Taylor swift 二手票最低价格，从第 13 天到最后只要有更低票价就入手，之后半个月做验证（后来发现收集到的数据到2.9 已经够了没必要做验证了）。结果如下：

回顾

从表格里可以看出来 $1/e$ 最佳停止方法是有效的。为什么呢？
$$\displaystyle {\begin{aligned}P(r)&=\sum _{i=1}^{n}P\left({\text{人选 }}i{\text{ 被选中}}\cap {\text{人选 }}i{\text{ 是最佳人选}}\right)\\&=\sum _{i=1}^{n}P\left({\text{人选 }}i{\text{ 被选中}}|{\text{人选 }}i{\text{ 是最佳人选}}\right)\cdot P\left({\text{人选 }}i{\text{ 是最佳人选}}\right)\\&=\left[\sum _{i=1}^{r-1}0+\sum _{i=r}^{n}P\left(\left.{\begin{array}{l}{\text{前 }}i-1{\text{ 个人选中的最佳人选}}\\{\text{在前 }}r-1{\text{ 个人选中}}\end{array}}\right|{\text{人选 }}i{\text{ 是最佳人选}}\right)\right]\cdot {\frac {1}{n}}\\&=\left[\sum _{i=r}^{n}{\frac {r-1}{i-1}}\right]\cdot {\frac {1}{n}}\\&={\frac {r-1}{n}}\sum _{i=r}^{n}{\frac {1}{i-1}}\end{aligned}}$$

令 $n$ 趋近于正无穷，用 $x$ 表示 $(r−1)/n$ 的极限， 令 $t$ 为 $(i−1)/n$、$dt$ 为 $1/n$，总和可以近似为如下积分：

$$P(x)=x \int_{x}^{1}\frac{1}{t}\,dt = -x \ln(x)\ $$

对 $P(x)$ 求导：

$$ P'(x)=-x' \ln(x)\ - x\ln'(x)\ = -lnx - x \cdot \frac{1}{t} $$

倒数为 $0$ 解出 $x = 1/e$。从而，当 $n$ 增大时最优截断趋近于 $n/e$ 最佳人选被选中的概率为 $1/e$。

另外一个有趣的文章是 2002 年数学传播第二卷第三期的海外學人相親記，有人真的拿来相亲也是绝了。更多的相关信息可以在维基百科找到。