分享一道G家昂赛题

我感觉自己运气非常好，题目都不难。楼主碰到2位三哥面试官，都非常友善，所以大家别怕。
楼主自己不太看面经，因为很多题看到第二次就懒得做倦怠没激情了。但是刷题对我还是很有帮助的，毕竟转专业敲代码不熟。

分享一道比较有意思的题目：
给一个fair coin，对任意正整数n，如何模拟出1/n的概率。follow up:简要证明，然后写这个程序。

由于楼主本身就是做概率方向的所以一会儿就想出来了，但是相信对大部分农友来说此题还是挺另类的：）

关注一亩三分地公众号：
Warald_一亩三分地

这样行吗，取一个数k = ceil(log2(n))，扔k次，把这k次的结果看成一个binary number，这个数小于等于n-1的概率是 n/(2^k)，反复投掷知道这个数小于等于n-1为止，然后再看这个数是否等于0. 证明就是楼上说的条件概率吧

关注一亩三分地微博：
Warald

二进制？ 字数字数

是利用conditional probability么？

sqrl 发表于 2016-11-20 02:48
二进制？ 字数字数

. 1point3acres.com/bbs对                              

kunge12345 发表于 2016-11-20 03:03
是利用conditional probability么？

对                        

daniel_hl 发表于 2016-11-20 03:29
这样行吗，取一个数k = ceil(log2(n))，扔k次，把这k次的结果看成一个binary number，这个数小于等于n-1的 ...

perfect!

Griffith♂Guts 发表于 2016-11-20 03:34
perfect!

非常感谢分享！

daniel_hl 发表于 2016-11-20 03:29
这样行吗，取一个数k = ceil(log2(n))，扔k次，把这k次的结果看成一个binary number，这个数小于等于n-1的 ...

可以详细解释一下吗？不是特别理解，概率学的太差了，谢谢。

Griffith♂Guts 发表于 2016-11-20 03:34
perfect!

可以详细解释一下吗？不是特别理解，概率学的太差了，谢谢。

zhouyejoe 发表于 2016-11-20 11:46
可以详细解释一下吗？不是特别理解，概率学的太差了，谢谢。

如果投掷k次，把每次投掷的结果看作0或1（正或反），那么投k次的结果就可以用一个k位的二进制数表示，这样会得到2^k个数，而且得到每个数的概率是一样的。但是题目要求模拟1/n的概率，所以就要设法以均匀的概率产生n个数，那么产生其中一个数的概率就是1/n。

这个方法就是，选一个k使得2^k >= n。然后这样模拟1/n概率：
    1. 投掷k次，产生一个数m，范围是0～2^k - 1
    2. 如果0 =< m <= n - 1, 停止投掷，跳到3。否则跳回1
    3. m等于[0, n - 1]其中任意一个数的概率就是1/n.

daniel_hl 发表于 2016-11-21 03:14
如果投掷k次，把每次投掷的结果看作0或1（正或反），那么投k次的结果就可以用一个k位的二进制数表示，这 ...

非常感谢~

daniel_hl 发表于 2016-11-21 03:14
如果投掷k次，把每次投掷的结果看作0或1（正或反），那么投k次的结果就可以用一个k位的二进制数表示，这 ...

我的概率就是渣。。。。
没看懂为什么这么算出来是1/n

落在[0, n - 1] 之间的概率是 n/2^k; 然后，怎么得出的1/n呢
求解释

sunnyroom 发表于 2016-11-22 14:26
我的概率就是渣。。。。
没看懂为什么这么算出来是1/n

我也不太理解，但到利用条件概率是指说满足了落在[0,n-1]的条件之后，每个数的概率一样，所以投掷结果等于0的概率就是1/n了？

sunnyroom 发表于 2016-11-22 14:26
我的概率就是渣。。。。
没看懂为什么这么算出来是1/n

P(A=0 | A < n) = P(A = 0 and A < n)/P(A < n) =P(A = 0)/P(A < n) = (1/2^k)/(n/2^k) = 1/n 我的理解是这样，不一定要是0，任何在0和n-1直接的数都可以

给楼上各位概率大神跪了!

sunnyroom 发表于 2016-11-22 14:26
我的概率就是渣。。。。
没看懂为什么这么算出来是1/n

是这样的，因为投掷多轮直到结果落在[0, n - 1] 之间为止，所以得到的这个结果是[0, n - 1]中的某个数，在满足了这个条件之后，它是[0, n - 1]中任意一数的概率是1/n。

理论上证明就是15楼给出的。