tag:blogger.com,1999:blog-4115025577315673827.post7611525961909168046..comments2020-01-23T12:35:45.593+05:30Comments on CSE Blog - quant, math, computer science puzzles: Birthday GamePratik Poddarhttp://www.blogger.com/profile/11577606981573330954noreply@blogger.comBlogger18125tag:blogger.com,1999:blog-4115025577315673827.post-27480499185143254972012-01-20T19:51:23.365+05:302012-01-20T19:51:23.365+05:30:) Yes, you got it correct prashant. Cheers!:) Yes, you got it correct prashant. Cheers!Pratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-49057728650538552002012-01-12T11:41:47.637+05:302012-01-12T11:41:47.637+05:30I got hold of it now.Here is how it goes.
When I...I got hold of it now.Here is how it goes.<br /><br /><br />When I talk that what is the minimum number of people required so that at least two people share their b’days ,its 23. Here we look for the cases where probability touches 50% for the ist time and it occurs at 23rd position. In this case we have 23C2 number of pairs to compare their respective b’days. If you put p(x)= 1-e^(-x^2)/2*365 > 0.5 <br />You will get approx 23.<br />While ,in case there is a contest I chose P(x)-p(x-1) to be maximized.its nothing but mathematical form of the statement that kth person has k choices of matching bdays and also nobody has won yet who are standing in front of him.<br /> <br />Here no 50% thing comes,its just a simple case of finding the maxima in the curve of p(x)-p(x-1) .<br />In simple words for the 2nd person to win ,the conditions to be satisfied are:<br /> 1.Nobody in front of him won yet<br /> 2.he has 1 choice of dates out of 365 to match his bdays(because only one person is standing in front of him)<br /> <br /> <br /> <br />For kth person in queue,his winning is dependent on:<br /> 1.no body in k-1 persons standing before him won yet.<br /> 2. kth person has k-1 out of 365 to chose from ,to match his b’day.<br /> <br />Find the probability ,p(k)= p(no one won yet) *[(k-1)/365]<br /> <br />This gets maximized at 20.prashanthttps://www.blogger.com/profile/06914877488024515021noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-56592947651232606962012-01-11T09:56:55.008+05:302012-01-11T09:56:55.008+05:30Where am I wrong?Where am I wrong?prashanthttps://www.blogger.com/profile/06914877488024515021noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-29854114495831209582012-01-11T09:56:38.282+05:302012-01-11T09:56:38.282+05:30So I tried to make a small code:
What I wrote was...So I tried to make a small code:<br /><br />What I wrote was a recursive method.<br /><br />public class BirthDayParadox {<br /><br /> public static void main(String[] args) {<br /> int n;<br /> for (n = 1; n <= 365; n++){<br /> double k = 1- different_birthdays(n);<br /> System.out.println( n +" "+k);<br /> }<br /> }<br /> static double different_birthdays(int n)<br /> {<br /> return n == 1 ? 1.0 : different_birthdays(n-1) * (365.0-(n-1))/365.0;<br /> }<br /> <br />}<br /><br />The output of the code is coming out to be:<br /><br />1 0.0<br />2 0.002739726027397249<br />3 0.008204165884781456<br />4 0.016355912466550326<br />5 0.02713557369979369<br />6 0.04046248364911165<br />7 0.05623570309597559<br />8 0.07433529235166925<br />9 0.09462383388916695<br />10 0.1169481777110779<br />11 0.14114137832173335<br />12 0.1670247888380647<br />13 0.19441027523242982<br />14 0.22310251200497344<br />15 0.2529013197636867<br />16 0.28360400525285023<br />17 0.3150076652965609<br />18 0.3469114178717895<br />19 0.37911852603153684<br />20 0.41143838358058016<br />21 0.4436883351652059<br />22 0.4756953076625502<br />23 0.5072972343239855<br />24 0.5383442579145289<br />25 0.568699703969464<br />26 0.598240820135939<br />27 0.6268592822632421<br />28 0.6544614723423995<br />29 0.680968537477777<br />30 0.7063162427192686<br />31 0.7304546337286438<br />32 0.7533475278503207<br />33 0.774971854175772<br />34 0.7953168646201543<br />35 0.8143832388747152<br />36 0.8321821063798795<br />37 0.8487340082163846<br />.....<br />at 23 position I am getting p(x)>0.5prashanthttps://www.blogger.com/profile/06914877488024515021noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-85395316254696798222012-01-11T09:55:40.679+05:302012-01-11T09:55:40.679+05:30I really had a hard time yesterday ,battling this ...I really had a hard time yesterday ,battling this birthday paradox.<br /><br /><br />I am sharing my mathematical calculations here:<br />For the ist person ,bday =365/365<br />2nd person 364/365 or 1- 1/365 In case the bdays don’t collide<br />3rd 363/365 or 1- 2/365<br /><br />And so on..<br />Lets assume xth position is favorable<br />So at xth position prob. 365-(k-1)/365 or 1- (x-1)/365 <br /><br /><br />We know e^x = 1+x+x^2/2!+…..<br />Approx. e^x = 1+x<br /><br />Therefore, 1- 1/365 = e^-1/365<br /><br />1- 2/365 = e^-2/365<br /><br /><br />All are independent therefore probability for no collisions in birthdates (e^-1/365)( e^-2/365)…….( e^-(x-1)/365) =g(x)<br />1-g(x)=p(x) where p(x) is prob of bdays collision<br /><br />f(x)=p(x)-p(x-1) it should be maximized<br />so we need to calculate value of f’(x) = 0<br /><br />p(x)= 1- e^-(1+2+…+x-1)/365= 1- e^-(x-1)x/2*365 = 1-e^(-x^2)/2*365 <br /><br />p(x-1) = 1-e^(-(x-1)^2)/2*365<br /><br /><br />f(x)= e^(-(x-1)^2)/2*365 - e^(-x^2)/2*365 <br />f’(x)= 1/x = 1-(e^(-(2x-1))/2*365)<br /><br />by hit and trial I got x =19.6 or 20<br /><br /><br />then I saw http://en.wikipedia.org/wiki/Birthday_problem has the solution as 23.prashanthttps://www.blogger.com/profile/06914877488024515021noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-53499913795002089442011-02-20T00:41:40.465+05:302011-02-20T00:41:40.465+05:30Thanks a lot Pratik for explanation.Thanks a lot Pratik for explanation.Vipulhttps://www.blogger.com/profile/18123066138041812770noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-70682023754050671992011-02-18T13:28:51.232+05:302011-02-18T13:28:51.232+05:30@Vipul..
I am assuming you understood how I got
P(...@Vipul..<br />I am assuming you understood how I got<br />P(k+1)=(binomial(n,k)*k!*k)/(n^(k+1))<br /><br />P(k+1)=(n!*k)/(n-k)!(n^(k+1))<br />P(k)= (n!*(k-1))/(n-k+1)!(n^(k))<br /><br />P(k+1)-P(k)= [n!/((n-k+1)!n^(k+1))]*[k(n-k+1)-(k-1)*n]<br />= Positive*(kn-k^2+k-kn+n) = Positive*(k+n-k^2)<br /><br />Hope that clarifies.Pratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-87371732633491518582011-02-17T18:52:37.152+05:302011-02-17T18:52:37.152+05:30Hi Pratik,
Would you please explain how did you ...Hi Pratik, <br /><br />Would you please explain how did you get this expression:<br /><br />P(k+1)-P(k) = positive*(k-k^2+n)<br /><br />Please help me here.<br /><br />Thanks,<br />VipulVipulhttps://www.blogger.com/profile/18123066138041812770noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-50226421042395083582011-01-28T12:01:06.115+05:302011-01-28T12:01:06.115+05:30This comment has been removed by a blog administrator.kalyanhttps://www.blogger.com/profile/17407735020886348965noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-44554853672349201302011-01-23T23:25:28.500+05:302011-01-23T23:25:28.500+05:30@Nishant (Novacaine)
I am defining P(k+1) as proba...@Nishant (Novacaine)<br />I am defining P(k+1) as probability that you stand at (k+1)th position and you are the first one to have a common birthday.<br />So, first fill first k spots with k different birthdays. then fill the last spot with any of these k entries. this gives you the numerator.<br /><br />The expression you are giving gives probability = (1-probability that there is no common birthdays in first k elements) which is different from what we need to do<br /><br />@Nikhil..<br />Global maxima has to be either local maxima or extremum points. Extremum points (standing at starting and at end) do not help. Hence, local maxima is the solution. Makes sense?Pratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-77050845332153873482011-01-22T11:50:17.750+05:302011-01-22T11:50:17.750+05:30Aah. I missed that denominator is also a function ...Aah. I missed that denominator is also a function of K and instead took it to be constant ! <br /><br />Anyways, its not immediately clear to me that any local maxima is also a global maxima. Any clarifications please?Nikhil Garghttps://www.blogger.com/profile/00137167173637522039noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-43188761715854810282011-01-21T15:41:26.018+05:302011-01-21T15:41:26.018+05:30Isn't P(k+1) = 1 - (binomial(n,k)*k!*(n-k))/(n...Isn't P(k+1) = 1 - (binomial(n,k)*k!*(n-k))/(n^k+1)?<br /><br />Referring to http://en.wikipedia.org/wiki/Birthday_paradoxNovacainehttps://www.blogger.com/profile/04966300170391606736noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-91437024463105196732011-01-20T16:11:39.416+05:302011-01-20T16:11:39.416+05:30Probability of winning if you stand at k+1 is P(k+...Probability of winning if you stand at k+1 is P(k+1)=(binomial(n,k)*k!*k)/(n^(k+1))<br /><br />P(k+1)-P(k) = positive*(k-k^2+n)<br /><br />P(k+1)-P(k)<0 and P(k)-P(k-1)>0<br />implies<br />k^2-k-n>0 and k^2-3k+2-n<0<br /><br />So, k>(1+sqrt(1+4n))/2 and k<(3+sqrt(1+4n))/2<br /><br />n=365<br />k>19.61 and k<20.61<br /><br />So, k=20 :)<br /><br />Zubin guessed it correctly :)Pratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-87275708815783226132011-01-18T17:08:34.105+05:302011-01-18T17:08:34.105+05:30I think the answer is approximately 20th or someth...I think the answer is approximately 20th or something. It's kind of approximate, i guess.<br /><br />From this wiki page -- <br />http://en.wikipedia.org/wiki/Birthday_paradox <br />Birthday collision occurrence can be approximated as having a form -> p(n) = 1 - e^(-n^2/2A) where A = 365<br /><br />Now, you can maximise your winning chances by maximising the function f(x) = p(x) - p(x-1); that is you cannot do any better by moving ahead in the line.<br /><br />f'(x)=0 ==> 1/x = 1-(e^(-(2x-1))/2A) and putting (expected answers :P) solving gives an x = 19 or 20.<br /><br />It's good to see this occurs at approx the 50% probability mark of the birthday problem where the slope of the curve is maximum.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-13099318559356941052011-01-14T20:04:53.858+05:302011-01-14T20:04:53.858+05:30Sorry if i get something wrong, but the goal is fo...Sorry if i get something wrong, but the goal is for me to match my birthday with somebody before me in the line, before they match their birthday.<br /><br />So if I stand at the k+1th place, I can make k pairs (my date with any of the k people before me). At the same time the k people before me can make (2Ck) pairs. They will have an edge as soon as they can make more pairs than me, no?<br />Which happens as soon as I stand past the 3rd place.<br />Me in 5th pos : 4 possible date pairs.<br />The 4 people before me can form 6 pairs ==> They have more odds to assemble a winning pair than I have...no ?<br /><br />Following that, the 3rd place is my best shot... <br /><br />Where did I fail ?Zebullonhttps://www.blogger.com/profile/15482616440490089819noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-44478798557177154942011-01-13T18:11:36.317+05:302011-01-13T18:11:36.317+05:30Problem similar to a problem in a quant company se...Problem similar to a problem in a quant company selection test this year. Winning=getting free ticket<br />Then P(Winning)= P(Your birthday matches with someone before you AND no one else before you has matching birthdays) <br />Assume each persons birthday is independent. So <br />P(first person winning)=0 <br />P(second person winning)= 1/365<br />P(third person winning)= 2/365 * 364/365<br />P(nth person winning) = n/365* 364/365 * ..... *(366-n)/365<br />Now to maximise,<br />P(nth person winning)>P((n-1)th person winning) and P((n+1)th person winning)<br />Solve to find optimal position.Gautamhttps://www.blogger.com/profile/07248556360293734740noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-9291651637263387662011-01-09T12:07:24.244+05:302011-01-09T12:07:24.244+05:30N which was size of event space, I forgot to menti...N which was size of event space, I forgot to mention was 365. :D<br /><br />So one must stand at 185th position, assuming line is long enough, else at the last position if line has less than 185 people.Nikhil Garghttps://www.blogger.com/profile/00137167173637522039noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-11374088649682928482011-01-09T11:54:46.132+05:302011-01-09T11:54:46.132+05:30Assume line has N people. What is the prob of winn...Assume line has N people. What is the prob of winning if you stand at K+1 th position ? Proportional to NcK * K. which is same as N * ( N-1cK-1). For best chances, N-1cK-1 should be maximized so K -1 should be same as (N-1)/2. <br />So we must stand at (N-1)/2 + 2 which is same as ceil(N/2) + 1.Nikhil Garghttps://www.blogger.com/profile/00137167173637522039noreply@blogger.com