# Probability that a random n-digit sequence has specific m-digit subsequence

We have a sequence of decimal digits $a_m=a_1 a_2 ... a_m$ and a random sequence of uniformely distributed decimal digits $a_n$, we want to estimate probability $P(a_m,n)$ such that $a_n$ contains $a_m$, i.e. '10012378' contains '123' and doesn't contain '101' or '345'.

Is it some well known problem? If it is hard to obtain general formula, may be there is a formula for specific sequence, e.g. sequence of ones.

So far we ended with following recursive formula for non-overlapping sequences ($a_m$ is such that $\forall k~ tail(a_m,k)\ne head(a_m,k)$): $$P(a_m,n)= \left\{\begin{matrix} P(a_m,n-1)+(1-P(a_m,n-m))/10^m&n\ge m \\ 0&n<m \end{matrix}\right.$$ But it is hard to estimate formula for large $n$. If there is no explicit formula, what is $\lim_{m\rightarrow\infty}P(a_m,10^m)$? What is $n(m)$ such that $P(a_m, n)>0.9$?

-

You will find that for your non-overlapping sequences $$P(a_m,n) \approx 1- \exp\left(-\frac{n}{\,10^m}\right)$$ so $\lim_{m\rightarrow\infty}P(a_m,10^m) = 1-e^{-1} \approx 0.632$ and $P(a_m, 10^m \log_e(10))\approx 0.9$

-
Thank you! I still can't figure it out, but I've written small program to compare results and it seems to be correct :) – DikobrAz Feb 27 '13 at 10:07