Valhalla Legends Archive

Quote from: Grok on April 13, 2004, 05:56 AM

Quote from: K on April 13, 2004, 12:07 AM

Quote from: KoRRuPT on April 13, 2004, 12:01 AM
I find it creepy because its a one in a billion chance, and it basically happened twice to me. Thing has the same birthday as me, and iago lives five minutes away.

1/365 != 1/1000000000.

With 26 randomly-selected people, there is a 50% chance that a non-specific two will have the same birthday.

I think the odds are actually much higher than that, if I recall correctly.  With a group of 30 people it was nearly 100% (>95% anyway).

Aha, I found a program I threw together in Philosophy last year to test out what our prof told us:

public class Birthday
{
   public static final int PEOPLE = 50;
   public static final int DAYS = 365;
   public static final int TESTSIZE = 100000;
   
   public static boolean []birthdays;

   public static boolean BDay()
   {
       birthdays = new boolean[DAYS];
       
       for(int i = 0; i < PEOPLE; i++)
       {
           int ThisBDay = (int)(Math.random() * 365.0);

           if(birthdays[ThisBDay] == true)
               return true;
           birthdays[ThisBDay] = true;
       }
   
       return false;
   }

   public static void main(String args[])
   {
       int Num = 0;

       for(int i = 0; i < TESTSIZE; i++)
       {
           if(BDay())
                   Num++;
       }

       System.out.println("In " + TESTSIZE + " groups of " + PEOPLE + " people, " + Num + " groups had at least one shared birthday.");
       System.out.println(Num/((double)TESTSIZE / 100.0) + "%");
   }  
}


In 1000000 groups of 25 people, 569786 groups had at least one shared birthday.
56.9786%

In 100000 groups of 30 people, 70726 groups had at least one shared birthday.
70.726%

In 100000 groups of 40 people, 89194 groups had at least one shared birthday.
89.194%

In 100000 groups of 50 people, 97040 groups had at least one shared birthday.
97.04%

In 100000 groups of 60 people, 99434 groups had at least one shared birthday.
99.434%

In 100000 groups of 70 people, 99920 groups had at least one shared birthday.
99.92%

This forum has 972 accounts so.. well, there's guarenteed to be at least 2 pairs no matter how you look at it, so I won't bother trying



<edit> Just for fun, I made it iterative:

QuoteIn 100000 groups of 0 people, 0 groups had at least one shared birthday.
0.0%
In 100000 groups of 5 people, 2726 groups had at least one shared birthday.
2.726%
In 100000 groups of 10 people, 11647 groups had at least one shared birthday.
11.647%
In 100000 groups of 15 people, 25174 groups had at least one shared birthday.
25.174%
In 100000 groups of 20 people, 41299 groups had at least one shared birthday.
41.299%
In 100000 groups of 25 people, 56907 groups had at least one shared birthday.
56.907%
In 100000 groups of 30 people, 70553 groups had at least one shared birthday.
70.553%
In 100000 groups of 35 people, 81299 groups had at least one shared birthday.
81.299%
In 100000 groups of 40 people, 89148 groups had at least one shared birthday.
89.148%
In 100000 groups of 45 people, 94272 groups had at least one shared birthday.
94.272%
In 100000 groups of 50 people, 97008 groups had at least one shared birthday.
97.008%
In 100000 groups of 55 people, 98612 groups had at least one shared birthday.
98.612%
In 100000 groups of 60 people, 99425 groups had at least one shared birthday.
99.425%
In 100000 groups of 65 people, 99739 groups had at least one shared birthday.
99.739%
In 100000 groups of 70 people, 99920 groups had at least one shared birthday.
99.92%
In 100000 groups of 75 people, 99972 groups had at least one shared birthday.
99.972%
In 100000 groups of 80 people, 99991 groups had at least one shared birthday.
99.991%
In 100000 groups of 85 people, 99996 groups had at least one shared birthday.
99.996%
In 100000 groups of 90 people, 100000 groups had at least one shared birthday.
100.0%
In 100000 groups of 95 people, 99998 groups had at least one shared birthday.
99.998%
In 100000 groups of 100 people, 100000 groups had at least one shared birthday.
100.0%
In 100000 groups of 105 people, 100000 groups had at least one shared birthday.
100.0%
In 100000 groups of 110 people, 100000 groups had at least one shared birthday.
100.0%
In 100000 groups of 115 people, 100000 groups had at least one shared birthday.
100.0%
 In 100000 groups of 70 people, 99920 groups had at least one shared birthday.
99.92%
In 100000 groups of 120 people, 100000 groups had at least one shared birthday.
100.0%
In 100000 groups of 125 people, 100000 groups had at least one shared birthday.
100.0%

Quote from: iago on April 13, 2004, 08:16 AM

Quote from: Grok on April 13, 2004, 05:56 AM

Quote from: K on April 13, 2004, 12:07 AM

Quote from: KoRRuPT on April 13, 2004, 12:01 AM
I find it creepy because its a one in a billion chance, and it basically happened twice to me. Thing has the same birthday as me, and iago lives five minutes away.

1/365 != 1/1000000000.

With 26 randomly-selected people, there is a 50% chance that a non-specific two will have the same birthday.

I think the odds are actually much higher than that, if I recall correctly.  With a group of 30 people it was nearly 100% (>95% anyway).

30 is way more than 26.  You don't need a program to figure this out.  Math works fine.  Ah, the actual number was 23, my bad.

PROOF:  http://www.itsecurity.com/dictionary/bday.htm

My philosophy teacher did the proof for us.  But I like programs better.  They'll generally work out to the same thing, which mine did at one time, for sure.  I might have broken it when I converted from windows C++ to Java.

<edit> actually, it WAS right.  25 =~ 57% and 20 =~ 42%, so 23 would be ~50% if I had outputed it

14 May 24th.

I actually spent a lot of time reading www.wikipedia.com and mathworld.wolfram.com and a few other things about the Birthday Paradox and Birthday Attack.  I enjoyed the part about how it can be used to defeat message digests and such.

Quote from: iago on April 13, 2004, 05:49 PM
I actually spent a lot of time reading www.wikipedia.com and mathworld.wolfram.com and a few other things about the Birthday Paradox and Birthday Attack.  I enjoyed the part about how it can be used to defeat message digests and such.

Well, I'm not so sure their reasoning was the correct explanation of the birthday paradox.  There's a huge difference between the chances of finding someone among 23 who has MY birthday, and the chances of finding two people among 23 who have the same birthday.  Specifically, the chances are 23 times better in the latter case.

Quote from: Grok on April 13, 2004, 06:50 PM

Quote from: iago on April 13, 2004, 05:49 PM
I actually spent a lot of time reading www.wikipedia.com and mathworld.wolfram.com and a few other things about the Birthday Paradox and Birthday Attack.  I enjoyed the part about how it can be used to defeat message digests and such.

Well, I'm not so sure their reasoning was the correct explanation of the birthday paradox.  There's a huge difference between the chances of finding someone among 23 who has MY birthday, and the chances of finding two people among 23 who have the same birthday.  Specifically, the chances are 23 times better in the latter case.

Yes, at least one of the sources I read made that distinction.  Part of the description was taking a text document that you want somebody to digitally sign, making changes to the meaning then making small changes (commas, spaces, tabs, etc) in both till you find one that match.  You quickly get a large pool where a match between real1, real2, real3...realn and fake1, fake2, .... faken gets likely pretty fast.

Quote from: iago on April 13, 2004, 07:17 PM
Yes, at least one of the sources I read made that distinction.  Part of the description was taking a text document that you want somebody to digitally sign, making changes to the meaning then making small changes (commas, spaces, tabs, etc) in both till you find one that match.  You quickly get a large pool where a match between real1, real2, real3...realn and fake1, fake2, .... faken gets likely pretty fast.

I wouldn't say "pretty fast"... What you're doing is reduce the complexity by a square root. For a 128 bit hash, the complexity is about the same as a 64 bit symmetric cipher. Also, to use a birthday attack, you need to be able to store all those values that you've calculated. To attack a 128 bit hash, you need to have at least 134217728 TB storage easily and quickly accessible.

Quote from: Adron on April 14, 2004, 10:49 AM

Quote from: iago on April 13, 2004, 07:17 PM
Yes, at least one of the sources I read made that distinction.  Part of the description was taking a text document that you want somebody to digitally sign, making changes to the meaning then making small changes (commas, spaces, tabs, etc) in both till you find one that match.  You quickly get a large pool where a match between real1, real2, real3...realn and fake1, fake2, .... faken gets likely pretty fast.

I wouldn't say "pretty fast"... What you're doing is reduce the complexity by a square root. For a 128 bit hash, the complexity is about the same as a 64 bit symmetric cipher. Also, to use a birthday attack, you need to be able to store all those values that you've calculated. To attack a 128 bit hash, you need to have at least 134217728 TB storage easily and quickly accessible.

hmm..

*researches prices*

Ok, I'm going to stick with breaking 8-bit hashes.

aww this is my bad, I accidentally voted No for under 25. Damn you mother fuckers and your abnormal wording!

I'm almost 97 years old believe it or not.

Quote from: jigsaw on April 18, 2004, 05:31 AM
I'm almost 97 years old believe it or not.

I love you just the way you are.

Quote from: Hostile on April 17, 2004, 09:15 PM
aww this is my bad, I accidentally voted No for under 25. Damn you mother fuckers and your abnormal wording!

What's so hard about "are you under 25"?

Quote from: iago on April 18, 2004, 11:36 AM

Quote from: Hostile on April 17, 2004, 09:15 PM
aww this is my bad, I accidentally voted No for under 25. Damn you mother fuckers and your abnormal wording!

What's so hard about "are you under 25"?

Damn lawyer-speak!