Timeline for Asymptotic difference between a function and its "binomial average"
Current License: CC BY-SA 2.5
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 12:58 | history | edited | CommunityBot |
replaced http://mathoverflow.net/ with https://mathoverflow.net/
|
|
| Feb 21, 2011 at 5:43 | history | edited | Mike Spivey | CC BY-SA 2.5 |
made answer more precise
|
| Feb 19, 2011 at 0:59 | vote | accept | Mike Spivey | ||
| Feb 18, 2011 at 19:02 | comment | added | Mike Spivey | I think I need to make the claim "the initial terms in the function eventually become negligible in determining the value of $f(n)$ via the recurrence relation" more rigorous. I think I see how to do that, but I don't have time right now to type up the argument. I'll put it on my list of things to do. :) | |
| Feb 18, 2011 at 18:59 | comment | added | Mike Spivey | @Didier: 1. I wouldn't call it noise. If you allow $L = 0$ then the proof goes through more easily with the $h(n)$ function and you get $O(\log n)$, which is still interesting. 2. I think you're right. If you replace $C$ and $D$ with $L - \epsilon$ and $L + \epsilon$ and follow the proof through you get that $f(n)/\log_2 n $ is bounded by $L \pm \epsilon + O(1/\log_2 n)$. | |
| Feb 18, 2011 at 7:07 | comment | added | Did | .../... Another, more scary, way of saying that is that, if your proof works, it does show that $f(n)/\log_2(n)$ converges as soon as $f-\mathrm{Bin}(f)$ converges (since you say that one can take $C$ and $D$ as close to $L$ as one wants). Mmmm... | |
| Feb 18, 2011 at 7:07 | comment | added | Did | @Mike: 0. Yes, MO does provide some satisfying experiences... 1. About the $L=0$ case, you are right of course, I forgot you want $\Theta(\log(n))$ and not only $O(\log(n))$. Sorry about the noise. 2. Rereading your post, it seems that what you did is to bound the limsup and liminf of $f(n)/\log_2(n)$ by the limsup and liminf of the sequence $f-\mathrm{Bin}(f)$ (the one that you assume converges to $L$). .../... | |
| Feb 18, 2011 at 0:43 | comment | added | Mike Spivey | @Didier: Thanks! It was very satisfying when I realized your post and the answers and comments from the others were what I needed to answer my own question. :) The hypothesis $L \neq 0$ is needed for the logarithmic growth. For example, any constant $f(n)$ will have $L = 0$. Your other question is a good one. I'll have to think about it... | |
| Feb 18, 2011 at 0:20 | comment | added | Did | @Mike: Bravo! It seems the hypothesis $L\ne0$ is irrelevant. More importantly, do you think that in fact $f(n)/\log_2(n)\to L$? If really the initial terms of the sequence $(f(n))$ eventually become negligible, this should be true. Dunno... | |
| Feb 17, 2011 at 23:26 | vote | accept | Mike Spivey | ||
| Feb 17, 2011 at 23:30 | |||||
| Feb 17, 2011 at 23:17 | history | answered | Mike Spivey | CC BY-SA 2.5 |