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.
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.
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.
Let x = (1-\eps). We know that for x < 0.9 (say) the summation is bounded by a small constant.
Now consider expanding the sum until x^{2^i} = 0.9
(1-\eps) + (1-\eps)^2 + (1-\eps)^4 + ...
(1- \eps) + (1-2\eps) + (1-\4eps) + ...
the number of terms needed to get to 0.9 is something like \log(1/eps), and the result follows.
the info you really want seems available in Gonnet/Yates, Handbook of Algorithms and Data Structures, a rather unappreciated and highly useful book.
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.
Yep, the answer is 42.
ReplyDeletePosted by Anonymous
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.
ReplyDeleteNow 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.
Posted by Michael Mitzenmacher
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.
ReplyDeleteLet x = (1-\eps). We know that for x < 0.9 (say) the summation is bounded by a small constant.
Now consider expanding the sum until x^{2^i} = 0.9
(1-\eps) + (1-\eps)^2 + (1-\eps)^4 + ...
(1- \eps) + (1-2\eps) + (1-\4eps) + ...
the number of terms needed to get to 0.9 is something like \log(1/eps), and the result follows.
Posted by Anonymous
Thanks all ! I knew someone would know the answer !! Now if only I could also solve my research questions this way ;)
ReplyDeletePosted by Suresh
Now if only I could also solve my research questions this way ;)
ReplyDeletethat is called the "lazyweb" ;)
Posted by Anonymous
the info you really want seems available in Gonnet/Yates, Handbook of Algorithms and Data Structures, a rather unappreciated and highly useful book.
ReplyDeleteIf 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.
Posted by Anonymous