The probability of k 9's in a string of random digits can be worked out like this. First, let's answer the question, what is the probability that we will not see a string of k 9s after n digits knowing the last r digits are 9s. Let's call this p(k, n, r). More on r in a minute.

Look at the last k digits. There are k cases to consider depending on where the first non-9 is. Since we're only considering the cases without k consecutive 9s, there must be at least one. In each case, we no longer care about the digits after that and can recurse on the problem with a now shorter string knowing it ends in a few 9s.

For example, if we're calculating p(4, 10, 0) we have 4 cases (using 0 as a placeholder for any non-9 and x as a placeholder for any digit). The result will be the sum of each case since they are mutually exclusive.

...0xxx - which happens with a probability of (9/10) and we recurse on p(4, 6, 0)

...90xx - which happens with a probability of (1/10)*(9/10) and we recurse on p(4, 7, 1)

...990x - etc.

...9990

How does having 9s on the end change things? It's pretty straightforward. We simply discard any cases that'd conflict with that. We already counted the probability for those trailing 9s, so no need to count it again.

Recurse until you hit one something you can compute directly. (I came up with four separate base cases.) Then your final answer will be 1 minus the result, or 1 - p(6, 1000, 0) for your question.

Now, I wrote up a little Python program to compute this. Assuming I haven't messed up somewhere (not entirely unlikely), I get that the probability is about 0.9% or about 1 in 112.

Here's the program:

Code:

import math
memo = {}
def p(k, n, r):
if (k,n,r) in memo:
return memo[(k,n,r)]
if r >= k:
return 0
if k == 1:
return math.pow(9/10, n)
if k > n:
return 1
if k == n:
return 1 - math.pow(1/10, n - r)
t = 0
for i in range(k-r):
t += math.pow(1/10, i) * (9/10) * p(k, n-k+i, i)
memo[(k,n,r)] = t
return t
print(1 - p(6, 10000, 0))

Edit: Oh. I should point out that I'm fairly certain there's easier ways to do this, but I'm not so certain there's a closed form for the answer. This is just what I came up with off the top of my head (more or less).