Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

How likely is it that a number of consisting of n digits, contains a number consisting of n digits or less?

I though that perhaps I could multiply the number of permutations by the chance of such a permutation occuring (as displayed below), but some permutations allow for others to occur simultaneously. Doesn't that make my calculation invalid?

calculation attempt

Please note: I only want to calculate the chances of a number appearing at all, doesn't matter if that is once, twice or more.

share|improve this question
2  
+1 Nice problem. Let me point that the probability can not be a function of $n$ and $s$ alone. For instance, let $n=3$ and $s=2$. Then there are 19 3-digit numbers containing substring 12, but there are only 18 numbers containing substring 11. With $n=4$ and $s=2$, there are 279 4-digit numbers containing substring 12, and only 261 4-digit numbers containing substring 11. –  Sasha Dec 7 '11 at 20:04
add comment

1 Answer

up vote 7 down vote accepted

The answer to the question depends fairly sensitively on the specific properties of the needle (the number you're looking for). If the needle has $k$ digits, then it can appear in one of $n-k+1$ possible locations in the haystack, but these events aren't independent: for example, if the needle is $11$, then this number appearing anywhere in the haystack makes it more likely to appear nearby. So the answer ought to depend on how the needle "autocorrelates," and indeed it does.

It's easier to reformulate the problem slightly. Instead of looking for numbers in numbers, let's look for words in words (that way we don't have to deal with the annoying fact that numbers can't start with a $0$, and we can change the number of letters arbitrarily). For a given needle word $w$ over an alphabet $A$, the set of all words $L$ in which $w$ does not appear is a regular language. If $L_n$ denotes the number of words in $L$ of length $n$, then the generating function $$f(z) = \sum L_n z^n$$

is a rational function which can be explicitly computed from $w$. From this rational function we can determine a closed form for $L_n$ (and in any case it is easy to compute $L_n$ efficiently), and then the probability of interest is $$1 - \frac{L_n}{|A|^n}.$$

The details are somewhat involved but elementary and they are completely worked out in Flajolet and Sedgewick's Analytic Combinatorics preceding Proposition I.4.

Here is a simple example. If $A = \{ 0, 1 \}$ and $w = 11$, then $L_n$ turns out to be the Fibonacci number $F_{n+1}$, $$f(z) = \sum F_{n+1} z^n = \frac{1}{1 - z - z^2}$$

and the probability of interest is $$1 - \frac{F_{n+1}}{2^n} = 1 - \Omega \left( \left( \frac{1 + \sqrt{5}}{4} \right)^n \right).$$

One way to see that $L_n = F_{n+1}$ is to verify that it satisfies the Fibonacci recurrence $$L_{n+2} = L_{n+1} + L_n$$

(the initial conditions $L_0 = 1, L_1 = 2$ should be clear). To do this it's easier to consider auxiliary sequences $a_n, b_n$. The sequence $a_n$ counts the number of words of length $n$ not containing the substring $11$ and ending with a $0$, while the sequence $b_n$ counts the number of words of length $n$ not containing the substring $11$ and ending with a $11$.

Clearly $a_n + b_n = L_n$. On the other hand, since $11$ can't appear in any of these words, removing the $1$ from the end of a word ending with $1$ gives a word ending with $0$, so $b_{n+1} = a_n$. And removing the $0$ from the end of a word ending with $0$ gives a word ending with either $0$ or $1$, so $a_{n+1} = a_n + b_n$. Hence $$a_{n+2} = a_{n+1} + b_{n+1} = a_{n+1} + a_n$$

and similarly for $b_n$. The conclusion follows. A similar but more complicated argument works in general by defining more complicated sets of auxiliary sequences. A nice conceptual way to think of these auxiliary sequences is as counting paths in a finite state machine recognizing the language $L$.

share|improve this answer
    
Wow, this is much more complicated than I thought. I must admit that I hadn't even considered the involvement of numbers made up of equal digits. Not having taken any high-level maths courses, I will need some time to process your complex but interesting explanation - thank you so much for your efforts! –  Chris Dec 7 '11 at 20:27
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.