问题标签 [birthday-paradox]

For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.

0 投票
2 回答
1590 浏览

c++ - 如何进行生日悖论循环

我必须做生日悖论计划作为学校的作业。我让程序运行,但似乎无法获得正确的答案。我认为这是我在check_birthdays函数中的循环的问题。

这是代码:

0 投票
2 回答
512 浏览

java - 计算一个有 400 个图块和 50 个对象的世界中至少 2 个重复的概率?爪哇

首先,我想让您知道,我已经寻找了几天的答案或可能对我有所帮助的东西,但我找不到任何东西,所以我在这里问。

我的 Java 代码中有:

包含 50 个对象的数组列表。
随机 X 和 Y 元素放入 arraylist 中的每个对象。
检查是否有重复的方法。

所以基于重复的数量(不确定这部分,但我认识的其他人似乎这样做)我需要计算在 400 个瓷砖/选择的世界中至少 2 个对象具有相同坐标的概率(20x20 )。我的代码中尚不存在 400 个图块的世界,但我必须通过考虑这一点来计算它。

至少有一个重复的概率应该是 0.95xx。

所以我知道我必须计算没有重复的概率并执行:(1 - P(NoDupes))。但是我如何计算 P(NoDupes)?

提前致谢

0 投票
1 回答
165 浏览

random - 生成*非重复*安全随机数的最佳方法是什么?

我正在研究需要安全地分配随机、短(~40 位)ID 的东西。它们需要是唯一的,这意味着在中央服务器上进行。

每次只使用一个新的 SecureRand 都会遇到生日问题,并开始花费更长的时间来生成新条目。

什么是更好的方法?

0 投票
1 回答
68 浏览

math - Calculate original set size after hash collisions have occurred

You have an empty ice cube tray which has n little ice cube buckets, forming a natural hash space that's easy to visualize.

Your friend has k pennies which he likes to put in ice cube trays. He uses a random number generator repeatedly to choose which bucket to put each penny. If the bucket determined by the random number is already occupied by a penny, he throws the penny away and it is never seen again.

Say your ice cube tray has 100 buckets (i.e, would make 100 ice cubes). If you notice that your tray has c=80 pennies, what is the most likely number of pennies (k) that your friend had to start out with?

If c is low, the odds of collisions are low enough that the most likely number of k == c. E.g. if c = 3, then it's most like that k was 3. However, the odds of a collision are increasingly likely, after say k=14 then odds are there should be 1 collision, so maybe it's maximally likely that k = 15 if c = 14.

Of course if n == c then there would be no way of knowing, so let's set that aside and assume c < n.

What's the general formula for estimating k given n and c (given c < n)?

0 投票
3 回答
505 浏览

vb.net - 为什么这个随机数生成代码不起作用?

我正在编写一个程序来证明“生日悖论”。

它为 1 到 365 之间的每一个生成一个随机数i (days(i)),函数为:

当我在 for 循环中添加断点并手动通过它时,它工作正常,但如果我只是运行程序,它会在天数(I)的每个插槽中放置相同的随机数。

任何想法为什么?


数字生成现在正在工作,但程序在使用断点调试时仍然以不同的方式工作。

这就是整个代码。它所做的是从集合中搜索两个匹配的随机数。整个过程重复 100 次,它应该计算结果,但它只输出 0 或 100。

0 投票
2 回答
1121 浏览

java - Java:如何创建一个包含随机生日的人的房间?

这是我学习 Java 的第二天。我遇到了一个关于生日悖论的有趣问题。

  1. 生成随机生日。
  2. 创建一个随机生日的人。
  3. 构建一个函数来检查两个人是否有相同的生日。
  4. 创建一个具有给定人数 n 的房间。
  5. 构建一个函数来检查房间中是否至少有两个人的生日相同。

但是,我被困在如何用“人”创建一个“房间”,然后比较这些人的生日。

有谁知道如何做到这一点?

感谢您的努力和时间!:)

0 投票
1 回答
55 浏览

uuid - 我可以安全地采取 uuidv4 的头部来达到我想要的碰撞/空间消耗权衡吗?

我想知道我是否可以通过采用uuidv4的可变头部(即:x第一个字符)来安全地计算使用生日悖论的碰撞机会。

用例:我想要碰撞几率很小的随机 id。但是,每个表的记录数永远不会超过 1.000.000,因此使用 uuidv4 会过多,我想减少一些。这将节省很多,因为我最终将拥有数千张桌子。

天真地,可以按照建议采用 uuidv4 的可变头部来获得固定数量的随机位。然后,使用生日悖论,您可以计算碰撞概率。

例如,用 72 位随机数据​​编码的 1.000.000 个 id 会产生 1.05* 10^-10 的足够小的冲突机会(请参阅 calc)这可以编码为 12 个字符(base64),这将提供足够好的 URL .

当然,问题是 uuidv4 的任意头部是否可以被认为是随机的(足够)。

顺便说一句:基于此HN 帖子的问题

0 投票
2 回答
1335 浏览

java - 使用 HashSet 对生日悖论进行蒙特卡罗分析

免责声明:我不想要这个问题的答案。我只是需要一些指导。

我想使用HashSet.

现在,当我运行它时,collisionCount它比我预期的要低得多。首先,我预计collisionCount一组 10 人的 11446(或 0.11446 的概率)。然后当我达到 100 人时,我预计碰撞计数为 100,000(概率为 1.0)。但是,对于每 10 人,collisionCount 仅按 1 计数(10 人:1 次碰撞,20 人:2 次碰撞,30 人:3 次碰撞,等等)。

这是我到目前为止写的代码:


我想我的问题是:我是否在我的任何一个 for 循环中都没有做正确的事情才能collisionCount正确计数?

我是学习 Java 的新手,也是 Stack Overflow 社区的新手,并且仍在学习中。非常感谢任何帮助/建议/提示。

0 投票
2 回答
192 浏览

search - 生日悖论最快搜索

生日问题或生日悖论预测一组 N 人中一个或多个匹配生日的可能性。几个网站解释了它是如何工作的,以及它背后的数学原理:

  1. https://en.wikipedia.org/wiki/Birthday_problem
  2. https://math.stackexchange.com/questions/25876/probability-of-3-people-in-a-room-of-30-having-the-same-birthday
  3. http://www.wolframalpha.com/input/?i=birthday+problem+calculator&a=FSelect_ **BirthdayProblem-.dflt-&f2=35&f=BirthdayProblem.n_35&f3=365&f=BirthdayProblem.pbds_365

这些网站都非常适合解释这个概念,但都要求已经收集了数据。没有人展示如何有效地调查一大群人。

我打算在一个简短的演示文稿中演示生日悖论。基本上,我需要最快的方法来确定哪些人(如果有的话)在大约 50 人的观众中共享或几乎共享生日。

我能想到的最好的算法:

  1. 让所有人想一想他们的生日,只是月和日(如果他们不愿意分享自己的真实生日,也可以是虚构的生日)
  2. 要求所有人仔细聆听
  3. 要求个人开始向小组宣布他们的生日并听取他们的比赛

在最坏的情况下,所有人都会按顺序宣布他们的生日,而没有任何人匹配。感觉就像我忽略了一些更快地找到答案的捷径,而不是蛮力方法。

我考虑过的替代方案:

• 将观众分成两组?不,这会阻止人们听到其他群体的回应

• 如果没有人中途匹配,请在观众中植入一个人与某人“分享”他们的生日?不,这是作弊

• 传递一年的日历和标记?不,这可能比说话要花更长的时间

• 在线调查?不,人们可能没有电话或 WIFI

解决方案必须是低技术含量的,无需事先准备即可完成,当然还需要诚实。

请让我知道您对快速搜索匹配生日的建议。

谢谢!

0 投票
1 回答
307 浏览

java - java随机字符串生成和生日悖论

我需要编写一个随机字符串生成类,它从 31 个字符的数字字符集和一些字母(10+26-5,省略 5 个元音)生成 7char 字符串。简单的数学给出了一组 31^7 种可能的组合 ~ 275 亿。我对生日悖论有疑问,我进行了一些测试,重复的数量成倍增加。我可以做些什么来避免这种情况吗?

下面是测试类: