Timeline for Probability of n-bit sequence appearing at least twice in m-bit sequence
Current License: CC BY-SA 3.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 28, 2016 at 20:07 | history | bounty ended | titus.andronicus | ||
| Mar 28, 2016 at 20:06 | vote | accept | titus.andronicus | ||
| Mar 26, 2016 at 22:44 | comment | added | Neil G | This one: stats.stackexchange.com/questions/21825/… | |
| Mar 26, 2016 at 20:00 | comment | added | Neil G | Nice explanation! Also, all very insightful points, @whuber. The final point is reminiscent of our two different answers to a similar problem somewhere on this site :) | |
| Mar 26, 2016 at 15:03 | history | edited | josliber | CC BY-SA 3.0 |
OP clarified they are seeking at least 2 occurrences, so I'll remove the last bit
|
| Mar 25, 2016 at 13:42 | history | edited | josliber | CC BY-SA 3.0 |
Remove intro (since I think my other answer actually is a reasonably simple closed-form expression)
|
| Mar 24, 2016 at 20:33 | history | edited | josliber | CC BY-SA 3.0 |
deleted 86 characters in body
|
| Mar 24, 2016 at 20:25 | comment | added | whuber♦ |
+1, especially for working out the hardest part of the solution explicitly, which is computation of the transition matrix. I suspect a reasonably succinct formula could be found in terms of the data structure typically used in the Boyer-Moore search algorithm. BTW, for larger problems where $m$ is big, diagonalize probs first and compute its power directly, rather than iteratively finding the power: not only will it be much faster, it will also have better numerical accuracy. A bonus is that it can suggest accurate asymptotic approximations.
|
|
| Mar 24, 2016 at 20:23 | history | edited | josliber | CC BY-SA 3.0 |
added 468 characters in body
|
| Mar 24, 2016 at 20:11 | history | answered | josliber | CC BY-SA 3.0 |