?

Log in

No account? Create an account

Josh-D. S. Davis

Xaminmo / Omnimax / Max Omni / Mad Scientist / Midnight Shadow / Radiation Master

Previous Entry Share Next Entry
Up and Coming birthdays
Josh 201604 KWP
joshdavis
So how is it that Eiwe and Jenny have the same birthday? I mean, there are 356 days in the year. The chances of 2 people being born on the same day are astronomical. I mean, there aren't THAT many people. What are the chances. Sheesh.


Assuming even distribution, of the present world population, 17418174 were born on any given day. World population will increase by an average of 200,534 each day this month. With an average of 154,585 dying each day, this means some 355k people are born each day this year.

And buying gifts early is the best way to go. I got EB's gift like 3 weeks ago because otherwise, I might have forgotten. She probably knows what it is, but who knows. She also got a spontaneous 10-drawer flat file because she stumbled onto one (OUCH!) for cheap and I decided to buy it when she couldn't really bring herself to bid. :)
Tags:


  • 1
As you are particularly interested in all things nerdy, I
can (fortunately or unfortunately) tell you exactly what size
the room must be in order for the possibilty of 2 people sharing
a birthday to be greater than 50%. The particular equation is know
as the "birthday paradox", and it is used in the cryptanalysis of
hash primitives. Hashing, in general, is a compression function
inputting a arbitrary number of bits and outputting at set number of
bits (128,160,192,256 in most cases). The compression function of
hashing is where its weakness lies. This is where it is possible
to determine x and x' s.t. x<>x' but h(x) = h(x'). Determining
the number of plaintext/hashtext pairs needed to be generated
before an attacker can reasonably find a match is where the
"birthday paradox" comes into play. Because hashing is at the
center of may encryption solutions (MD5 falls in this category),
there is a genuine concern regarding hash output bit-size. The
lower the output bit-size, the more likely it will fall prey to
cryptanalysis. The function to generation size to break a
"collision-resistant" hash function (MD5 again) is 2^(M/2),
where M represents the hash output-length. So, in MD5, being
128-bit out, an attack would need to create hash pairs on the
"order" of 2^64 or 18446744073709551616 pairs before finding
2 or more plaintexts with matching hash with a probability > 50%.

Now the actual birthday question, for those who skipped the
reason I learned all of this crap!


If you have a room containing a random number of people, how
many people are required to raise the probability of two people
having the same birthday above 50%?

This equation is considerably more simple because natural birthdays
are not "collision-resistant". Pr = 1 - 365! / ((365-k)! 365!)
To determine the number where the probability is greater than 50%,
we set Pr=.50 and solve for k. Long and the short, k=23.

So, it is likely (>50%) that in any given room (or friends list)
with 23 or more people, there are two people who share a birthday.

(Deleted comment)
You have it all wrong, don't wish to be
that brainy just marry someone that is.
It's kind of like marrying for money
but not as socially acceptable.

(Deleted comment)
We do not have an assigned text. The professor is convinced
that most texts do not do justice to all of the subjects we
are studying. So instead we have a ton of slides, and I have
chosen:

Cryptography: Theory and Practice -- Stinson
Handbook of Applied Cryptography -- Menezes, Oorschot & Vanstone

It should be said that although I am really enjoying learning the
basis of crypto and the theory and whys, I would be much better off
in a applied cryptography class. Something that demostrated the use
and overall process. Instead, I have gotten very in-depth, and I
have gone beyond what I will practically use. As an example, for my
semester project, I am rewriting the WEP encryption standard in an
effort to reduce some of its weaker attack points. Would I ever
use this kind of information in a corporate sense? Probably not, but
it has been pretty cool to research the creation of RSA, AES, ElGamal,
and Rabin.

Oh, and skip the calculus...it will do you no good.
You need number theory and linear algebra...that will
eliminate some of the "mathy" feel to everything.
Now I wish I would have taken these classes as an undergrad.

Damn, that's small, though we are talking only about 50.00000000000....1% or greater.

Oh, but then, I was also thinking if you were trying to pin it on a specific day. I guess it's easier if it's any day, so long as 2 people share it.

At 357 people, you would be at 100% (could be a leap-year), I think. Let's try.

1 = 1 - 365! / ((365 - k)! * 365!)

Order of operations makes this:

1 = 1 - (365! / ((365 - k)! * 365!)

Then we add to both sides: (365! / ((365 - k)! * 365!)

1 + (365! / ((365 - k)! * 365!) = 1

Then we subtract 1 from both sides:

365! / ((365 - k)! * 365! = 0

Then we multiply by: ((365 - k)! * 365!

365! = 0

Then universe crashes

ok, ok, -1 on both sides is a bad idea, so we'll continue from here:

1 + (365! / ((365 - k)! * 365!) = 1

((365 - k)! * 365!) + 365! = ((365 - k)! * 365!)

(365 - k)! + 1 = (365 - k)!

ok, wtf. Can I not do math anymore?

Assuming that it was supposed to be this:
             1 - 365!
1 =  --------------------
        (365 - k)! * 365!


Multiply both sides by: (365 - k)! * 365!

(365 - k)! * 365! = 1 - 365!

Divide both sides by: 365!

(365 -k)! = 1/(365!) - 1

Since 1 = 1!, we reduce to this:

365 -k = (1/365) - 1

The we add K to both sides:

365 = k + 364/365

Then subtract the fraction from both sides:

364 + 364/365 = k

So technically, we need 364.99726 people for 100%

I probably did this wrong, even though I know the equation doesn't KNOW there might be legal implications of removing 0.27% of someone.

See, Brad has to do this stuff for school...
but what's your excuse ;)

(Deleted comment)

Re: speaking math...

Maybe it's just because they're so excited?

Re: speaking math...

It's not called a "bang" for nothing.

'!' is the notation for factorial (i.e. 5! = 5*4*3*2*1)
But now Josh is making me break out the real math to answer
his questions. I don't even know if I am going to able to
post without using LaTEX.

Re: speaking math...

LaTEX = the stuff gloves are made out of.

Re: speaking math...

We have a few jars of liquid latex.
It's best use is to keep floor mats from slipping unless you are supremely patient.

Re: speaking math...

NnnnOOOOO! No TEX. I can't use TEX or DVIprint.

Re: speaking math...

! = factorial
1! = 1*1
365! = 365 * 364 * 363 * 362 ......

Re: speaking math...

I was born strangled. :)
Or maybe I wanted to see if I could still do it.

Try this on for size...hopefully I didn't typo anything else

Okay...now you've done it. Now I need to break out the equations.
I just filled in the equation to make it easier to explain here is
the actual math behind it.

Since we are measuring a probabiltiy, it will never be higher than 1.
This can be expressed: P(365,k) = 1 - ((356!)/((365-k)! * 365^k))
where k<365. Sorry for the typo! We can set the probability P(365,k)
to be 50% which results in a number of people (k) of approx 22.3 in a
non-leap year.

The general solution to the problem is a little bit more complex.
Generally we are trying to solve the number of instances k required,
given a random variable with a uniform distribution between 1 and n,
where k < n and the probability of finding duplicate instances P(n,k)
>= 50%.

P(n,k) = 1 - (n! / ((n-k)! * n^k)) =
1 - [(1-(1/n))*(1-(2/n))*...(1-(k-1/n))] =


Then, suddenly, we start throwing in estimations and approximations!

1-x ~ e^-x, and we start substituting this into our equation such that:

P(n,k) ~ 1- e^((k*(k-1))/2n)

To solve P(n,k) >= 50% -> 1/2 = 1- e^((k*(k-1))/2n)
For large numbers: k(k-1) ~ k^2 -> ln(1-e) ~ (k^2/2n)

k^2 ~ 2n*ln(1-e)
k ~ √(2n * ln(1-e)) -> The natural log portion is negligible.
k ~ 1.18 * √n

So, for our little birthday problem:
k ~ 1.18 * √365 -> k~22.4

(Deleted comment)

Re: Try this on for size...hopefully I didn't typo anything else

Everything appears natural when you don't see it being made.

Re: Try this on for size...hopefully I didn't typo anything else

No
I don't like it.
Put my brain back.

No linear algebra in here, no ~= use, etc.

I like my way better. :)

This thread made my day :)
I love geeks and pride myself highly to count among them!

As a young kid I dated a very cool girl for several years that had the same birthday as me.
Now I'm good friends with another cool girl who has the same birthday as me.

Does that me me doubly cool? I think so.

Happy Birthday Jenny! :)

Double-Mint Gum!

I had a friend in school with my birthday and year, Amy Brooks.

I had a girlfriend in 95 with my birthday, Caroline Lorraine James.

Since then, I haven't really met other Oct 6 people.

March is a good month. Erica is March 28.

Have a good evening tonight.

What are you two doing Tue/Wed? Let's plan something.

My birthday is October 15, 1975. However, I applaud you for even remembering the approximate date range.

*NOTE TO SELF* Try not to google your whole name, because you never know what you are going to get.

Haha... Wow, for some reason I thought you were the same bday.

So, yah, how has life treated you over the last 9-10 years?

Hopefully full of more stable people than, oh, 19/20 year old Librans. :)

Happy soon-to-be-29. :)

  • 1