Monthly Archives: July 2016

调查问卷的有效性(2)相对误差

\begin{equation}Pr(|\hat{p}-p|\geq 5\%)\leq 5\%\end{equation}

上一回我们讲到当p本身很小的时候,容易被5%(绝对误差)给淹没掉,导致结果的不可信。我们可以引入相对误差,把(1)式转换为如下的不等式

\begin{equation}Pr(|\hat{p}-p|\geq\delta p)\leq\epsilon\end{equation}

同理,我们可以用

\begin{equation}\hat{p}=\frac{x_1+x_2+...+x_n}{n}\end{equation}

代替\hat{p}(建议先看上一篇博客),转换为

\begin{equation}Pr(|X-np|\geq\delta np)\end{equation}

类似的,X=x_1+x_2+...+x_nE(X)=\mu=np,所以(4)式等价为

\begin{equation}Pr(|X-\mu|\geq\delta\mu)\end{equation}

Continue reading

调查问卷的有效性(1)绝对误差

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

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

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

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

有趣的交互式证明

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

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

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