淘客熙熙

主题:【原创】六度空间考 -- 荷子

共:💬14 🌺31
全看树展主题 · 分页首页 上页
/ 1
下页 末页
家园 【原创】六度空间考

还是八卦,所以在龙门

很早就想聊这个,今天又看到呆鹅和燕兄的对话呆鹅:【感慨】世界真小,忍不住要胡说一番了

六度空间这个词儿,似乎是和web2.0,SNS一起火起来的,俺一个师弟的博士论文和这个有关,多少听说一些,学名是小世界网络和复杂网络理论。

但这个词儿对俺来说,要早得多。

想当年俺是从一本“盗版书”——《从惊讶到思考——数学悖论奇景》上第一次看到这个词儿的,那应该是中学的时候,在妈妈学校的图书馆看到的,其实那是《科学美国人》的一个选集,很多内容在马丁加德纳的《啊哈!灵机一动》里面都有。

本书译自《科学美国人》杂志社发行的一套数学悖论幻灯片“Paradox Box”(悖论箱)的说明。“Paradox Box”是第一次采用幻灯形式来集中演示一些生动有趣而又异乎寻常的悖论,还配有一套录音带作解说,以此来激发人们对数学的兴趣。遗憾的是,我们无力把包括幻灯片、录音带在内的全套材料介绍给国内读者,只能将幻灯片的全部画面复印出来,附以解说,以连环画的形式给出各种悖论小故事,这样虽不如原有材料生动活泼,倒也不失其新颖有趣之处。

想当年看到那么一本书的确很震惊,虽然大多数关于逻辑,概率,数,几何,统计和时间的悖论早有耳闻,但妙趣横生的卡通图解的确非常吸引人。

书的封面

点看全图

第五章的第四个故事——小世界悖论

点看全图

M:近来很多人相信巧合是由星星或别的神秘力量引起的。

点看全图

M:譬如说,有两个互不相识的的人坐同一架飞机。二人对话:

甲:这么说,你是从波士顿来的啰!我的老朋友露茜·琼斯是那儿的律师。

乙:这个世界是多么小啊!她是我妻子最好的朋友!

M:这是不大可能的巧合吗?统计学家已经证明并非如此。

很多人在碰到一位陌生人,尤其是在远离家乡的地方碰到一个生人,而发现他与自己有一个共同的朋友时,他们都会成到非常惊讶。在麻省理工学院,由伊西尔领导的一组社会科学家对这个“小世界悖论”作了研究。他们发现,如果在美国随便任选两个人,平均每个人认识大约1000个人。这时,这两个人彼此认识的概率大约是1/100000,而他们有一个共同的朋友的概率却急剧升高到1/100。而他们可由一连串熟人居间联系(如上面例举的二人)的概率实际上高于百分之九十九。换言之,如果布朗和史密斯是在美国任意选出的两个人,上面的结论就表示:一个认识布朗的人,几乎肯定认识一个史密斯熟识的人。

最近心理学家斯坦利·米尔格拉姆用一种方法逼近小世界的问题,学生们很容易试一试它。他任意地选择了一组“发信人”,给每一个人一份文件,让他发给一个“收信者”,这个收信者是他不认识的,而且住在这个国家另外一个很远的地方。做法是过他把信寄给他的一个朋友(是一个他没有深交的朋友),也许他很可能认识那个收信者,这个朋友再接着发信给另一朋友,如此下去,直到将文件寄到认识收信者的某人为止,米尔格拉姆发现,在文件达到收信者手中之前,中间联系人的数目从2到10不等,其中位数是5。当你问别人这到底需要多少中间联系人时,他们多数猜想大约要100人。

米尔格拉姆的研究说明了人与人之间由一个彼此为朋友的网络联结得多么紧密。由于这一结果的启示,两个陌生人在离家很远的地方相遇而有着共同的熟人就不足为怪了。这种关系网络还可解释很多其他不寻常的统计学现象,例如流言蜚语和耸人听闻的消息不胫而走,新的低级趣味的笑话很快四处蔓延,同样地,一条可靠的情报也在料想不到的短时间里就为很多人知道了。

感谢没有版权制约前的科学出版社,科学技术文献出版社等一批有识之士

可惜的是后来俺没有老驴兄的胆量(我不是马甲:【原创】移居台湾:中国化学家轶事(二十)钱思亮、周厚复 ,尽管这本书才1.35元(1986)

当然,现在有电子版,俺也从北图复印留存了(附带说一句,北京高校复印店的价格的确是4分一页,已经有3年了)

有了互联网,小世界悖论的验证更加容易了,似乎师弟说过研究这个方向的测试数据库也不少,美国电影演员数据库什么的,前两年有个哥们还把水母bbs的id数据研究了一番,俺觉着吧,erdos数应该也算。

上大学的第一年,曾经和俺们宿舍老大讨论过诸多有趣的问题,好多时候吵得不亦乐乎。后来知道了,老大就是装傻,逗俺玩儿呢。嗯,想念老大。

其中也包括这个问题——比如说,俺和老大需要几个人才能认识呢?

美鳖还是土鳖,这是个问题...

关键词(Tags): #鹿透社八卦数学

本帖一共被 1 帖 引用 (帖内工具实现)
家园 扛不扛?

点看全图

外链图片需谨慎,可能会被源头改

家园 好像还有一个:就是问多少个问题就可以确定对方想的事情

本帖一共被 1 帖 引用 (帖内工具实现)
家园 俺觉得,其实这道理街坊大妈最清楚
家园 不太一样吧,小包子一个

荷子:孩子是我们的老师——也来发语录(四六)猜猜看

家园 说得对

后面会大概说到这个意思

家园 和一帮人中有多少人可能是同一天生日是不是类似的问题?

去过一个聚会,正好说到有多少个人是这个月的生日,结果发现人数比较少,不太平均。就想起这个同一天生日的人数问题来了。

家园 随机抽取20人

一般至少2人的生日相同的比例超过80%

家园 有类似之处,不完全一样

一般来说生日问题是个完全随机的,如果不考虑闰年(2月29日出生)的话基本上是这样的:

多少个人当中至少有两个人同一天生日的概率大于50%?

假设是N个人,那么有

1-(364/365)*(363/365)*(362/365)*...*(365-N/365) > 50%

N等于23的时候概率就大于50%了

也就是说,假设一个小团体(班级)有23个人,其中有两个人同一天生日的概率就会大于一半

小世界网络往往不是完全随机网络,它还具有无标度(scale-free)特性,就是说网络中节点的度(degree)不服从泊松分布而服从“幂指数定律”,这一点事实上很有价值——幂律说明了为什么万维网是由少数集散节点 Google 和 Yahoo 公司等所主控的网络。(Albert-László Barabási ),后面可能会讲到这个。

1999 年,他在美国圣母大学物理系提出了无尺度网络(Scale-Free Networks)模型。他在研究万维网时,考虑到由于人们会根据多种多样的兴趣来决定链接到哪些网站,可选择的网页数量极其庞大,原以为会找到一个随机网络。然而,结果却是发现了新型的网络——无尺度网络(也有人称为无标度或自由标度网络)。他利用专用工具软件,从一个网页跳转到另一个,尽可能地收集网络上的所有连接。他发现万维网是由少数高连接性的页面串连起来的, 80% 以上页面的连接数不到 4 个。然而只占节点总数不到万分之一的极少数节点,却有 1000 个以上的连接。其中有一份文件竟然已经被超过 200 万的其他网页所链接!他发现网页的连接分布并不是随机网络的泊松分布,而是服从“幂指数定律”(Power Law ,通常简称为幂定律或幂律):在网络中,连线数只有某节点一半的那些节点的数量为该类节点数的 4 倍。幂律说明了为什么万维网是由少数集散节点 Google 和 Yahoo 公司等所主控的网络。随机网络中绝对不可能出现集散节点。他在解释采用“无尺度”用语时指出:“当我们开始研究万维网时,原本预期节点会像人类的身高一样呈现钟形的泊松分布,但是,后来发现有些节点不遵循这种分布。我们就像突然发现了很多身高百尺的巨人一样,大吃了一惊。因此,我们想出了‘无尺度(Scale-Free)'这样的用语”。

家园 错啦,小呆

20个人中至少两个同一天生日的概率只有41%

家园 飘走
家园 【补充材料】生日悖论

还是《从惊讶到思考——数学悖论奇景》上的

第五章的第五个故事——你属于哪一宫

点看全图

M:这四个人第一次见面。如果他们四个至少有两个人属于黄道十二宫中的同一宫,这岂不是非常巧的偶合吗?[*]你也许以为,这是非计凑巧的事,而实际上这种巧合在十次中就会大约发生四次。

假定每个人都以相同的概率出生在十二宫之一,那么四个人中至少有两个人属于同一宫的概率是多少?

让我们用一副牌来模拟这种情况。先抽掉四张K。这副牌现在就是四种花色,每种12张。我们用一种花色代表一个人,每个点数代表一个宫。如果我们从每一种花色中任抽一张牌,四张牌里至少两张点数一样的概率是多少?很明显,这就和四个陌生人中至少两人有同样的黄道宫的概率一样。

解决这个问题最简单的方法是先算出没有两张牌的点数相同的概率,再把它从1中减去,就得到我们所要的概率。

如果我们考虑两个花色,譬如说黑桃和红心,由于一张红心和十二张黑桃中的一张配对,只有一对是同点数的,故点数不同的概率是11/12。而一张梅花与黑桃、红心这两张牌的点数都不同的概率就是10/12,一张方块又不同于这其余三张脾的概率是9/12。这三个因子的乘积就是四张牌的点数彼此都不相同的概率,结果是55/96。用1减去这个数得到41/96,大约是4/10,它也既是四个人中至少有两个是属于同一宫的概率。这差不多是1/2,因此这种巧合毫不足怪。

这肯定是著名的生日悖论的翻版。如果有23个人无意中碰到一起,至少有两个人的生日是同一天的概率稍小于1/2。其计算过程类似于上面的黄道宫的算法,不过这里相乘的有22个因子:

点看全图

乘积是0.5073+,或者说稍大于1/2(所求概率则稍小于1/2)。用小型计算器计算这个数是一个再好不过的练习了。如果人数多于23个,则生日相同的概率会迅速升高。如果你们班的同学有40人,那么至少有两人生日一样的概率是7/10。如果有100个学生,则至少有两人生日相同的概率比之谁的生日不一样的概率是3000000比1。

建议作一些实际练习:

1)美国有几位总统的生日相同?有几个逝世的日期—样?这些结果与理论预计比较如何?(詹姆斯·波尔克和沃伦·哈丁的生日都是11月2号。托马斯·杰斐逊、约翰·亚当期和詹姆斯·门罗都逝于7月4日)。

2)一组人,若要求其中至少有两人生日在同一个月的概率大于1/2,这组人的人数最少是几?(回答是5。此时有两人生在同一个月的概率是89/144,大约是0.62)。

3)一组人,若要求至少有两人生于同一个星期数的概率大于1/2,那么这个组最少要由几个人?(回答:4,此时相应的概率是223/343,大约是0.65)。

4)若要求你所遇到的人中至少有一人和你的生日在同一天的概率大于1/2,你最少要遇到多少人?(回答:253。不是183,如果每个人只有一个生日而不会还有一个的话,就是如此。)

========

这本书真的很好,用很多生动的小例子揭示了藏在悖论后面的数学原理,特别是概率,著名的“汽车和羊”问题在本书第二章的“三个贝壳的骗局”的故事里也有介绍,当时很是引发了我对概率的热爱,后来看桥牌书和学排列组合的时候都感觉非常轻松。

打桥牌的同学都知道,最“平均”的牌型不是4333,而是4432,如果某门花色在外面有四张,22分布要比31分布概率低

从那时候起,俺就相信,概率,是一种人生态度

家园 好!河里有谁是11月19日生日的?
家园 顺便说一句

至少有两个人同一天生日,和有人和我同一天生日的概率事完全不同的

当然,西西河注册id 30k+,至少有一个和兄弟同一天生日的概率肯定也很大(大约是99.9999...999%,超过30个9)

倘若仍然要求1/2呢,大约是253左右

全看树展主题 · 分页首页 上页
/ 1
下页 末页


有趣有益,互惠互利;开阔视野,博采众长。
虚拟的网络,真实的人。天南地北客,相逢皆朋友

Copyright © cchere 西西河