Hash, Hash and Hash

(更新中)
Universal Hashing
A probability distribution H over hash functions from U to $\{1, \ldots, M\}$ is uni-
versal if for all x = y in U , we have
$$
Pr\{h(x) == h(y)\} \leq 1/M
$$

换言之当h是从H中随机选取,任何两个元素collide的概率不超过1/M.

(c,k)-Universal Hashing
$\{h_i\} h_i : U \to R$, for any distinct elements $x_1,\ldots,x_k \in U$, and $y_1,\ldots,y_k \in R$, we have
$$
Pr\{h_i(x_1) = y_1,\ldots, h_i(x_k) =y_k\} \leq c/|R|^k
$$

[数学]关于Coupon Collector的问题

原题在这里.简单的说,市面上有一种coupon有n个样式.每一个你新收集的coupon以1/n的概率为其中任意一种.如果说你需要收集T个coupon你才能把所有的样式都拿到,那么T的均值是多少呢?

假设我们手里已经有了i-1种不同的coupon.那么在收集了i-1种不同coupon后,出现一个新式的coupon所需要的尝试次数服从参数为pi的几何分布.pi=(n-i+1)/n　也就是出现第i种新coupon的概率.

E[T]=1/p_1+1/p_2+\cdots+1/p_n =  \frac{n}{n}+\frac{n}{n-1}+\cdots+\frac{n}{n} = n H_n\approx n \ln n

该问题的一个变种是:求当我们收集齐了所有n种coupon,其中某个样式(比如印着机器猫的)coupon只拿到了一张的概率.

该珍贵的coupon,可以是第1种收集到的,也可以是第j种收集到的.j服从1,...,n,的均匀分布.如果它是第j种收集到的coupon,则后面不出现该coupon的概率是 1/(n-j+1). 所以全概率是:

\sum_{j=1}^n \frac{1}{n}\frac{1}{n-j+1}= \frac{H_n}{n}\approx \frac{\ln n}{n}

[数学]一道关于硬币的概率题

硬币不知道fair还是不fair,第一次扔是head,第二次让你赌,你赌哪个,概率多少? zz from mitbbs
SOL: 采用Bayes. 设硬币得到head的概率为p. 因为硬币不一定是fair, 所以这里p实际是一个随机变量. 在没有其他信息的情况下,我们假设p的先验是一个0到1之间的均匀分布,即U[0,1]. 这种情况下, 得到head的概率为:

P\{head\} = \int_{p=0}^1P{head|p}\mathrm{d}p = \int_{p=0}^1p\mathrm{d}p=\frac{1}{2}

投掷硬币得到head, 在这种情况下,p的条件概率密度函数f(p|head)就不再是U[0,1]. 这是因为p越大越容易得到head,因此得到head的时候以更大可能观察到比较大的p而不是等概率.f(p|head)的密度由下式求得.注意这里f(p)=1(均匀分布),以及P{head|p} = p.

f(p|head) =\frac{P\{head|p\}f(p)}{P\{head\}}=2p

所以给定head情况下,p的点估计:

\hat{p} = \int_{p=0}^1 2p p\mathrm{d}p = 2/3

再来一道类似的:6个小孩,3女2男,还有一个性别未知.随机选择6人中的一个,发现是男孩.那么未知的那个小孩是男孩的概率?
SOL: 假设未知的那个小孩是男孩的概率是p. 假定p=1/2
选出来的小孩是男孩的概率是
P{pick a boy}=P{pick a boy|unknown=boy}P{unknown=boy}+P{pick a boy|unknown=girl}P{unknown=girl}
=3/6*1/2+2/6*1/2=5/12

则
P{unknown=boy|pick=boy} = P{pick=boy|unknown=boy}P{unknown=boy}/P{pick a boy}=3/5

[数学]一道小学应用题

近日，网友“跳水白菜”在天涯重庆上发帖，希望借网友的智慧，解答出一道小学六年级的数学题。

“一辆大客车和大货车分别从甲乙两地出发，经过7个小时相遇，然后仍按各自的速度前行，3小时后，大客车距乙地120公里，大货车距甲地 160公里，求甲、乙两地的距离是多少千米？”

解答出这样一道数学题，在最初回答问题的网友看来，似乎是一件很简单的事情。众多网友都给出了步骤和答案，但大多都采用了2元1次方程式，甚至3元1次方程式。有网友提出了尖锐的问题：小学生是没有学习过2元1次方程式的，更别谈3元1次方程式，这样的题目就不能使用这种方式解答。面对这样的题目，其内容和解答方式雷翻了众多的网友。

SOL:其实这道题不需要用到方程.我从小就喜欢把那些看似要用解方程才能做出来的题目硬是分步计算出来.这里给出这道题目的分步计算方法:
甲乙两地距离=甲速*7+乙速*7,同时又有 甲乙两地距离=甲速*3+乙速*3+120+160
我们可以得知 (甲速+乙速)*4 = 280 => 甲速+乙速 = 70 (公里/小时)
甲乙两地距离=70*7 = 490 (公里)