Timeline for How to show a function converges to 1
Current License: CC BY-SA 4.0
19 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 18 at 20:47 | comment | added | Zach Hunter | okay the lemmas are properly written. the conclusion is not the prettiest, but hopefully clear now. | |
| Jan 18 at 20:45 | history | edited | Zach Hunter | CC BY-SA 4.0 |
added 1443 characters in body
|
| Jan 18 at 6:06 | comment | added | Zach Hunter | ah sorry, I really should. I will set a reminder to do it tonight after work. | |
| Jan 18 at 2:46 | comment | added | Timothy Chow | @ZachHunter Are you going to rewrite your answer? | |
| Dec 20, 2023 at 9:32 | history | bounty ended | Simd | ||
| Dec 17, 2023 at 11:42 | comment | added | Zach Hunter | yeah I will rewrite in a day or so. | |
| Dec 17, 2023 at 8:20 | comment | added | Alex Ravsky | @FedorPetrov I usually read all comments. | |
| Dec 17, 2023 at 6:58 | comment | added | Fedor Petrov | @ZachHunter then I suggest to rewrite the answer, as now it looks like incomplete, and my MO experience says that nobody reads the comments | |
| Dec 16, 2023 at 17:27 | comment | added | Zach Hunter | oops I forgot it was over an interval, I thought you meant as a function to $p$. yeah that looks good. | |
| Dec 16, 2023 at 8:04 | comment | added | Fedor Petrov | $\epsilon_2$ is a constant, what do you mean by shrunking exponentially? We remain in the same interval $[\alpha,\beta]$ only for finitely many steps, and when we leave it, the probability is already at least $\beta$. | |
| Dec 12, 2023 at 15:09 | comment | added | Zach Hunter | yeah but if $\epsilon_2$ shrunk exponentially with each iteration, you could be screwed. but really $\epsilon_2$ should be a decreasing function of $p$ (presumably). in which case, we always increase by $\epsilon_2(.99)$ until we get the desired ratio. | |
| Dec 12, 2023 at 6:42 | comment | added | Fedor Petrov | if you want to avoid computations, then simply note that $((1-\epsilon) p+\epsilon q):((1-\epsilon) q)>p:q$, thus for every closed interval $[\alpha,\beta]\subset (0,1)$ there exist $\epsilon_1,\epsilon_2>0$ such that if $p\in [\alpha,\beta]$ and you perform $\epsilon_1n$ steps, then the density $p$ increases at least by $\epsilon_2$ with probability $1-o(1)$. This suffices. | |
| Dec 12, 2023 at 3:43 | comment | added | Fedor Petrov | If you have $n$ balls, the density of white is $p\in (10^{-9},1-10^{-2}]$ and you apply $10^{-9}n$ steps, the density seems to increase at least by $10^{-1000}$ | |
| Dec 12, 2023 at 2:24 | comment | added | GH from MO | In your first display, $p$ cannot exceed $1/4$, because in that case $p-4p^2$ is negative. | |
| Dec 12, 2023 at 0:57 | history | edited | Zach Hunter | CC BY-SA 4.0 |
bad wifi. half of my edit was missing last time.
|
| Dec 12, 2023 at 0:36 | history | edited | Zach Hunter | CC BY-SA 4.0 |
deleted 184 characters in body
|
| Dec 12, 2023 at 0:30 | comment | added | Zach Hunter | okay yeah, $f(a,b)\ge a/(a+b)$ is easy. the main annoying thing with getting 99 percent is showing that we converge to 1 rather than some weird other solution (presumably you could show that the amount we increment at each stage is monotone, but that requires calculation). but doing a billion Chernoff bounds is what I want to do. I just don't have the know-how to make sure the differential equation that underlies things actually tends to 1 (though it surely ought to). | |
| Dec 11, 2023 at 20:46 | comment | added | Fedor Petrov | We have a uniform bound $f(a, b) \ge a/(a+b) $. For getting at least 99 percent of white balls we may partition the steps onto billion parts and apply Chernoff bound for each part, can not we? | |
| Dec 11, 2023 at 17:03 | history | answered | Zach Hunter | CC BY-SA 4.0 |