# Hubert Wang

I am
Hubert Wang

Wechat Official Account
Find fun things here!

# Verify 1/e Optimal Stopping Law by Buying Taylor Swift Tickets 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.

Date Inner Middle Outer
1/6 - $899$833
1/7 $1,206$899 $630 1/8$1,199 $899$765
1/9 $1,199$899 $765 1/10$1,206 $1,035$675
1/11 $1,199$900 $675 1/12$1,199 $990$675
1/13 $1,199$945 $700 1/14 - - - 1/15$1,199 $720$700
1/16 $1,199$720 $699 1/17 - - - start_buying 1/18$1,199 $1,035$700
1/19 $1,199$1,035 $699 1/20$1,199 $1,035$699
1/21 $1,199$1,080 $698 1/22$990 (bought) $1,080$585
1/23 $1,199$1,080 $698 1/24$1,193 $1,080$699
1/25 $1,193$1,080 $694 1/26$1,186 $896$675
1/27 $1,184$837 $675 1/28$990 (section 13, facing extended stage) $837$675
1/29 - - -
1/30 $1,199$900 $584 1/31 - - - 2/1$1,199 $900$675
2/2 $1,185$900 $675 2/3$1,183 $900$675
2/4 $1,183$900 $675 2/5$1,177 $900$699
2/6 $1,199$900 $699 2/7$1,199 $810$699
2/8 $1,199$810 $630 2/9$1,199 $742$585

## 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$ 法则?

“37%法则”的意思就是，寻找阶段进行到37%就要停止。 100个应聘者，先面试前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 已经够了没必要做验证了）。结果如下：

Date Inner Middle Outer
1/6 - $899$833
1/7 $1,206$899 $630 1/8$1,199 $899$765
1/9 $1,199$899 $765 1/10$1,206 $1,035$675
1/11 $1,199$900 $675 1/12$1,199 $990$675
1/13 $1,199$945 $700 1/14 - - - 1/15$1,199 $720$700
1/16 $1,199$720 $699 1/17 - - - start_buying 1/18$1,199 $1,035$700
1/19 $1,199$1,035 $699 1/20$1,199 $1,035$699
1/21 $1,199$1,080 $698 1/22$990 (bought) $1,080$585
1/23 $1,199$1,080 $698 1/24$1,193 $1,080$699
1/25 $1,193$1,080 $694 1/26$1,186 $896$675
1/27 $1,184$837 $675 1/28$990 (section 13, facing extended stage) $837$675
1/29 - - -
1/30 $1,199$900 $584 1/31 - - - 2/1$1,199 $900$675
2/2 $1,185$900 $675 2/3$1,183 $900$675
2/4 $1,183$900 $675 2/5$1,177 $900$699
2/6 $1,199$900 $699 2/7$1,199 $810$699
2/8 $1,199$810 $630 2/9$1,199 $742$585

## 回顾

\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}}

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

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

655
TOC • 