每年春晚过后，央视又要吹嘘说今年春晚收视率创新高了，但是我们总感觉央视在骗我们，因为我是越长大越不看春晚了[笑cry]，所以收视率到底是怎么统计出来的，央视的说法是否靠谱呢？

最近的美国大选真是热闹，很多机构都会发放一些调查问卷，然后统计出希拉里或者唐纳德的民众支持率是多少，但是我并没有收到调查问卷，凭什么就得出了民众支持率了，意思是把我排除在民众之外咯？所以引出这样一个问题，调查问卷是否可信，即调查问卷的有效性。

其实，央视统计收视率并不要问全中国14亿人口有多少人看了春晚，他只需要从14亿人口里面随机抽$n$个人，问一下这$n$个人里有多少人看了春晚，然后把看的人数除以总数就大概估计出全国的收视率了。同理调查民众支持率也是一样，只需要随机调查$n$个人的意向，把支持希拉里的人数除以总数就大概得到了希拉里的支持率。

但是你要问了，通过抽样调查出来的收视率和支持率靠谱吗，需要随机抽样多少人才能得到一个比较好的全局近似解呢？今天我们就来解决这个问题。 Continue reading →

你是否想过如下问题：怎样向色盲证明两只袜子的颜色是不一样的？怎样证明两个图是不同构的？怎样证明一个数是二次非剩余的？

咋听起来觉得很有意思吧，色盲是区分不了颜色的，怎么能让他相信两只袜子的颜色不一样呢。图同构问题目前既没有被证明属于P，也没有被证明属于NP-Complete。二次非剩余问题也没有被证明属于NP。

这些听起来很“难”的问题，却可以通过交互式证明进行证明，下面先通过“向色盲证明两只袜子的颜色不同”这个有趣的例子一窥交互式证明的强大。 Continue reading →