Timeline for What is the convergence rate of this "infinite monkey"-type probability?
Current License: CC BY-SA 4.0
6 events
when toggle format | what | by | license | comment | |
---|---|---|---|---|---|
Apr 5 at 16:56 | answer | added | Marcus M | timeline score: 1 | |
Apr 3 at 7:45 | comment | added | Joseph Expo | Thank you for your comment! I tried this approach and got stuck on computing the variance/applying chebyshev. Could you elaborate a little on that? Additionally, could you give some heuristics as to why $X$ should be Poisson in the limit? | |
Mar 30 at 14:09 | comment | added | Marcus M | Here's standard strategy. Let $X_{m}(n) = X$ be the number of pairs $1 \leq i < j \leq m + n$ for which you have $(R_i,\ldots, R_{i+n-1}) = (R_j,\ldots,R_{j+n-1})$. When $E X < 1$, you can use that as an upper bound on $A_{m}(n)$. In fact the Bonferroni inequalities imply $ E X - E \binom{X}{2} \leq P(A_m(n)) \leq E X$, so this will be good for when the mean is $\ll 1$. When the mean grows, you can compute the variance and use Chebyshev. If you really care, when the mean is constant, you can prove $X$ will be Poisson in the limit. | |
Mar 30 at 8:31 | history | edited | Joseph Expo | CC BY-SA 4.0 |
added 2 characters in body
|
S Mar 30 at 8:15 | review | First questions | |||
Mar 30 at 9:43 | |||||
S Mar 30 at 8:15 | history | asked | Joseph Expo | CC BY-SA 4.0 |