标签归档:数学之美

数学之美:从“二分法”到“万物皆数”!

二分法,就是一分为二的方法。

如我们两个人,共同吃一个苹果,通常我们会从中切开,然后一人一半。

除了日常使用之外,二分法还是一个非常高效的算法,它常被用作计算机的查找过程中。

#

为了说清楚二分法,我们先来玩一个猜数字游戏:

我心里默念一个1~64之间的数,你来猜是什么数,猜的过程中你可以向我提问,但是你只能问答案是“是”或“否”的问题。

为了保证不论在什么情况下都能以尽量少的次数猜中,你应该采取什么策略呢?

答案很显然,使用二分法!

我们先是猜是不是位于1~32之间,排除掉一半可能性,然后对区间继续二分。

这种策略,能够保证无论数字怎么跟你捉迷藏,都能在log_2{n}次以内猜中,用算法的术语来说就是它的下界是最好的。

为什么这种策略具有最优下界?答案也很简单,这个策略是平衡的。

反之,如果策略不是平衡的,比如问是不是在1~10之间,那么一旦发现不是在1~10之间的话就会剩下比N/2更多的可能性需要去考虑,简单的事情有可能会变得复杂。

这种采用二分法的策略的本质可以概括成“让未知世界无机可乘”。

它是没有“弱点的”,答案的任何一个分支都是等概率的。

反之,一旦某个分支蕴含的可能性更多,当情况落到那个分支上的时候你就郁闷了。

猜数字游戏最糟糕的策略就是一个一个的猜:

是1吗?是2吗?…

这种猜法最差的情况下需要64次才能猜对,下界非常糟糕,效率很低,而且结果具有随机性。

二分法为什么好,就是因为它每次都将可能性排除一半并且无论如何都能排除一半(它是最糟情况下表现最好的)。

继续阅读

数学之美:数学学得好,赚钱也简单!

彩票怎样才能中奖?

理论上,只能靠运气。但是,如果规则设计得不好,就可以钻漏洞。

2005年2月,美国的一个彩票品种,就出现了漏洞,被麻省理工学院的学生发现了。随后的七年,这个学生反复购买这个品种,一共赚到了300万美元。

我们分析一下他是怎么做到的,以及其中的数学原理。

我依据的材料,主要来自数学教授 Jordan Ellenberg 在斯坦福大学的一次演讲(Youtube)。

#

01

期望值

彩票最重要的数学概念,叫做”期望值”(expected value),即同一种行为多次重复以后,所能得到的平均收益。

举例来说,如果每次抽奖需要2元,假设200次抽奖可以中奖一次,奖金为300元。那么,你花了2000元,一共抽奖1000次,中奖了5次,奖金为1500元。

也就是说,1000次抽奖的总收益是1500元,每次的平均收益是1.5元,这就是期望值。

它的计算公式如下:

期望值 = 300 * (1 / 200) + 0 * (199 / 200) = 1.5

期望值是1.5元,但是每次抽奖成本2元,于是净亏损0.5元。

一看就知道,这个事情是不划算的,做得越多,越不划算。

偶尔买一次彩票,倒也算了,如果你一天到晚不断买彩票,就肯定会亏很多钱(上例是每200次亏100元)。

总之,期望值是衡量彩票收益的一个关键指标。

继续阅读