Questions tagged [birthday-paradox]
The Birthday Paradox is a phenomenon in probability in which the probability of a population containing two individuals with the same property is much greater than would be intuitively expected. In its original form it describes the likelihood that any two individuals in a room share a birthday. Amongst other things, the Birthday Paradox affects cryptography, hashing and various applications of random number generators.
birthday-paradox
58
questions
81
votes
11
answers
56k
views
Random is barely random at all?
I did this to test the randomness of randint:
>>> from random import randint
>>>
>>> uniques = []
>>> for i in range(4500): # You can see I was optimistic.
... ...
- 56.1k
25
votes
4
answers
26k
views
Examples of Hash-Collisions?
For demonstration-purposes, what are a couple examples of strings that collide when hashed? MD5 is a relatively standard hashing-option, so this will be sufficient.
- 267k
25
votes
1
answer
33k
views
Probability of hash collision
I am looking for some precise math on the likelihood of collisions for MD5, SHA1, and SHA256 based on the birthday paradox.
I am looking for something like a graph that says "If you have 10^8 ...
- 403
18
votes
3
answers
776
views
How was there no collision among 50,000 random 7-digit hex strings? (The Birthday Problem)
I've encountered some code that generates a number of UUIDs via UUID.randomUUID(), takes the last 7 digits of each (recent versions of UUID are uniformly distributed in terms of entropy), and uses ...
- 29.8k
11
votes
5
answers
8k
views
How random is Random.Next()?
I have been doing some testing on the Random class and I have used the following code:
while (x++ <= 5000000)
{
y = rnd.Next(1, 5000000);
if (!data.Contains(y))
data.Add(y);
...
- 10.6k
7
votes
5
answers
2k
views
Uniquely identifying URLs with one 64-bit number
This is basically a math problem, but very programing related: if I have 1 billion strings containing URLs, and I take the first 64 bits of the MD5 hash of each of them, what kind of collision ...
- 29.1k
6
votes
1
answer
404
views
java random string generation and birthday paradox
i need to write a random string generation class which generates 7char strings from a 31-char charset of numbers and some alphabets (10+26-5 , 5 vowels omitted). simple maths gives a set of 31^7 ...
- 1,475
5
votes
1
answer
977
views
Can someone please clarify the Birthday Effect for me?
Please help interpret the Birthday effect as described in Wikipedia:
A birthday attack works as follows:
Pick any message m and compute h(m).
Update list L. Check if h(m) is in the list ...
- 1,214
4
votes
3
answers
948
views
Why am I getting dups with random.shuffle in Python?
For a list of 10 ints, there are 10! possible orders or permutations. Why does random.shuffle give duplicates after only 5000 tries?
>>> L = range(10)
>>> rL = list()
>>> ...
- 7,817
4
votes
2
answers
2k
views
Birthday Paradox List is nonetype
I'm trying to solve the Birthday Paradox with Python. I'm close but the last piece has me at a loss. I'm using random to generate a list of numbers given a range and number of items to create. That ...
- 83
3
votes
3
answers
682
views
Why isn't this Random number generation code working?
I'm writing a program for proving the 'Birthday Paradox'.
For i = 0 To (pnum - 1)
days(i) = rnd(h:=365)
Next
It generates a random number for every i (days(i)) between 1 and 365, the ...
- 29
2
votes
2
answers
1k
views
Random token generation - a supposedly unlikely collision occurred
A couple months ago, we were using UUIDs to generate random string IDs that needed to be unique across the board. I then changed the algorithm in order to save some data and index space in our ...
- 165
2
votes
2
answers
1k
views
Why am I getting this error in my JAVA code?
The birthday paradox says that the probability that two people in a room
will have the same birthday is more than half as long as the number of
people in the room (n), is more than 23. This ...
- 93
2
votes
2
answers
919
views
Generalised Birthday Calculation Given Hash Length
Let us assume that we are given the following:
The length of the hash
The chance of obtaining a collision
Now, knowing the above, how can we obtain the number of "samples" needed to obtain the given ...
- 353
2
votes
3
answers
3k
views
Birthday Paradox: How to programmatically estimate the probability of 3, and N, people sharing a birthday
There are extensive resources on the internet discussing the famous Birthday Paradox. It is clear to me how you calculate the probability of two people sharing a birthday i.e. P(same) = 1 - P(...
user425727
2
votes
4
answers
271
views
How many students can you put into a hash table before a collision occurs?
My professor gave us this slide while explaining Hash Collision probabilities:
When I looked up the probabilities of two people having the same birthday in the "Birthday Paradox", I found on ...
- 41
2
votes
2
answers
2k
views
Doing a Monte Carlo Analysis of the Birthday Paradox using a HashSet
DISCLAIMER : I DO NOT WANT THE ANSWER TO THIS PROBLEM. I SIMPLY NEED SOME GUIDANCE.
I want to perform Monte Carlo analysis on the infamous Birthday Paradox (determining the probability that at least ...
2
votes
1
answer
72
views
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 ...
- 47.8k
1
vote
2
answers
650
views
Birthday Paradox - Function with input variable
I am trying to simulate the probability that more than two students have the same birthday in a room full on n people. Currently I think my code is working properly, although I have to initially just ...
- 181
1
vote
1
answer
170
views
Having trouble with large numbers in Python
running into problems with:
from pylab import *
x=arange(0,365,1)
y = []
for j in x:
y.append(1-((math.factorial(365)/math.factorial(365-j))/(365**j)))
plot(x,y)
show()
Any thoughts? I'm ...
- 85
1
vote
1
answer
63
views
birthday paradox function in R
I'm a beginner in R and am trying to create a birthday paradox function and managed to reach this point, and the result is approximately 0.5, as expected.
k <- 23
sims <- 1000
event <- 0
...
- 13
1
vote
1
answer
233
views
The Birthday Problem - at least 2 out of N [closed]
I received a bit of a modified birthday problem-
I need to run a function that returns the probability that at least two out of N persons share the same birthday. Then a
main function that calculates ...
- 365
1
vote
1
answer
4k
views
How can I find a collision for a toy hash function?
I'd like to find a collision for a simple hash function below (python):
def hash_function(s=''): # 'Hello World!' -> 7b2ea1ba
a, b, c, d = 0xa0, 0xb1, 0x11, 0x4d
result_hash = ''
...
- 3,337
1
vote
4
answers
852
views
C++ Birthday Paradox Using a Boolean Function
I have an assignment where I need to calculate the probability that two people share the same birthday for a given room size (in my case 50) over many trials (5000). I have to assign the birthdays ...
- 11
1
vote
1
answer
848
views
How to tackle the Birthday Paradox Problem in Python?
I'm practicing the Birthday Paradox problem in Python. I've run it a bunch of times, with changing the random number of birthdays and **loop run number **, but the probability is either 0 or 100%, and ...
1
vote
2
answers
1k
views
Java: How to create a room with people having random birthdays?
This is my second day on Java. I came across an interesting question on the Birthday Paradox.
Generate a random birthday.
Create a Person with a random birthday.
Build a function to check if two ...
- 115
1
vote
2
answers
694
views
Calculating the probability of at least 2 duplicates in a world with 400 tiles and 50 objects? Java
First of all I want to let you know that I have been searching for some days now for an answer or something that could perhaps help me out a bit but I couldn't find anything so I am asking here.
I ...
- 49
1
vote
0
answers
38
views
What's wrong with this code that tries to calculate the birthday paradox with ArrayLists?
The odds should be like 10% more to my understanding. However I can't ever get past 7 percent even when doing 7000 tests. I figure it must be the calculation for count of matches, but I cant figure ...
1
vote
1
answer
221
views
Is there a reverse way to find number of people with given 0.5 probability that two people will have same birthday but no using mathematical formula?
I'm doing birthday paradox, and want to know how many people can meet 0.5 probability that two people have same birthday by using python.
I have tried no using mathematical formula to find ...
- 25
1
vote
1
answer
205
views
What is the best way to generate *non-repeating* securely random numbers?
I'm working on something that needs to assign securely random, short (~40 bit) IDs. They need to be unique, which means doing it on a central server.
Just using a new SecureRand each time would run ...
- 7,039
0
votes
2
answers
1k
views
Birthday paradox
I want to simulate the birthday paradox in java. For some reason my output(probability) keeps getting very close to 1 e.g. simulation(10)->0,9268. In start you can see the probabilities my simulations ...
- 3
0
votes
1
answer
95
views
Too frequent Random Byte Collision
I've written a program to simulate collisions in accordance to the typical "Birthday Problem".
However, even taking that into account I'm seeing collisions happen far too frequently in the ...
- 1,748
0
votes
4
answers
3k
views
Birthday paradox python - incorrect probability output
I am having issues with the programming the birthday paradox in Python. The birthday paradox basically says that if there are 23 people in a class, the probability that two of them will have the same ...
- 43
0
votes
3
answers
281
views
Speed up processing 32 bit numbers in combinations (k from n)
I have a list of 128 32 bit numbers, and I want to know, is there any combination of 12 numbers, so that all numbers XORed give the 32 bit number with all bits set to 1.
So I have started with naive ...
- 111
0
votes
1
answer
370
views
How many samples needed for a collision (birthday paradox) [closed]
Just trying to understand birthday paradox.
Using a following code I figured out that I need on average 12 samples to get a birthday collision.
Can not understand why it is much lower than normal 23 ...
- 3
0
votes
1
answer
594
views
Birthday Paradox in Python with monte carlo method?
Trying to find the smallest # of people needed to "enter" a room to have a probability of at least 50% for two people sharing the same birthday, using the monte carlo method (the well known solution ...
- 21
0
votes
1
answer
1k
views
What is the general formula for calculating the probability of generating a duplicate random number?
I am generating random order tracking numbers that should be short, yet should not be duplicate.
For a tracking number consisting of 3 digits, we will generate a duplicate random number after 40 ...
user6269864
0
votes
2
answers
316
views
My birthday paradox event simulator in javascript is not working well
I tried to do a in Javascript a birthday paradox event for 23 students, it should give me an average probability of 51% but it always give me number around 67%. Here the code:
var pers = [];
var D = ...
0
votes
1
answer
2k
views
Find duplicate birthday (Java)
The code is to run simulations to find out the probability of n people sharing the same birthday.
I compared randomly assigned birthdates to an array of dates. For any dates that has more than 1 ...
- 11
0
votes
1
answer
69
views
How to modify the Birthday Problem to answer the probability of 3, 4, 5 or more people in a room having the same birthday
The Birthday Problem asks how many people need to be in a room for there to be greater than a 50% chance that at least two people have the same birthday. I've used the Python code below to solve for ...
- 49
0
votes
0
answers
45
views
Is my approach valid for showing that my algorithm (usage of python's random.sample) is NOT susceptible to the Birthday Problem?
I tried to prove to myself one way or the other whether the way I was generating these "codes" was susceptible to the Birthday Problem, in which case--I tell myself--collisions should ...
- 2,880
0
votes
0
answers
66
views
How to deal with large numbers from specific range?
I have struggled with errors while modifying the below code to select numbers from specific range.
// RANDOM NUMBERS:
struct seed
{
uint256_t seed;
uint128_t counter;
};
/*
* Create a new ...
0
votes
1
answer
90
views
How to Resolve For Loop Error While Running the Birthday Paradox
prob_matches = []
num_people = [2,80]
def birthday_sim(num_people , num_sims = 1000):
possible_birthdays = [i for i in range(0,365)]
for party in range(num_sims):
birthdays = pd....
- 11
0
votes
2
answers
892
views
Monte Carlo simulation of Birthday paradox in python 3
The birthday paradox is that everyone has equal probability of having a birthday on any given of 365 days. We start adding people in a room. What is the probability that 2 people have birthdays on ...
user16116851
0
votes
1
answer
427
views
Generate small UID with uniqueness
I need to generate the UID (alphanumeric) for my use case but that should be a maximum of 7 characters long as we want UID to be random but manageable, like a PNR (CYB6KL) for example.
Now if I am not ...
- 503
0
votes
1
answer
324
views
Java array problem regarding Birthday Paradox - details inside post. I have been unable to figure out what is wrong with my code and need assistance
Problem prompt
Birthday problem. Suppose that people enter a room one at a time. How people must enter until two share a birthday? Counterintuitively, after 23 people enter the room, there is ...
- 1
0
votes
0
answers
192
views
birthday probability program in Fortran 90
I have been given an assignment to create a Fortran 90 program that calculates how many people are needed so that the probability of two or more people having the same birthday becomes 90%.
I would ...
user13559762
0
votes
1
answer
603
views
Hashing Birthday Paradox
So I am working on a piece of code that computes the hashes of 2^4 sets of 3 random prime numbers (less than 2^8). Then keep selecting sets of 3 composite numbers (less than 2^8) until there is a set ...
- 37
0
votes
1
answer
221
views
Can i safely take the head of an uuidv4 to arrive at the collision/space-consumption tradeoff I want?
I'm wondering if I can safely calculate the chances of collision using the birthday-paradox, by taking a variable head (i.e.: the x first characters) of an uuidv4.
usecase: I want random id's with ...
- 18.8k
0
votes
2
answers
2k
views
How to do the Birthday Paradox looping
I have to do the birthday paradox program as an assignment for school. I got the program to run but seem to hav trouble getting the correct answer. I think it's a problem with my loops in the ...
