ZT：出轨-组合数学

Zach按：作为一个geek，这篇文章太对我的胃口了……http://blog.renren.com/blog/246146320/443963812


出轨-组合数学
2010-01-28 19:11 | (分类:成人栏目)


应老婆大人命令，现在弄篇关于出轨的文章。uw大部分学数学的，那我就从数学方面谈起。以下是去年看木遥写的一篇文章，分享给大家，并祝信奉一夫一妻制的各位，从一而终，之中不出轨，出轨了也不被抓到。

话说在1962年，两个数学家David Gale 和Lloyd Shapley提出了下面的问题：
给定若干个男生和同样多的女生，他们每个人都对所有的异性有一个心理的偏好次序。是否存在一种男女配对组合构成一种稳定的组合关系？这里稳定组合的意思是说，不存在两个非伴侣的异性对彼此的评价比对各自伴侣的评价还要高。（可以理解，这样的异性太容易红杏出墙了，所以是某种不稳定因素。）进一步的问题是，在已知每个人对异性的偏好顺序的情况下，怎样求出这种稳定组合方式（如果它存在的话）？你可以理解为这是数学家们替月老问的问题：给定一群孤男寡女，寻找一种牵红线的方式，以确保把红杏扼杀在摇篮里。
这一问题被称为稳定婚姻问题。它有很多种可能的解法。为了让大家相信数学家不是真得如此无聊，我要指出它确确实实是一个地道的组合数学问题，有其特定的数学价值。当然啦，它也有很多别的背景和应用，比如用来在若干个公司和应聘者之间进行招聘中介……但是数学家们怎么会放过如此八卦的一个名字呢？于是它就这样流传下来了。
话说回来，有很多组合数学问题都可以如此这般的翻译为生活中的问题。比如著名的Hall定理：给定n个有限集合（其间可以有交集），如果其中任意m个集合的并集的元素个数都不小于m，那么一定存在n个不同的元素，使得它们正好依次存在于这n个集合之中。我相信没有人明白以上这是在说什么。可是它有一个很好的解释：把那n个集合想象成n个男生各自心仪的女孩子们（一般来说都不止一个），中间的那个条件是说，如果对于其中任意一部分男生，他们喜欢的女孩子的总数都不少于这组男生的人数（这个条件是必要的，否则就打起来了），那么总的说来一定存在一种办法给每个男生都分配一个女生恰好是他喜欢的。
听起来真是令人心情愉快啊……
回到一开始提到的稳定婚姻问题，给定每个人关于异性的偏好排序，要寻找一种男女配对组合构成稳定的组合。Gale 和Shapley不但提出了这个问题本身，而且给出了一种著名的解法。这个解法可以描述为如下的求偶过程：
首先，让这些男生去向他们最心仪的女生求婚——这是数学家们的原本的用词。如果你觉得太快了的话，让我们暂时改成表白吧……
然后，等所有男生表白完毕后，所有的收到表白女生们都从自己的表白者中选择自己最喜欢的人接受为男朋友。没人表白的女生只能暂时等一等了，不要着急，表白会有的。
以上过程称为“一轮”。之后的每一轮都按照类似的方式进行。首先由还处于单身状态的男生们每个人再次向自己还没有表白过的女生中自己最喜欢的人表白（无论人家是否已经有了男朋友），然后，等所有单身男生表白完毕后，所有的收到表白女生们都从自己的表白者中选择自己最喜欢的人接受为男朋友。如果原来有男朋友而表白者中有自己更喜欢的，不要犹豫，换之。等到尘埃落定之后，再开始如上所述的新的一轮表白。
依此类推。可以证明的是，这个过程一定是会终止的，也就是说，不会陷入任何死循环。并且一旦终止，每个人都会找到一个伴侣。更关键的是，这个过程最终得到的一定是如前所述的“稳定组合”：不存在两个非伴侣的异性对彼此的评价比对各自伴侣的评价还要高。——这几个事实都不难证明，有兴趣的话可以自己试试看。
所以这就得到了稳定婚姻问题的一个解（顺便也证明了解的存在性）。但是真正有趣的部分还在后面。一般来说，给定若干个男生女生和他们之间的偏好关系，稳定组合存在不止一种。上述“算法”只是给出了所有可能的稳定组合其中之一而已。但是这个特定的解具有某些特别的性质：可以证明（这一次证明不很容易了），上述方式得到的稳定组合和所有其他的可能的稳定组合相比，是对男生最优而对女生最劣的。
确切地说是这样：
它是对男生最优的。也就是说，对每个男生来说，按照这种方式最后找到的伴侣，是在所有的稳定组合中自己可能具有的伴侣中自己评价最高的。——注意这并不等于说被个男生都能追到自己最喜欢的女生，而只是说，他一定能追到“有可能和他在稳定组合中在一起的女生”中自己最喜欢的。有些女生虽然很好，但是和他在一起是不可能形成稳定组合的。这就是人生啊……
另一方面，它是对女生最劣的。也就是说，对每个女生来说，按照这种方式最后找到的伴侣是在所有的稳定组合中自己可能具有的伴侣中自己评价最低的。同样的，这也不等于说每个女生都只有和自己最不喜欢的男生在一起，而只是说她最后的男朋友会是所有“有可能”的男生中自己觉得最勉强的。不过这样听起来也已经很悲惨了。
这两个结论并不直观，因为看起来在上面所描述的过程中，女生是相对占有优势的。作为男生，需要很辛苦地去不断表白，然后被拒，再表白，再被拒……而女生只要随心所欲挑选就好，而且还有随时更换男友的权利（在上面的规则里男生是不能主动提出分手的）。为什么结局会是如此？
但是如果仔细思考上面所描述的规则，会看到男生至少有一样优势——也许是至关重要的优势：他们是主动方。主动的好处是，即使一次又一次的被拒，他也仍然可以和剩下的女生中自己最喜欢的在一起。而对于女生来说，纵然有再多挑选的自由，可是一个女生也许永远也等不到自己最喜欢的男生来追自己——或者在她等到之前，游戏就已经结束了。

阅读(260)| 评论(3)| 分享(22)

这个太牛掰了

鼓掌的猴子
Any chance to post proof to the lemmas mentioned?

呵呵 太有才了~~

鼓掌的猴子
Any chance to post proof to the lemmas mentioned?
小K 发表于 2010-2-23 21:19

我也很想看那个证明……越往上学越能感受到数学之美了，呵呵

想起来当年看见.632证明的时候，哗一下给震慑了。
问题：（i.e. bootstrap, ie. sampling with replacement)
现有n个样本点，每次抽样都是可以重复的抽取出n个来，组成新的sample 做统计
请问这样取样N次，某特定样本A一次都没被抽中的概率是多少？

深奥了。。

想起来当年看见.632证明的时候，哗一下给震慑了。
问题：（i.e. bootstrap, ie. sampling with replacement)
现有n个样本点，每次抽样都是可以重复的抽取出n个来，组成新的sample 做统计
请问这样取样N次，某特定 ...
小K 发表于 2010-2-24 00:36

[(n-1)/n]^(n*N)？小K姐姐，.632是什么东西？

[(n-1)/n]^(n*N)？小K姐姐，.632是什么东西？
zach 发表于 2010-2-24 01:56

基本是对的。如果写成(1-1/N)^N，when N goes to infinity, this value goes to 1-e^(-1) which is  .368.  Freshman year calculus.

于是，某特定样本被选中的概率就是0.632

bootstrapping is one of the basic model selection and assessment methods.
this formula above is used to demonstrated how the straightforward bootstrapping estimator for a given statistic can be biased

Based on this a bunch of NB guys developed similar estimators that took account of this bias better and better, e.g. .632 estimator, .632+ estimator

anyway these are really going pretty deep into stats, I am just impressed that freshman yr calculus can turn out to be very useful in such a simple way.

基本是对的。如果写成(1-1/N)^N，when N goes to infinity, this value goes to 1-e^(-1) which is  .368.  Freshman year calculus.

于是，某特定样本被选中的概率就是0.632

bootstrapping is one of the bas ...
小K 发表于 2010-2-24 02:04

嗯。中学的时候一直很想知道那些无理数是怎么弄出来的，等到了大学一下就被e的美震撼了～