tag:blogger.com,1999:blog-6555947.post113038890949989634..comments2020-10-20T22:39:09.892-06:00Comments on The Geomblog: a puzzleSuresh Venkatasubramanianhttp://www.blogger.com/profile/15898357513326041822noreply@blogger.comBlogger6125tag:blogger.com,1999:blog-6555947.post-1130469837081749232005-10-27T21:23:00.000-06:002005-10-27T21:23:00.000-06:00the info you really want seems available in Gonnet...<I>the info you really want seems available in Gonnet/Yates, Handbook of Algorithms and Data Structures, a rather unappreciated and highly useful book.</I> <BR/><BR/>If it is any consolation, I understand both the first and second editions sold like pancakes when they came out, bought out mostly by practicioners. Theoreticians seem to pretty much have ignored it. <BR/><BR/><A></A><A></A>Posted by<A><B> </B></A>AnonymousAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-1130462522516775142005-10-27T19:22:00.000-06:002005-10-27T19:22:00.000-06:00Now if only I could also solve my research questio...Now if only I could also solve my research questions this way ;)<BR/><BR/>that is called the "lazyweb" ;) <BR/><BR/><A></A><A></A>Posted by<A><B> </B></A>AnonymousAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-1130442304127700312005-10-27T13:45:00.000-06:002005-10-27T13:45:00.000-06:00Thanks all ! I knew someone would know the answer ...Thanks all ! I knew someone would know the answer !! Now if only I could also solve my research questions this way ;) <BR/><BR/><A></A><A></A>Posted by<A><B> </B></A>SureshSuresh Venkatasubramanianhttps://www.blogger.com/profile/15898357513326041822noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-1130436315837683142005-10-27T12:05:00.000-06:002005-10-27T12:05:00.000-06:00Looks like Micharl beat me to it, I blame the time...Looks like Micharl beat me to it, I blame the time difference with the west coast. I don't have access to the book, but here's a simple handwavy proof for the bound. <BR/><BR/>Let x = (1-\eps). We know that for x < 0.9 (say) the summation is bounded by a small constant. <BR/><BR/>Now consider expanding the sum until x^{2^i} = 0.9 <BR/><BR/>(1-\eps) + (1-\eps)^2 + (1-\eps)^4 + ...<BR/><BR/>(1- \eps) + (1-2\eps) + (1-\4eps) + ... <BR/><BR/>the number of terms needed to get to 0.9 is something like \log(1/eps), and the result follows. <BR/><BR/><A></A><A></A>Posted by<A><B> </B></A>AnonymousAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-1130426106837047602005-10-27T09:15:00.000-06:002005-10-27T09:15:00.000-06:00This type of summation showed up in my thesis (ava...This type of summation showed up in my thesis (available on-line), where I was looking at the limit as x goes to 1. It's proprtional to log (1-x)^{-1}, funnily enough, if I'm remembering right.<BR/><BR/>Now that I've plugged my thesis, the info you really want seems available in Gonnet/Yates, Handbook of Algorithms and Data Structures, a rather unappreciated and highly useful book. On my copy it's page 303; Equation II.33 in Appendix 2. It's ugly enough I won't write it here. <BR/><BR/><A></A><A></A>Posted by<A><B> </B></A><A HREF="http://geomblog.blogspot.com/2005/10/puzzle.html#comments" REL="nofollow" TITLE="michaelm at eecs dot harvard dot edu">Michael Mitzenmacher</A>Michael Mitzenmacherhttps://www.blogger.com/profile/00458446293652845258noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-1130398940354319062005-10-27T01:42:00.000-06:002005-10-27T01:42:00.000-06:00Yep, the answer is 42. Posted by AnonymousYep, the answer is 42. <BR/><BR/><A></A><A></A>Posted by<A><B> </B></A>AnonymousAnonymousnoreply@blogger.com