{"id":3859,"date":"2013-12-10T11:22:52","date_gmt":"2013-12-10T11:22:52","guid":{"rendered":"http:\/\/www.timestored.com\/b\/?p=3859"},"modified":"2013-12-03T19:26:00","modified_gmt":"2013-12-03T19:26:00","slug":"birthday-paradox-in-kdb","status":"publish","type":"post","link":"https:\/\/www.timestored.com\/b\/birthday-paradox-in-kdb\/","title":{"rendered":"Solving the Birthday Paradox in kdb q"},"content":{"rendered":"<p>In a previous post I looked at using the <a href=\"\/b\/rolling-dice-kdb-monte-carlo\/\">monte carlo method in kdb<\/a> to find the outcome of rolling two dice. I also posed the question:<\/p>\n<p><b>How many people do you need before the odds are good (greater than 50%) that at least two of them share a birthday?<\/b><\/p>\n<p>In our <a href=\"http:\/\/www.timestored.com\/kdb-training\">kdb+ training courses<\/a> I always advise breaking the problem down step by step, in this case:<\/p>\n<ol>\n<li>Consider making a function to examine the case where there are N people.<\/li>\n<li>Generate lists of N random numbers between 0-365 representing their birthdays.<\/li>\n<li>Find lists that contain collisions.<\/li>\n<li>Find the number of collisions per possibilities examined.<\/li>\n<li>Apply our function for finding the probability for N people to a list for many possibilities of N.<\/li>\n<\/ol>\n<p>In kdb\/q:\n<\/p>\n\r\n<textarea rows='12' cols='20' class='code' id='code-birthday-paradox'>\r\nq){x cut (x*99909)?365} 4 \/ consider it for 4 people\r\n340 217 139 191\r\n12  295 15  113\r\n344 206 161 203\r\n351 45  181 344\r\n138 47  311 205\r\n41  224 271 223\r\n283 47  77  77\r\n..\r\n\r\nq)\/ sort each list of numbers and then check for numbers the same beside each other\r\nq)\/ here we use the adverbs ': each previous and ' each\r\nq)(=':') asc each {x cut (x*99909)?365} 4\r\n0000b\r\n0000b\r\n0000b\r\n0000b\r\n0000b\r\n0000b\r\n0010b\r\n..\r\nq)\/ where any collisions occur return true\r\nq)any each (=':') asc each {x cut (x*99909)?365} 4\r\n0000000000000000000000000000000000000000000000000000000000000000000000000001000000000..\r\n\r\nq)\/ find the probability\r\nq){(sum x)%count x} any each (=':') asc each {x cut (x*99909)?365} 4\r\n0.01580438\r\n\r\nq)findProb:{{(sum x)%count x} any each (=':') asc each {x cut (x*99909)?365} x}\r\nq)\/ find the probality for N people from 2 to 101\r\nq)t:update prob:findProb peach a from ([] a:2+til 100)\r\nq)t\r\na  prob\r\n--------------\r\n2  0.002752505\r\n3  0.008357605\r\n4  0.01603459\r\n5  0.02655416\r\n6  0.04084717\r\n7  0.05693181\r\n8  0.07378715\r\n9  0.09346505\r\n10 0.1160856\r\n..\r\nq)exec first a from t where prob>0.5\r\n23\r\n<\/textarea><script type='text\/javascript'>var myCodeMirror = CodeMirror.fromTextArea(document.getElementById('code-birthday-paradox'), {lineNumbers: true, matchBrackets: true, indentUnit: 4, tabMode: 'default', mode: 'x-plsql', readOnly:true });<\/script>  \r\n\r\n\n<p>Plotting our data in using <a href=\"\/qstudio\">qStudio charting for kdb<\/a> we get:<\/p>\n<p><a href=\"\/qstudio\"><img loading=\"lazy\" src=\"https:\/\/www.timestored.com\/b\/wp-content\/uploads\/2013\/12\/birthday-problem-kdb-chart.png\" alt=\"kdb chart showing the birthday paradox\" width=\"728\" height=\"259\" class=\"alignnone size-full wp-image-3868\" srcset=\"https:\/\/www.timestored.com\/b\/wp-content\/uploads\/2013\/12\/birthday-problem-kdb-chart.png 728w, https:\/\/www.timestored.com\/b\/wp-content\/uploads\/2013\/12\/birthday-problem-kdb-chart-300x106.png 300w\" sizes=\"(max-width: 728px) 100vw, 728px\" \/><\/a><\/p>\n<p>Therefore as you can see from either the q code or the graph, you need 23 people to ensure there&#8217;s a 50% chance that atleast 2 people in the room share a birthday. For more details see the <a href=\"http:\/\/en.wikipedia.org\/wiki\/Birthday_problem\">wikipedia page<\/a>. This still leaves us with the other problem of finding Pi using the monte carlo method in kdb.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>In a previous post I looked at using the monte carlo method in kdb to find the outcome of rolling two dice. I also posed the question: How many people do you need before the odds are good (greater than 50%) that at least two of them share a birthday? In our kdb+ training courses [&hellip;]<\/p>\n","protected":false},"author":3,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_bbp_topic_count":0,"_bbp_reply_count":0,"_bbp_total_topic_count":0,"_bbp_total_reply_count":0,"_bbp_voice_count":0,"_bbp_anonymous_reply_count":0,"_bbp_topic_count_hidden":0,"_bbp_reply_count_hidden":0,"_bbp_forum_subforum_count":0},"categories":[2],"tags":[],"_links":{"self":[{"href":"https:\/\/www.timestored.com\/b\/wp-json\/wp\/v2\/posts\/3859"}],"collection":[{"href":"https:\/\/www.timestored.com\/b\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.timestored.com\/b\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.timestored.com\/b\/wp-json\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/www.timestored.com\/b\/wp-json\/wp\/v2\/comments?post=3859"}],"version-history":[{"count":15,"href":"https:\/\/www.timestored.com\/b\/wp-json\/wp\/v2\/posts\/3859\/revisions"}],"predecessor-version":[{"id":3882,"href":"https:\/\/www.timestored.com\/b\/wp-json\/wp\/v2\/posts\/3859\/revisions\/3882"}],"wp:attachment":[{"href":"https:\/\/www.timestored.com\/b\/wp-json\/wp\/v2\/media?parent=3859"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.timestored.com\/b\/wp-json\/wp\/v2\/categories?post=3859"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.timestored.com\/b\/wp-json\/wp\/v2\/tags?post=3859"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}