概率题求助 - V2EX

This topic created in 2074 days ago, the information mentioned may be changed or developed.

有没有概率比较好的朋友，想算一下 bloomfilter 的理论负载。

题目可以抽象为如下:

目前有一数组，长度为四万，内容全是 0 。每次调用一函数，随机选取其中四个值改为 1，不论该数据本来是 1 还是 0 。(单次调用中四个值一定不同，重复调用中则不影响)

调用一万次函数后，期望数组中还剩多少 0，多少 1 ？

同理，还可以引申成以下题型:
期望 0 的数量超过 90%，期望调用多少次函数？

函数

调用

期望

概率

5 replies • 2021-03-04 19:07:15 +08:00

xkeyideal

Mar 4, 2021

理论不会，写个代码跑一下，如果没写错的话，1 的个数在 21900(+-100)

xkeyideal

Mar 4, 2021

第二问：不超过 1210 次

LeeReamond

Mar 4, 2021 via Android

@xkeyideal 跑都可以跑，不需要啊(悲)

xupefei

Mar 4, 2021

第一问：
调用一次一个 bit 被选中的概率: 4/40000
调用一次一个 bit 没有被选中的概率: 1-4/40000
一万次调用里一次都没被选中的概率: (1-4/40000)^10000
一万次调用后没被选中过的 bit 数量：(1-4/40000)^10000*40000 = 14714

第二问把 10000 换成 x 自己解方程。

LeeReamond

Mar 4, 2021 via Android

@xupefei 大佬再问一题，假设调用一万次后有 14714 个 0，剩下都是 1，第 10001 次调用恰好选取全是 0 而没有 1 的概率是多少