好久没写日志, 今天看到个有意思的问题, 也能很快说清楚, 记录一下.

问题: 有一对夫妇有两个孩子, 已知其中一个是男孩, 则另一个也是男孩的概率是多少?
候选答案一: 因为生男生女的概率都是 1/2, 每次生育都是独立事件, 所以概率是 1/2
候选答案二: 因为两个孩子的性别总共有四种等概率可能, 分别是 男男, 男女, 女男, 女女, 现在已知其中一个是男孩, 排除掉 女女 这 1/4 的概率, 所以另一个为男孩的概率是 1/3

这个问题引起了很多争论, 两种说法的支持者都很坚定. 今天看了一堆讨论, 最后发现其实是对题意理解不一致导致的, 关键问题就是 “已知其中一个是男孩” 代表了什么意思.

说 1/2 概率的把那句话理解成 “已知大孩子是男孩”, 所以把四种等概率可能排除掉了 女男, 女女 两种可能, 剩下两种可能里, 小孩子是男孩的概率是 1/2.
说 1/3 概率的把那句话理解成 “已知其中有一个孩子是男孩, 但是不知道是大孩子还是小孩子”, 所以只能排除 女女 这一种可能, 剩下三种可能里, 另一个孩子是男孩的概率是 1/3.

感觉我应该把分歧说清楚了. 下次如果有人遇到类似问题的时候, 可以看看问题中的条件是否有 tricky :P

十月份的时候写了一篇 面试题, 随机抽样问题及扩展, 当时这个 blog 没整好, 发在了好几个地方

• http://www.yewen.us/blog/2011/10/random-select-problem/
• http://hi.baidu.com/whusnoopy/blog/item/4f54b3de5d708344cdbf1a08.html
• http://blog.renren.com/blog/bp/Q7fr2sueah

前几天跟 Lee.Mars 聊, 又把这堆问题解答了一遍, 并指出其中一个问题的 bug.

原始版, 数据流 n 选 1. 构建一个可容纳一个数的 buffer, 数据流中第 i 个数过来时做一次 [0, 1] 的 random, 如果小于 1/i, 则更新 buffer. (证明过程略, 很简单的)

buf = 0
cnt = 0
for i in sys.stdin:
  cnt += 1
  if random.random() < 1.0/cnt:
    buf = int(i)

print buf

加强版, 数据流 n 选 k. 同上, 构建的 buffer 大小变为 k, 每次 rand 小于 k/i 时, 将 rand*i 对应的 buffer 更新

k = 3 
buf = []
cnt = 0 
for i in sys.stdin:
  cnt += 1
  rd = int(random.random()*cnt)
  if rd < k:
    if cnt <= k:
      buf.append(int(i))
      buf[cnt-1] = buf[rd]
    buf[rd] = int(i)

print buf 

带权版, 带权数据流 n 选 1. 同原始版, 只是对权重为 w[i] 的第 i 个数, rand 时判断是否小于 w[i]/SUM(w)

sum = 0
buf = 0
cnt = 0 
for i in sys.stdin:
  cnt += 1
  sum += int(i)
  if random.random() < float(i)/sum:
    buf = int(i)

print buf 

带权选 k 版. 这个有 bug, 无解, 因为无法保证最后选出来的 k 个数, 其 SUM(w[k1..kk])/sum(w[1..n]) = k/n, 那个概率无法算

分布式版, m 个序列最后选 k. 每个序列先按加强版选 k 个, 然后将 m*k 个数放到一起, 做带权版的 n 选 k. 由于带权选 k 版有 bug, 所以这里会有一定误差. 而实际上一般的分布式框架是可以保证每个序列数据规模分布都比较均匀, 所以最后的 m*k 个数可以当无权版直接选 k, 这样的误差在工业应用是可以接受的

注: 从 n 选 k 那个就可以很容易看出来, 这其实就是那个把一个序列打乱成随机状态的算法简化, n 选 1 只是 n 选 k 的一个特例

今天看到张栋在新浪微博上说一个他当时被 Google 面试时碰到的一个问题 (其实我也碰到过), 觉得这个问题很有意思, 我自己也在工作中碰到过该问题的实际应用, 扩展一下, 大家一起活动下脑子玩玩 :) (答案我就不说了, 不然多没意思)

原始版
有一个店老板, 他决定从每天光顾他的店的顾客中随机选出一个人, 在当天打烊时给这位顾客发去一份小礼品, 问怎样选才能保证随机 (我表达能力太弱, 没看懂的请直接看抽象版. 关键点, 顾客不是同时来, 所以没法让这一堆人站好随机挑, 而且每天会来多少人你不知道, 可能打烊前突然来一大拨人, 老板比较呆, 只能记住一两个人, 没法把所有人的信息都记录下来)

抽象版
有一个数据流输入过来, 请在数据流停止时, 返回数据流中的随机的一个数. 注意, 数据是流, 只能一次读, 而且数据流很大, 本机无法完整存储 (最多也就很少几条)

实际应用
从每天的日志中, 对符合条件的日志, 随机抽出一条来做校验, 数据太大只能一次读过去, 要保证是随机的

加强版
如果店老板每天不是送一个人礼品, 而是送 k 个人礼品, 怎么办?

加强版的抽象
从数据流中返回随机的 k 个数

加强版的实际应用
从每天的日志中随机挑出 k 条来做校验

带权版
每个顾客有一个会员级别, 级别越高的人获奖概率越大, 怎么办?

带权版的抽象
数据流中每个数有权重 w[i], 对数字 i, 返回他的概率从 1/n 变为 w[i] / SUM(w[j], j from 1 to n). k 个数的情况类推

带权版的实际应用
从日志中按权重挑出一条或 k 条来做校验

分布式版
老板开了 m 家分店, 希望还能按平均概率给随机一位或 k 位顾客奖品, 怎么办?

分布式版的抽象
有 m 个数据流, 最后返回的是 m 个数据流合并后的随机数, 一个或 k 个

分布式版的实际应用
日志太大, 一台机器搞不定, 分布式抽取随机的一条或 k 条来做校验 (我下星期会做这个, 所以不要说面试题都是面试官蛋疼想出来坑爹的…)