La respuesta a la pregunta depende bastante sensible a las propiedades específicas de la aguja (el número que estás buscando). Si la aguja ha $k$ dígitos, entonces puede aparecer en una de las $n-k+1$ posibles ubicaciones en el pajar, pero estos eventos no son independientes: por ejemplo, si la aguja es $11$, entonces este número aparecen en cualquier lugar en el pajar hace que sea más probable que aparezca en las cercanías. Así que la respuesta debería depender de cómo la aguja "autocorrelates," y de hecho lo hace.
Es más fácil para reformular el problema un poco. En lugar de buscar números en números, vamos a buscar palabras en palabras (de esa manera no tenemos que lidiar con el molesto hecho de que los números no puede comenzar con un $0$, y podemos cambiar el número de letras de forma arbitraria). Para un determinado aguja palabra $w$ sobre un alfabeto $A$, el conjunto de todas las palabras $L$ que $w$ no aparece es un lenguaje regular. Si $L_n$ indica el número de palabras en $L$ de la longitud de la $n$, entonces la generación de la función
$$f(z) = \sum L_n z^n$$
es una función racional que puede ser explícitamente calcula a partir de $w$. A partir de esta función racional se puede determinar de una forma cerrada para $L_n$ (y en cualquier caso es fácil de calcular, $L_n$ eficiente) y, a continuación, la probabilidad de que el interés es
$$1 - \frac{L_n}{|A|^n}.$$
Los detalles son un poco involucrados, pero la primaria y son completamente trabajado en Flajolet y Sedgewick de la Analítica de la Combinatoria anterior a la Proposición I. 4.
Aquí está un ejemplo sencillo. Si $A = \{ 0, 1 \}$$w = 11$, $L_n$ resulta ser el número Fibonacci$F_{n+1}$,
$$f(z) = \sum F_{n+1} z^n = \frac{1}{1 - z - z^2}$$
y la probabilidad de que el interés es
$$1 - \frac{F_{n+1}}{2^n} = 1 - \Omega \left( \left( \frac{1 + \sqrt{5}}{4} \right)^n \right).$$
Una forma de ver que $L_n = F_{n+1}$ es para comprobar que se satisface la recurrencia de Fibonacci
$$L_{n+2} = L_{n+1} + L_n$$
(las condiciones iniciales $L_0 = 1, L_1 = 2$ debe ser claro). Para hacer esto más fácil considerar auxiliar de secuencias de $a_n, b_n$. La secuencia de $a_n$ cuenta el número de palabras de longitud $n$ no contiene la subcadena $11$ y terminando con un $0$, mientras que la secuencia $b_n$ cuenta el número de palabras de longitud $n$ no contiene la subcadena $11$ y terminando con un $11$.
Claramente $a_n + b_n = L_n$. Por otro lado, desde la $11$ no puede aparecer en cualquiera de estas palabras, la eliminación de la $1$ desde el final de una palabra que termina con $1$ da una palabra que termina con $0$, lo $b_{n+1} = a_n$. Y la eliminación de la $0$ desde el final de una palabra que termina con $0$ da una palabra que termina con $0$ o $1$, lo $a_{n+1} = a_n + b_n$. Por lo tanto
$$a_{n+2} = a_{n+1} + b_{n+1} = a_{n+1} + a_n$$
y lo mismo para $b_n$. La conclusión de la siguiente manera. Una similar, pero más complicado argumento de las obras en general, mediante la definición más complicados conjuntos de auxiliar de secuencias. Un buen conceptual de la forma de pensar de estos auxiliares de secuencias es como contar las rutas en una máquina de estados finitos reconocer la lengua $L$.
