If I flip a coin 10 times in a row, obviously the probability of rolling heads ten times in a row is $\left(\frac{1}{2}\right)^{10}$. However, I am not sure how to calculate the exact odds that I will have at some point rolled heads 10 times in a row during a series of n flips. I have written a program to calculate the odds, but it runs in exponential time on n so it is relatively unusable. Here are the first couple results:
in 10 rolls, 0.0009765625.
in 11 rolls, 0.00146484375.
in 12 rolls, 0.001953125.
in 13 rolls, 0.00244140625.
in 14 rolls, 0.0029296875.
in 15 rolls, 0.00341796875.
in 16 rolls, 0.00390625.
in 17 rolls, 0.00439453125.
in 18 rolls, 0.0048828125.
in 19 rolls, 0.00537109375.
in 20 rolls, 0.005859375.
in 21 rolls, 0.006347179412841797.
in 22 rolls, 0.006834745407104492.
in 23 rolls, 0.007322072982788086.
in 24 rolls, 0.007809162139892578.
in 25 rolls, 0.008296012878417969.
in 26 rolls, 0.008782625198364258.
in 27 rolls, 0.009268999099731445.
in 28 rolls, 0.009755134582519531.
in 29 rolls, 0.010241031646728516.
in 30 rolls, 0.010726690292358398.
The source code is here
Best Answer
Here is my attempt: So denote by $P_i$ the probability of having $10$ heads in a row in $i$ tosses. So $P_{10}=1/2^{10}$.
For $i=10,...,20$, we can calculate the probability straight forward by saying: Probability that I get $10$ heads row and my heads start at $1$ plus probability that I get $10$ heads in a row and I start at $2$ plus, and so on. For instance, for $i=16$ we have $1/2^{10}+6/2^{11}=0.390625$ precisely what you got.
When $i>20$, then the counting becomes a little more messy, but I think its doable using recursion. Note that $P_{i+1}=P_i+$Probability that my $10$ heads in a row start at $i-9$ (let me denote this probability $Q_i$). So you know that $P_i$ is for the first couple of cases, note that $Q_i$ for $i\leq 20$ is just $1/2^{11}$ because we need a $T$ to go on the $i-10$ position and followed by $10$ heads, however, that does not work for say $i=21$ because we want more, we want the $11$th position to be a $T$, the following to be 10 $H$s, and the previouse ones not to be a string of $10$ heads because we are counting the strings whose starting point is at $12$. Thus, $Q_{21}=(1/2^{11})(1-P_{10})$. Hence, $P_{21}=P_{20}+Q_{21}$ to exactly what you have.
For $P_{22}=P_{21}+Q_{22}$ where $Q_{22}=(1/2^{11})(1-P_{11})$, I just checked and indeed I get the same result.
In general, you can build them recursively, and use $Q_i=(1/2^{11})(1-P_{i-11})$.
A little more clear (above was me thinking as I typed, so it turned out somewhat messy): You can denote $P_0,..,P_9$ all to be $0$, $P_{10}=1/2^{10}$, and $P_n=P_{n-1}+(1/2^{11})(1-P_{n-11})$.