未分類
26 2 月 2021

概率题求助

概率题求助

資深大佬 : LeeReamond 4

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

题目可以抽象为如下:

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

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

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

大佬有話說 (5)

  • 資深大佬 : xkeyideal

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

  • 資深大佬 : xkeyideal

    第二问：不超过 1210 次

  • 主 資深大佬 : LeeReamond

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

  • 資深大佬 : xupefei

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

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

  • 主 資深大佬 : LeeReamond

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