(*********************************************************************** Mathematica-Compatible Notebook This notebook can be used on any computer system with Mathematica 3.0, MathReader 3.0, or any compatible application. The data for the notebook starts with the line of stars above. To get the notebook into a Mathematica-compatible application, do one of the following: * Save the data starting with the line of stars above into a file with a name ending in .nb, then open the file inside the application; * Copy the data starting with the line of stars above to the clipboard, then use the Paste menu command inside the application. Data for notebooks contains only printable 7-bit ASCII and can be sent directly in email or through ftp in text mode. Newlines can be CR, LF or CRLF (Unix, Macintosh or MS-DOS style). NOTE: If you modify the data for this notebook not in a Mathematica- compatible application, you must delete the line below containing the word CacheID, otherwise Mathematica-compatible applications may try to use invalid cache data. For more information on notebooks and Mathematica-compatible applications, contact Wolfram Research: web: http://www.wolfram.com email: info@wolfram.com phone: +1-217-398-0700 (U.S.) Notebook reader applications are available free of charge from Wolfram Research. ***********************************************************************) (*CacheID: 232*) (*NotebookFileLineBreakTest NotebookFileLineBreakTest*) (*NotebookOptionsPosition[ 30407, 888]*) (*NotebookOutlinePosition[ 31094, 912]*) (* CellTagsIndexPosition[ 31050, 908]*) (*WindowFrame->Normal*) Notebook[{ Cell[CellGroupData[{ Cell[TextData[{ "The Birthday Paradox and Microsoft GUIDs or How I use ", StyleBox["Mathematica", FontSlant->"Italic"], " to Reassure Myself to Go Back to Sleep at Nights." }], "Title"], Cell["The Birthday Paradox", "Subtitle"], Cell["\<\ \tQuick, how many people must be in the same room so that the chance of at \ least two of them having the same birthday is 50%? 300 people?, 180 people? \ 100 people? The answer might surprise you. It sure did surprise me the \ first time I heard it.\ \>", "Text"], Cell[TextData[{ "\tIf you have two people in the same room, the chance that they will have \ the same birthday is ", Cell[BoxData[ \(TraditionalForm\`1\/365\)]], "or approximately 0.003, assuming there is no such things as leap years. \ If you have three people in the same room, what is the chance that at least \ two of them have the same birthday? To find that, we notice that the chance \ that at least two of them having the same birthday plus the chance that all \ of them having distinct birthdays is one--P(at least two person have the same \ birthday) = 1 - P(all of them have distinct birthdays). Now the chance that \ all of them have distinct birthdays is ", Cell[BoxData[ \(TraditionalForm\`364\/365\)]], ".", Cell[BoxData[ \(TraditionalForm\`363\/365\)]], ", therefore, the chance that at least two person have the same birthday is \ 1-", Cell[BoxData[ \(TraditionalForm\`364\/365\)]], ".", Cell[BoxData[ \(TraditionalForm\`363\/365\)]], " or approximately 0.008.\n\n\tNow, if you have 365 people in the same \ room, you can be certain that at least two of them will have the same \ birthday (again assuming there is no leap year.) An interesting question is, \ to have a 50% chance that at least two people have the same birthday, how \ many people must be in the same room? The answer surprised so many people \ that it is called ", StyleBox["the", FontSlant->"Italic"], " ", StyleBox["Birthday Paradox", FontSlant->"Italic"], ".\n\n\tFirst, we write down a formula for the chance that at least two \ people, out of k people, will have the same birthday. Let's call that p[k]. \ We know that p[1]=1-", Cell[BoxData[ \(TraditionalForm\`365\/365\)]], "=0, p[2]=1-", Cell[BoxData[ \(TraditionalForm\`365\/365\)]], Cell[BoxData[ \(TraditionalForm\`364\/365\)]], ", p[3]=1-", Cell[BoxData[ \(TraditionalForm\`365\/365\)]], Cell[BoxData[ \(TraditionalForm\`364\/365\)]], Cell[BoxData[ \(TraditionalForm\`363\/365\)]], ", p[4] = 1-", Cell[BoxData[ \(TraditionalForm\`365\/365\)]], Cell[BoxData[ \(TraditionalForm\`364\/365\)]], Cell[BoxData[ \(TraditionalForm\`363\/365\)]], Cell[BoxData[ \(TraditionalForm\`362\/365\)]], ", in general: p[k] is:" }], "Text"], Cell[BoxData[ \(p[k_]\ := \ 1 - \(\((365 - 1)\)!\)/\((\(\((365 - k - 1)\)!\) 365^k)\)\)], "Input"], Cell["Here are some numerical values for p[k]:", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(TableForm[Table[{k, N[p[k], 3]}, {k, 1, 25}], \ TableHeadings\ -> \ {None, {"\", "\"}}]\)], "Input"], Cell[BoxData[ TagBox[GridBox[{ {\("k"\), \("p[k] to three decimal places"\)}, {"1", StyleBox["0.00273972602739726012`", StyleBoxAutoDelete->True, PrintPrecision->3]}, {"2", StyleBox["0.00820416588478138564`", StyleBoxAutoDelete->True, PrintPrecision->3]}, {"3", StyleBox["0.0163559124665503041`", StyleBoxAutoDelete->True, PrintPrecision->3]}, {"4", StyleBox["0.0271355736997935848`", StyleBoxAutoDelete->True, PrintPrecision->3]}, {"5", StyleBox["0.0404624836491114869`", StyleBoxAutoDelete->True, PrintPrecision->3]}, {"6", StyleBox["0.0562357030959754133`", StyleBoxAutoDelete->True, PrintPrecision->3]}, {"7", StyleBox["0.0743352923516690289`", StyleBoxAutoDelete->True, PrintPrecision->3]}, {"8", StyleBox["0.0946238338891667218`", StyleBoxAutoDelete->True, PrintPrecision->3]}, {"9", StyleBox["0.116948177711077638`", StyleBoxAutoDelete->True, PrintPrecision->3]}, {"10", StyleBox["0.141141378321733057`", StyleBoxAutoDelete->True, PrintPrecision->3]}, {"11", StyleBox["0.167024788838064397`", StyleBoxAutoDelete->True, PrintPrecision->3]}, {"12", StyleBox["0.194410275232429405`", StyleBoxAutoDelete->True, PrintPrecision->3]}, {"13", StyleBox["0.223102512004972997`", StyleBoxAutoDelete->True, PrintPrecision->3]}, {"14", StyleBox["0.252901319763686327`", StyleBoxAutoDelete->True, PrintPrecision->3]}, {"15", StyleBox["0.283604005252849944`", StyleBoxAutoDelete->True, PrintPrecision->3]}, {"16", StyleBox["0.315007665296560634`", StyleBoxAutoDelete->True, PrintPrecision->3]}, {"17", StyleBox["0.346911417871789362`", StyleBoxAutoDelete->True, PrintPrecision->3]}, {"18", StyleBox["0.379118526031536662`", StyleBoxAutoDelete->True, PrintPrecision->3]}, {"19", StyleBox["0.411438383580580069`", StyleBoxAutoDelete->True, PrintPrecision->3]}, {"20", StyleBox["0.44368833516520576`", StyleBoxAutoDelete->True, PrintPrecision->3]}, {"21", StyleBox["0.475695307662549993`", StyleBoxAutoDelete->True, PrintPrecision->3]}, {"22", StyleBox["0.507297234323985346`", StyleBoxAutoDelete->True, PrintPrecision->3]}, {"23", StyleBox["0.538344257914528867`", StyleBoxAutoDelete->True, PrintPrecision->3]}, {"24", StyleBox["0.568699703969464032`", StyleBoxAutoDelete->True, PrintPrecision->3]}, {"25", StyleBox["0.598240820135938911`", StyleBoxAutoDelete->True, PrintPrecision->3]} }, RowSpacings->1, ColumnSpacings->3, RowAlignments->Baseline, ColumnAlignments->{Left}], (TableForm[ #, TableHeadings -> {None, {"k", "p[k] to three decimal places"}}]&)]], "Output"] }, Open ]], Cell["\<\ \tNote that when we have 22 people, the chance is 50.7% that at least two of \ them will have the same birthday! Most people would guess that there must be \ a lot more than 22 people to have a 50% chance. That's why this is called \ the Birtday Paradox. Below is a plot of p[k] for k from 1 to 100.\ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(Plot[p[k], {k, 1, 100}]\)], "Input"], Cell[GraphicsData["PostScript", "\<\ %! %%Creator: Mathematica %%AspectRatio: .61803 MathPictureStart /Mabs { Mgmatrix idtransform Mtmatrix dtransform } bind def /Mabsadd { Mabs 3 -1 roll add 3 1 roll add exch } bind def %% Graphics /Courier findfont 10 scalefont setfont % Scaling calculations 0.0238095 0.00952381 0.0147151 0.588604 [ [.21429 .00222 -6 -9 ] [.21429 .00222 6 0 ] [.40476 .00222 -6 -9 ] [.40476 .00222 6 0 ] [.59524 .00222 -6 -9 ] [.59524 .00222 6 0 ] [.78571 .00222 -6 -9 ] [.78571 .00222 6 0 ] [.97619 .00222 -9 -9 ] [.97619 .00222 9 0 ] [.01131 .13244 -18 -4.5 ] [.01131 .13244 0 4.5 ] [.01131 .25016 -18 -4.5 ] [.01131 .25016 0 4.5 ] [.01131 .36788 -18 -4.5 ] [.01131 .36788 0 4.5 ] [.01131 .4856 -18 -4.5 ] [.01131 .4856 0 4.5 ] [.01131 .60332 -6 -4.5 ] [.01131 .60332 0 4.5 ] [ 0 0 0 0 ] [ 1 .61803 0 0 ] ] MathScale % Start of Graphics 1 setlinecap 1 setlinejoin newpath 0 g .25 Mabswid .21429 .01472 m .21429 .02097 L s [(20)] .21429 .00222 0 1 Mshowa .40476 .01472 m .40476 .02097 L s [(40)] .40476 .00222 0 1 Mshowa .59524 .01472 m .59524 .02097 L s [(60)] .59524 .00222 0 1 Mshowa .78571 .01472 m .78571 .02097 L s [(80)] .78571 .00222 0 1 Mshowa .97619 .01472 m .97619 .02097 L s [(100)] .97619 .00222 0 1 Mshowa .125 Mabswid .07143 .01472 m .07143 .01847 L s .11905 .01472 m .11905 .01847 L s .16667 .01472 m .16667 .01847 L s .2619 .01472 m .2619 .01847 L s .30952 .01472 m .30952 .01847 L s .35714 .01472 m .35714 .01847 L s .45238 .01472 m .45238 .01847 L s .5 .01472 m .5 .01847 L s .54762 .01472 m .54762 .01847 L s .64286 .01472 m .64286 .01847 L s .69048 .01472 m .69048 .01847 L s .7381 .01472 m .7381 .01847 L s .83333 .01472 m .83333 .01847 L s .88095 .01472 m .88095 .01847 L s .92857 .01472 m .92857 .01847 L s .25 Mabswid 0 .01472 m 1 .01472 L s .02381 .13244 m .03006 .13244 L s [(0.2)] .01131 .13244 1 0 Mshowa .02381 .25016 m .03006 .25016 L s [(0.4)] .01131 .25016 1 0 Mshowa .02381 .36788 m .03006 .36788 L s [(0.6)] .01131 .36788 1 0 Mshowa .02381 .4856 m .03006 .4856 L s [(0.8)] .01131 .4856 1 0 Mshowa .02381 .60332 m .03006 .60332 L s [(1)] .01131 .60332 1 0 Mshowa .125 Mabswid .02381 .04415 m .02756 .04415 L s .02381 .07358 m .02756 .07358 L s .02381 .10301 m .02756 .10301 L s .02381 .16187 m .02756 .16187 L s .02381 .1913 m .02756 .1913 L s .02381 .22073 m .02756 .22073 L s .02381 .27959 m .02756 .27959 L s .02381 .30902 m .02756 .30902 L s .02381 .33845 m .02756 .33845 L s .02381 .39731 m .02756 .39731 L s .02381 .42674 m .02756 .42674 L s .02381 .45617 m .02756 .45617 L s .02381 .51503 m .02756 .51503 L s .02381 .54446 m .02756 .54446 L s .02381 .57389 m .02756 .57389 L s .25 Mabswid .02381 0 m .02381 .61803 L s 0 0 m 1 0 L 1 .61803 L 0 .61803 L closepath clip newpath .5 Mabswid .03333 .01633 m .03793 .01768 L .04222 .01928 L .05195 .02409 L .06144 .03034 L .07158 .03867 L .09342 .06203 L .1133 .08907 L .15283 .15555 L .19086 .22913 L .23131 .30939 L .27027 .38167 L .30773 .44204 L .34761 .49406 L .386 .53188 L .40551 .54684 L .42681 .56026 L .44743 .57069 L .46612 .57827 L .4856 .58454 L .50636 .5897 L .52541 .59332 L .54603 .59626 L .56576 .59833 L .58662 .59992 L .60606 .60097 L .62421 .60168 L .63456 .60199 L .64436 .60223 L .66273 .60258 L .67229 .60272 L .68244 .60284 L .70068 .603 L .70995 .60306 L .71995 .60312 L .73805 .60319 L .74753 .60322 L .75789 .60324 L .76871 .60326 L .77878 .60327 L .7892 .60328 L .79903 .60329 L .80779 .6033 L .81743 .6033 L .82706 .60331 L .83725 .60331 L .84668 .60331 L .85551 .60331 L .86582 .60331 L .8756 .60332 L Mistroke .88438 .60332 L .89395 .60332 L .90419 .60332 L .91347 .60332 L .92417 .60332 L .93424 .60332 L .94393 .60332 L .95416 .60332 L .96289 .60332 L .97246 .60332 L .97619 .60332 L Mfstroke % End of Graphics MathPictureEnd \ \>"], "Graphics", ImageSize->{288, 177.938}, ImageMargins->{{45, 0}, {0, 1}}, ImageRegion->{{0, 1}, {0, 1}}, ImageCache->GraphicsData["Bitmap", "\<\ CF5dJ6E]HGAYHf4PAg9QL6QYHgOol00`00Oomoo`3gOol001Eoo`03001oogoo00mo o`03001oogoo0?Ioo`005Goo00<007ooOol047oo00<007ooOol0mGoo000EOol00`00Oomoo`0AOol0 0`00Oomoo`3dOol001Eoo`03001oogoo015oo`03001oogoo0?Aoo`005Goo00<007ooOol04Woo00<0 07ooOol0lgoo000EOol2000DOol00`00Oomoo`3bOol001Eoo`03001oogoo01=oo`03001oogoo0?9o o`005Goo00<007ooOol057oo00<007ooOol0lGoo000EOol00`00Oomoo`0DOol00`00Oomoo`3aOol0 01Eoo`03001oogoo01Eoo`03001oogoo0?1oo`005Goo00<007ooOol05Woo00<007ooOol0kgoo000E Ool00`00Oomoo`0FOol00`00Oomoo`3_Ool001Eoo`8001Qoo`03001oogoo0>ioo`005Goo00<007oo Ool05goo00<007ooOol0kWoo000EOol00`00Oomoo`0HOol00`00Oomoo`3]Ool001Eoo`03001oogoo 01Uoo`03001oogoo0>aoo`005Goo00<007ooOol06Goo00<007ooOol0k7oo0006Ool00`00Oomoo`03 Ool50004Ool00`00Oomoo`0JOol00`00Oomoo`3[Ool00003001oogoo00Uoo`03001oogoo00Ioo`03 001oogoo01]oo`03001oogoo0>Yoo`0000<007ooOol02Woo00<007ooOol01Goo00<007ooOol06goo 00<007ooOol0jWoo00000`00Oomoo`0;Ool00`00Oomoo`04Ool3000LOol00`00Oomoo`3YOol00003 001oogoo00aoo`03001oogoo00=oo`03001oogoo01aoo`03001oogoo0>Uoo`0000<007ooOol03Goo 00<007ooOol00Woo00<007ooOol07Goo00<007ooOol0j7oo00000`00Oomoo`0=Ool00`00Oomoo`02 Ool00`00Oomoo`0NOol00`00Oomoo`3WOol00003001oogoo00Uoo`05001oogooOol00004Ool00`00 Oomoo`0NOol00`00Oomoo`3WOol000eoo`<000Eoo`03001oogoo01moo`03001oogoo0>Ioo`005Goo 00<007ooOol07goo00<007ooOol0iWoo000EOol00`00Oomoo`0POol00`00Oomoo`3UOol001Eoo`80 029oo`03001oogoo0>Aoo`005Goo00<007ooOol08Goo00<007ooOol0i7oo000EOol00`00Oomoo`0R Ool00`00Oomoo`3SOol001Eoo`03001oogoo029oo`03001oogoo0>=oo`005Goo00<007ooOol08goo 00<007ooOol0hWoo000EOol00`00Oomoo`0SOol00`00Oomoo`3ROol001Eoo`03001oogoo02Aoo`03 001oogoo0>5oo`005Goo00<007ooOol097oo00<007ooOol0hGoo000EOol2000VOol00`00Oomoo`3P Ool001Eoo`03001oogoo02Eoo`03001oogoo0>1oo`005Goo00<007ooOol09Woo00<007ooOol0ggoo 000EOol00`00Oomoo`0VOol00`00Oomoo`3OOol001Eoo`03001oogoo02Moo`03001oogoo0=ioo`00 5Goo00<007ooOol09goo00<007ooOol0gWoo000EOol00`00Oomoo`0XOol00`00Oomoo`3MOol001Eo o`03001oogoo02Qoo`03001oogoo0=eoo`005Goo0P00:Woo00<007ooOol0g7oo000EOol00`00Oomo o`0YOol00`00Oomoo`3LOol001Eoo`03001oogoo02Yoo`03001oogoo0=]oo`005Goo00<007ooOol0 :goo00<007ooOol0fWoo000EOol00`00Oomoo`0[Ool00`00Oomoo`3JOol000Ioo`03001oogoo00Eo o`<000Aoo`03001oogoo02aoo`03001oogoo0=Uoo`0000<007ooOol037oo00<007ooOol00goo00<0 07ooOol0;7oo00<007ooOol0fGoo00000`00Oomoo`09Ool50004Ool00`00Oomoo`0]Ool00`00Oomo o`3HOol00003001oogoo00Uoo`04001oogoo0005Ool3000]Ool00`00Oomoo`3HOol00003001oogoo 00Yoo`03001oo`0000Eoo`03001oogoo02ioo`03001oogoo0=Moo`0000<007ooOol02Woo00<007oo 00001Goo00<007ooOol0;Woo00<007ooOol0egoo00000`00Oomoo`0;Ool20005Ool00`00Oomoo`0_ Ool00`00Oomoo`3FOol00003001oogoo00]oo`8000Eoo`03001oogoo02moo`03001oogoo0=Ioo`00 3goo00<007ooOol00goo00<007ooOol0<7oo00<007ooOol0eGoo000EOol00`00Oomoo`0`Ool00`00 Oomoo`3EOol001Eoo`03001oogoo035oo`03001oogoo0=Aoo`005Goo0P00Goo00<0 07ooOol0c7oo000EOol2000jOol00`00Oomoo`3Woo00<007ooOol0bgoo000EOol00`00Oomoo`0kOol00`00Oomoo`3:Ool0 00Ioo`03001oogoo00Aoo`<000Eoo`03001oogoo03]oo`03001oogoo0Ool20005Ool00`00Oomoo`0oOol0 0`00Oomoo`36Ool001Eoo`03001oogoo041oo`03001oogoo0Ool00`00Oomoo`04Ool00`00Oomo o`22Ool;001kOol000ioo`03001oogoo00Aoo`03001oogoo08eoo`/0071oo`003Woo00<007ooOol0 17oo0`00V7ooI`002Goo000>Ool00`00Oomoo`04Ool00`00Oomoo`3oOol9Ool000ioo`03001oogoo 00Aoo`03001oogoo0?moo`Uoo`003Woo00<007ooOol017oo00<007ooOol0ogoo2Goo000"], ImageRangeCache->{{{0, 287}, {176.938, 0}} -> {-8.32696, -0.0825899, 0.389667, 0.00630494}}], Cell[BoxData[ TagBox[\(\[SkeletonIndicator] Graphics \[SkeletonIndicator]\), False, Editable->False]], "Output"] }, Open ]], Cell[CellGroupData[{ Cell["Microsoft GUIDs", "Subtitle"], Cell[TextData[{ "\tHow is the Birthday Paradox having anything to do with Microsoft GUIDs? \ For that matter, what is a GUID?\n\n\tGUID stands for Globally Unique \ Identifier. It is a 128-bit number which means that if we write it down \ using base 2, we will need 128 digits of either one or zero to represent it. \ If we write it down in our usual base 10, we will need about 38 digits (", Cell[BoxData[ \(TraditionalForm\`2\^128\)]], "~ 3.4 x ", Cell[BoxData[ \(TraditionalForm\`10\^38\)]], ".) \n\t\n\tUnder Microsoft Windows, it's more and more likely that most \ of the programs, package routines, and other programming components will be \ labeled with GUIDs. To make everything works, each GUID must be truely \ unique. Microsoft Windows relies on the fact that every distinct object has \ its own distinct GUID label. If a GUID is repeated, unpredictable behaviors \ will occur. Definitely a bad thing. So, the question is, how can we be sure \ that the GUIDs never repeat?\n\n\tThe answer to that question is that we can \ never be sure. The only thing that prevents GUIDs from repeating is the fact \ that the number of values that GUIDs can be is enormous. There can be the \ total of \t", Cell[BoxData[ \(TraditionalForm\`2\^128\)]], " (or 3.4 x ", Cell[BoxData[ \(TraditionalForm\`10\^38\)]], ") distinct GUIDs. Microsoft provides us with a CoCreateGuid function to \ generate \"extremely likely distinct\" GUIDs. If the function works as \ advertised, how many GUIDs must be generate before there is an appreciable \ chance that they start to repeat? That's the question that occured to me \ when I had to generate quite a number of GUIDs for my programming projects.\n\ \t\n\tThe first thing that we should notice is that this problem is the same \ problem as the Birthday Paradox problem, with the number of days in a year \ equals to ", Cell[BoxData[ \(TraditionalForm\`2\^128\)]], " instead of 365, the people in a room are replaced by GUIDs, and the \ question becomes \"How many GUIDS must be generated before at least two of \ them repeat?\"\n\t\n\tWe replace the formula for p[k] with p[N,k] where \ p[N,k] is the chance of having at least two GUIDs with the same value, given \ that the number of possible GUIDs is N. We just replace 365 in p[k] with N \ and get our new formula:" }], "Text"], Cell[BoxData[ \(p[N_, k_] := 1 - \(\((N - 1)\)!\)/\((\(\((N - k - 1)\)!\) N^k)\)\)], "Input"], Cell["\tTo check our new formula, we calculate p[365,22]:", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(p[365, 22] // N\)], "Input"], Cell[BoxData[ \(0.507297234323985346`\)], "Output"] }, Open ]], Cell["\tThis agree with p[22].", "Text"], Cell["\<\ \tSince we will deal with extremely large N, it's a good idea to find some \ approximation so that the factorials will not exhaust our computing resource. \ We use the first term of Stirling approximation of factorial function:\ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(Normal[Series[Factorial[x], {x, Infinity, 1}]]\)], "Input"], Cell[BoxData[ \(E\^\(-x\)\ \@\(2\ \[Pi]\)\ \@\(1\/x\)\ x\^\(1 + x\)\)], "Output"] }, Open ]], Cell["\<\ \tand define logfactorial function to be the natural log of the \ approximation:\ \>", "Text"], Cell[BoxData[ \(logfactorial[x_] := \ x\ Log[x] - x + 1/2 Log[2\ Pi\ x]\)], "Input"], Cell["\<\ \tTo see how good our approximation is, we list some of its relative \ errors:\ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(TableForm[ Table[{2^x, 100 \((Exp[logfactorial[2^x]]/\(\((2^x)\)!\) - 1.0)\)}, {x, 3, 10}], TableHeadings\ -> \ {None, {"\", "\<% error of approximated n!\>"}}]\)], "Input"], Cell[BoxData[ TagBox[GridBox[{ {\("n"\), \("% error of approximated n!"\)}, {"8", \(-1.03572556384761149`\)}, {"16", \(-0.519411958723703381`\)}, {"32", \(-0.260069423917286268`\)}, {"64", \(-0.130122540880517334`\)}, {"128", \(-0.0650828461408292646`\)}, {"256", \(-0.0325467691664749203`\)}, {"512", \(-0.0162747151362885311`\)}, {"1024", \(-0.00813768944880610689`\)} }, RowSpacings->1, ColumnSpacings->3, RowAlignments->Baseline, ColumnAlignments->{Left}], (TableForm[ #, TableHeadings -> {None, {"n", "% error of approximated n!"}}]&)]], "Output"] }, Open ]], Cell["\<\ \tSo, for n as small as 8, our approximate n! is off by only a percent. We \ then write an approximate formula for p[N,k] for large N, replacing all the \ factorials with its Stirling approximation:\ \>", "Text"], Cell[BoxData[ \(approxP[N_, k_] := \ 1 - Exp[\ \(-k\)\ Log[N] + \((\((N - 1)\) Log[N - 1] - \((N - 1)\) + 1/2 Log[2 Pi\ \((N - 1)\)])\) - \((\((N - k - 1)\) Log[N - k - 1] - \((N - k - 1)\) + 1/2 Log[2 Pi\ \((N - k - 1)\)])\)]\)], "Input"], Cell[CellGroupData[{ Cell[BoxData[ \(approxP[365, 22] // N\)], "Input"], Cell[BoxData[ \(0.507289978248492534`\)], "Output"] }, Open ]], Cell[TextData[{ "\tNow, we notice that at large N, p[N, k] will be appreciable only for k \ at least as large as", Cell[BoxData[ \(TraditionalForm\`\(\ \@N\)\)]], " , so we try to find a limit for p[N, a ", Cell[BoxData[ \(TraditionalForm\`\(\ \@N\)\)]], "] for positive number a:" }], "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(Limit[approxP[N, a\ N^\((1/2)\)], {N -> Infinity}]\)], "Input"], Cell[BoxData[ \({1 - E\^\(-\(a\^2\/2\)\)}\)], "Output"] }, Open ]], Cell[TextData[{ "\tWe then try to find a value of a for which p[N, a ", Cell[BoxData[ \(TraditionalForm\`\(\ \@N\)\)]], "] is equal to 0.5:" }], "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(Solve[1 - E\^\(-\(a\^2\/2\)\) == \ 0.5, a]\)], "Input"], Cell[BoxData[ \({{a \[Rule] \(-1.17741002251547466`\)}, { a \[Rule] 1.17741002251547466`}}\)], "Output"] }, Open ]], Cell[TextData[{ "\tTherefore, p[N,1.18", Cell[BoxData[ \(TraditionalForm\`\@N\)]], "] is about 0.5 for large N. This means that if the total number of \ distinct GUIDs is N, we can expect to generate about 1.18", Cell[BoxData[ \(TraditionalForm\`\@N\)]], " GUIDs before there is a 50% chance that they repeat. In our case, N is ", Cell[BoxData[ \(TraditionalForm\`2\^128\)]], " and 1.18", Cell[BoxData[ \(TraditionalForm\`\@N\)]], " is about 2 x ", Cell[BoxData[ \(TraditionalForm\`10\^19\)]], " which is definitely a big number." }], "Text"], Cell[TextData[{ "\tLet's say that there are a million programmers each generating a million \ GUIDs per seconds, it will take 2 x ", Cell[BoxData[ \(TraditionalForm\`10\^7\)]], " seconds or 116 days to generate 2 x ", Cell[BoxData[ \(TraditionalForm\`10\^19\)]], "GUIDs. A more likely situation is 100,000 programmers each generating 1 \ GUID per hour. This will take 2 x ", Cell[BoxData[ \(TraditionalForm\`10\^14\)]], "hours or twenty two billion years to generate 2 x ", Cell[BoxData[ \(TraditionalForm\`10\^19\)]], "GUIDs. For those of you who still wonder, our estimated age of the \ universe since big bang is between 12 and 15 billion years.\n\n\tSo, assuming \ that the implementation of the GUID genenating function is not defective, I \ don't think I will generate repeating GUIDs anytime soon. However, \ considering how buggy Microsoft Windows can be, it wouldn't surprise me that \ there will be a crisis arising from repeating GUIDs akin to our current \ Year-2000 problems before I die :-)" }], "Text"] }, Open ]] }, Open ]] }, FrontEndVersion->"Microsoft Windows 3.0", ScreenRectangle->{{0, 1024}, {0, 712}}, WindowSize->{484, 589}, WindowMargins->{{230, Automatic}, {Automatic, -12}}, StyleDefinitions -> "DEFAULT.NB" ] (*********************************************************************** Cached data follows. If you edit this Notebook file directly, not using Mathematica, you must remove the line containing CacheID at the top of the file. The cache data will then be recreated when you save this file from within Mathematica. ***********************************************************************) (*CellTagsOutline CellTagsIndex->{} *) (*CellTagsIndex CellTagsIndex->{} *) (*NotebookFileOutline Notebook[{ Cell[CellGroupData[{ Cell[1731, 51, 195, 5, 285, "Title"], Cell[1929, 58, 40, 0, 54, "Subtitle"], Cell[1972, 60, 278, 5, 71, "Text"], Cell[2253, 67, 2332, 62, 409, "Text"], Cell[4588, 131, 110, 2, 27, "Input"], Cell[4701, 135, 56, 0, 33, "Text"], Cell[CellGroupData[{ Cell[4782, 139, 172, 3, 59, "Input"], Cell[4957, 144, 3807, 110, 439, "Output"] }, Open ]], Cell[8779, 257, 326, 5, 90, "Text"], Cell[CellGroupData[{ Cell[9130, 266, 56, 1, 27, "Input"], Cell[9189, 269, 13237, 381, 187, 3787, 260, "GraphicsData", "PostScript", "Graphics"], Cell[22429, 652, 130, 3, 27, "Output"] }, Open ]], Cell[CellGroupData[{ Cell[22596, 660, 35, 0, 54, "Subtitle"], Cell[22634, 662, 2386, 42, 603, "Text"], Cell[25023, 706, 100, 2, 27, "Input"], Cell[25126, 710, 67, 0, 33, "Text"], Cell[CellGroupData[{ Cell[25218, 714, 48, 1, 27, "Input"], Cell[25269, 717, 55, 1, 27, "Output"] }, Open ]], Cell[25339, 721, 40, 0, 33, "Text"], Cell[25382, 723, 253, 4, 71, "Text"], Cell[CellGroupData[{ Cell[25660, 731, 79, 1, 27, "Input"], Cell[25742, 734, 85, 1, 50, "Output"] }, Open ]], Cell[25842, 738, 104, 3, 33, "Text"], Cell[25949, 743, 89, 1, 27, "Input"], Cell[26041, 746, 102, 3, 33, "Text"], Cell[CellGroupData[{ Cell[26168, 753, 231, 5, 91, "Input"], Cell[26402, 760, 704, 18, 166, "Output"] }, Open ]], Cell[27121, 781, 223, 4, 71, "Text"], Cell[27347, 787, 314, 6, 91, "Input"], Cell[CellGroupData[{ Cell[27686, 797, 54, 1, 27, "Input"], Cell[27743, 800, 55, 1, 27, "Output"] }, Open ]], Cell[27813, 804, 317, 9, 52, "Text"], Cell[CellGroupData[{ Cell[28155, 817, 83, 1, 27, "Input"], Cell[28241, 820, 59, 1, 49, "Output"] }, Open ]], Cell[28315, 824, 164, 5, 33, "Text"], Cell[CellGroupData[{ Cell[28504, 833, 75, 1, 47, "Input"], Cell[28582, 836, 116, 2, 27, "Output"] }, Open ]], Cell[28713, 841, 599, 19, 90, "Text"], Cell[29315, 862, 1064, 22, 242, "Text"] }, Open ]] }, Open ]] } ] *) (*********************************************************************** End of Mathematica Notebook file. ***********************************************************************)