没脚的雀

对不起,你属于前37%

发表于

柏拉图走进了他的麦田，给世人留下了错过与后悔。

—— 沃兹基·索德

人类是一种三维空间的生物， 我们能够在xyz 方向上任意穿梭， 从欧氏空间的任意一点跃迁到另外一点。可是啊，在第四个维度——时间轴上， 每一个人也就只能缓缓而前， 无法预知未来亦未能改变过去。每一条生命的长河总会在某个时间节点与某一条河流交汇。 从我们呱呱落地遇见那两个赋予我们生命的人开始，到牙牙学语遇见与我们相交一生的伙伴，再到灵魂相认找到灵魂的另一半。个中关系， 有一些是我们可以无法选择的， 而有一些确实我们可以选择的。就比如女生选男票。有了选择权， 按照人类最正常的想法就是： 啊， 选最好的。 可是， 怎么样的才能选择出最好的？ 有人说，这个问题可以称为“拒人问题”， 因为，你为了选择得到最好的， 总要把某些向你表白的男生拒掉， 而采用怎么样的拒绝人的策略才能是你最终选择一个最好的男生。

问题描述

现有一有脸有智商有身材的女生， 面对着排着队拜倒在自己石榴裙下的一波男生， 女生自己有一个对男生的评分函数， 假设该函数是函数式的(即对同一个男生的评分不随时间的改变而改变)，这一波男生随机的按照一定的顺序来想女生表白， 一旦女生拒绝了， 该男生基本不会回头，一旦女生接受了， 后面的男生就都哭去吧。 问： 女生在无法提前得知谁会想自己表白的条件下， 如何才能够从这些男生中找到评分最高的那个？

每次遇到一个优秀的男生，女生也许会想是拒绝好呢还是接受好呢？如果接受了， 万一下一个更好岂不是亏大了；可是如果拒绝了，那就有可能过了这个村，没了这个店了喔。很是烦躁！

不怕， 女生是有智商的。怎么办呢？ 嗯， 先跟前面几个小男生玩玩，大概了解以下这一波男生都什么水准。有了一个大致的了解之后， 开始对后面的男生认真的考虑，选择第一个比之前所有男生都要优秀的人；直白点讲，就是直接拒绝前面k个男生(炮灰了)，从第k+1个男生开始考虑， 将第一个比前面k个男生都好优秀的人认作男票。这里的k的选择呢，不能太大也不能太小。如果太大了， 可能把最好的男生拒绝了； 如果太小，可能后面没法等到最好的男生想自己表白就接受了一个次优的。问题变成了， 如何选取k，使得女生选到最优的男生的概率是最大的

最大化选中的概率

我们假设女生一生中会遇到n个男生向她表白，而最优男生随机出现在k个次序上。上面的问题用概率来表示则是：

p_derive

由于最优男生随机出现， 那么

p_i_biaobai

接着，看看第一个子项——最优男生在第i个表白的条件下， 女生选到的他的概率。显然， 如何最优男生出现在前k个位置，直接成了炮灰，这个概率为0； 如果， 最优男生出现在k之后，要想选中他， 则必须前i-1个表白的男生中最优的的男生出现在前k个位置， 保证第k+1位到i-1位男生都不被选择， 再一次，因为男生的表白次序随机， 该事件概率为$\frac k {i-1}$则

p_i_cond

所以，问题变成了最大化下面的式子：

p_i_expre

关于最大化上面的概率？ 基本上就是利用黎曼积分的定义， 最后得到了

der

令

compute

也就是说 k/n = 0.37 表示的是， 被拒绝的人数占总表白人数的37%😏， 也就是说，如果你知道一生中有多少人会向你表白，你可以把前面37%的男生都拒绝掉， 这样你最后选择最优的男生的概率是最大的。

有人可能会说， 怎么可能知道有多少人会想自己表白！！！一看你就没有修过随机过程。。。假设像女生表白的男生人数服从齐次泊松过程(生活里面很多计数过程服从泊松过程)。这样一来，表白男生的达到间隔服从指数分布。然后，再假设女生的人生很有规划， 从20岁开始有人表白， 大致到30岁结婚(假设原谅她这种剧情不会在女生身上上演)。那么(30 - 20)* 0.37 + 20 = 23.7岁之前表白的男生就可以充当炮灰了。然后，可以开始考虑后面的。(所以，成了炮灰的各位，你选对时间了吗？)

所谓上有政策，下有对策， 别说我没给大家留活路啊，表白之前，问问人家女生的打算，算算这个表白时间，加油， 我很欣赏看到这里的男生们！你们可以的。

以上一切纯属YY， 如有模仿，后果自负。

听说你不信，待我给你模拟一遍如何

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
%pylab
def rejectK(k):
    def pick(boys):
        maxK = max(boys[:k])
        m_index = k + (boys[k:] > maxK).argmax()
        return m_index
    return pick
    
def simulate(k):                       ## simulate函数对拒绝前k个的策略进行10000次模拟， 返回选中最佳男生的次数
    boys = np.arange(100)              ## 表白的男生有100个
    girl_date_and_choice = rejectK(k)  ## 某个女生采用了拒绝前K的策略
    hit = 0
    for i in range(10000):             ## 模拟10000次该过程
        np.random.shuffle(boys)        ## 随机打乱男生们的表白顺序， 男生的编号越大， 说明女生对他评分越高
        if boys[girl_date_and_choice(boys)] == 99:  ## 如果女生选中了 编号为99 的男生，说明选中了最佳男生
            hit += 1
    return hit


results = [simulate(i) for i in range(1,100)]   ## 模拟从1 到 99 的策略， 得到每个策略下；
bar(list(range(1,100)), results)                ## 选中最佳男生的次数
t = [sum(results[i*10:(i+1)*10]) for i in range(10)]
bar(list(range(10)), t)
f = lambda x: -x * log(x)
plot(np.linspace(0.0001, 1), f(np.linspace(0.0001, 1)))

画出来的结果图如下：

  1. 1 到 99 的拒绝策略下， 选中的次数
    simulation

    在这次模拟结果中，最大值并不是在 37 ， 而是在33， 但在 30 ~40 的区间的次数，比别的区间的次数都要大。

  2. 把模拟结果按照每10个求和
    simulate10
    也可以看出， 在30~40 的区间中选中的次数是最多的。

  3. 再来看看 f(x) = -x * lnx在区间[0, 1]的图像
    function

  4. 把上面的的模拟结果归一化
    fill

    ​基本与函数 -x*ln(x) 吻合

所以呢，讲道理的话，概率P(选中最佳男生;k)​ 在k =1/e ​ 取得最高值，也就是 大概在 37% 左右；但是由于随机性的问题，每一次模拟的结果总会出现一点偏差，并不一定保证模拟结果中拒绝前37个人的策略，选中最优男生的次数就最大。

后记

  • 各位大佬如果以后要拒绝我，可以说得委婉一点，说个你属于前37%或者直接37，咱就知道乍回事了；
  • 上帝通过概率论馈赠了我们他的思考方式，却不给与我们只属于他的能力。即使你知道了拒掉前37%的人，最后你能够选到最好的概率是最大的。你并不知道你是否身处被上帝选中的那个能够选中最优男生的世界里面；
  • 那么既然我们都没法知道我们的选择是否最佳，那不如，快快乐乐的当个唯心主义者。如果接受了， 坚定的认为自己的选择是最佳的；或者说努力让自己的选择成为最佳的选择咯；如果拒绝了， 坚决认为后面会有更好的。哎， 各位选择困难症要犯了。

参考链接

死理性派恋爱法：拒绝掉前面37%的人(参考链接里面没有说公式怎么来的，模拟的似乎也不是很合理)

大佬给口饭吃咧