Número esperado de conjeturas consecutivas para obtener una secuencia dada de números

Question

Tengo un bloqueo en mi puerta de su dormitorio que realmente estúpido. Básicamente, sólo comprueba si es o no la secuencia de números que he puesto es el combo, si o no se haya restablecido la cerradura entre conjeturas. Así que digamos que mi combo es 5556. Entonces puedo entrada 555555556 en mi cerradura y se desbloquea, sin tener que reiniciar después de la introducción de los primeros cuatro números.

Traté de calcular el número esperado de número aleatorio conjeturas para finalmente introducir el derecho de combo, asumiendo cada "adivinar" era independiente. Por ejemplo, la entrada de 123454321 tiene 6 "conjeturas": 1234, 2345, 3454, 4543, 5432, 4321. En este supuesto, la duración prevista de entrada requerida sería de 10.000, es decir, 10^4 permutaciones de 4 dígitos combo.

Sin embargo, para comprobar mi trabajo, he creado una simulación con un objeto de cola y generadores de números aleatorios y corrió los 100 ensayos en cada experimento más de 100 experimentos en Python. En cada experimento, el promedio fue siempre por encima de 10.000 por un margen significativo, que van desde 500 a 2000.

Me pregunto, son las suposiciones que realmente independiente? ¿Cuál es el real valor esperado?

Answer 1

Usted puede acercarse a esta como un proceso de Markov. Usted encontrará que el estado de transición de la tabla depende de la estructura de la solución correcta. Tomar dos extremos, si la solución es $1234$ , a continuación, sus estados son

• Sufijo: $\varepsilon$ va a la $1$ con una probabilidad de $\frac1{10}$ y de vuelta a $\varepsilon$ con una probabilidad de $\frac9{10}$
• Sufijo: $1$ va a la $12$ con una probabilidad de $\frac1{10}$, $\varepsilon$ con una probabilidad de $\frac8{10}$, y de vuelta a $1$ con una probabilidad de $\frac1{10}$.
• Sufijo: $12$ va a la $123$ con una probabilidad de $\frac1{10}$, $\varepsilon$ con una probabilidad de $\frac8{10}$, e $1$ con una probabilidad de $\frac1{10}$.
• Sufijo: $123$ va a la $1234$ con una probabilidad de $\frac1{10}$, $\varepsilon$ con una probabilidad de $\frac8{10}$, e $1$ con una probabilidad de $\frac1{10}$.
• Sufijo: $1234$ es la captura.

OTOH, si la solución es $1111$ , a continuación, sus estados son

• Sufijo: $\varepsilon$ va a la $1$ con una probabilidad de $\frac1{10}$ y de vuelta a $\varepsilon$ con una probabilidad de $\frac9{10}$
• Sufijo: $1$ va a la $11$ con una probabilidad de $\frac1{10}$, e $\varepsilon$ con una probabilidad de $\frac9{10}$
• Sufijo: $11$ va a la $111$ con una probabilidad de $\frac1{10}$, e $\varepsilon$ con una probabilidad de $\frac9{10}$
• Sufijo: $111$ va a la $1111$ con una probabilidad de $\frac1{10}$, e $\varepsilon$ con una probabilidad de $\frac9{10}$
• Sufijo: $1111$ es la captura.

Claramente la duración esperada debe ser más largo que para el segundo caso que el primero: en ambos casos se necesitan cuatro éxitos consecutivos, pero en el primer caso, un fallo de una secuencia puede ser el primer éxito en otra secuencia.

---

A la luz de los comentarios

Tratamos de usar esta línea de razonamiento para calcular el promedio, pero fue demasiado complicado.

aquí es cómo hacerlo sin llegar a ser demasiado complicado. Tome $1234$ como un ejemplo. Deje $E_S$ denotar el número esperado de pasos de sufijo $S$ a la captura de sufijo $1234$. Las transiciones convertir directamente en las ecuaciones simultáneas $$\begin{eqnarray}E_\varepsilon &=& 1 + \frac{1}{10} E_1 + \frac{9}{10} E_\varepsilon \\ E_1 &=& 1 + \frac{1}{10} E_{12} + \frac{8}{10} E_\varepsilon + \frac{1}{10} E_1 \\ E_{12} &=& 1 + \frac{1}{10} E_{123} + \frac{8}{10} E_\varepsilon + \frac{1}{10} E_1 \\ E_{123} &=& 1 + \frac{1}{10} E_{1234} + \frac{8}{10} E_\varepsilon + \frac{1}{10} E_1 \\ E_{1234} &=& 0 \end{eqnarray}$$

Answer 2

Podemos probar el siguiente resultado general:

Dado un código de $C$ de $n$ dígitos, para cada una de las $1\le i\le n-1$, vamos a $b_i$ ser un número que es $1$ si la primera $i$ dígitos de $C$ igual a la última $i$ dígitos de $C$, e $0$ lo contrario. El tiempo de espera para $C$ es $$10^n+\sum_{i=1}^{n-1}b_i10^i.$$

Por ejemplo, cuando se $n=4$:

• El tiempo de espera para los códigos como $aaaa$ es $11,110$.
• El tiempo de espera para los códigos como $abab$ es $10,100$.
• El tiempo de espera para los códigos como $abca$ es $10,010$.
• El tiempo de espera para todo lo demás es $10,000$.

Para probar esto, primero vamos a suponer que $b_i=0$ para todos los $i$, lo que significa que ningún prefijo de $C$ es también un sufijo.

Imagina un casino con un diez dígitos de la rueda de la ruleta. Gira esta rueda una vez por minuto, a excepción de que el casino se apaga una vez que el código de $C$ aparece en el curso de $n$ giros consecutivos. Los jugadores pueden colocar al $\$x$ bet on the outcome of the spin; if they are wrong, they lost $\$x$y si están en lo correcto, ellos ganan $\$9 x$, por lo que la apuesta es justo.

Imagina que cada minuto, una nueva persona entra en el casino. Que primer lugar una $\$1$ bet on the first digit of $C$. If they win, they place a $\$10$ apuesta en el segundo dígito de $C$, y en general las personas que han ganado $k$ veces colocar un $10^k$ apuesta en la $(k+1)^{st}$ dígitos de $C$. Tenga en cuenta que cualquier persona que no lo hace hasta el final de la $C$ perderá exactamente $\$1$; for example, if they make it to digit two then lose, their net winnings are $+9+90-100=-1$. Only a person who makes it all the way through to the end of $C$ will win big, a total of $10^(n-1)$. This can only happen to one person, because we stipulated the casino shuts down once $C$ aparece en orden.

Puesto que todas estas apuestas son justos, el total previsto de las ganancias de todos los jugadores es $0$. Por otro lado, dejando $T$ el número total de tiradas, el real de las ganancias se $10^n-T$, desde el primer $T-1$ personas pierden $1$ y la última persona que gana $10^n-1$. Igualando estas dos, obtenemos que el número esperado de espines es $10^n$.

El pleno resultado es de señalar que, cuando algunas de las $b_i$ son cero, entonces en realidad, hay un par más de los ganadores en el final del juego. Es decir, el $i^{th}$ jugador de la final gana $10^i-1$ , mientras el primer $i$ dígitos de $C$ son iguales a la última $i$ dígitos.

Answer 3

Demasiado tiempo para comentar. He utilizado el siguiente programa para averiguar el promedio de la longitud de la secuencia cuando la clave es finalmente encontrado.

import java.util.Random;

public class Competition {
    public static final String KEY = "1111";
    public static final int TOTAL_RUNS = 200000;

    public static int getSequenceLength(String key) {
        Random rnd = new Random();
        String current = "";
        int count = 0;
        while(!current.equals(key)) {
            // skip a few random numbers
            int skip = rnd.nextInt(10);
            for(int i = 0; i < skip; i++) {
                rnd.nextInt();
            }
            String digit = String.valueOf(rnd.nextInt(10));
            current += digit;
            if(current.length() > key.length()) {
                current = current.substring(1);
            }
            count++;
        }
        return count;
    }

    public static void main(String[] args) {
        long totalLength = 0;
        int totalRuns = 0;
        while(totalRuns < TOTAL_RUNS) { 
            totalLength += getSequenceLength(KEY); 
            totalRuns++;
            if(totalRuns % 1000 == 0) {
                String msg = String.format("Average sequence length after %d runs is %.2f", totalRuns, (totalLength / (double)totalRuns));
                System.out.println(msg);
            }
        }
    }
}

He corrido 200.000 experimentos (secuencias) para cada clave de la prueba. Parecía que Daniel comentario era correcta (se espera secuencia de longitud fue de alrededor de 10.000) para claves como 1234, 1122 o 5556.

Pero para las claves como 3636 o 7474, el promedio de la longitud de la secuencia se mantuvo por encima de 10,100. Tal vez, es sólo un tipo de error que se espera. Pero para las claves como 1111, 2222, 9999... que siempre han obtenido secuencias de longitud superior a 10.000, en algún lugar de 11,000+ gama.

Podría ser que estoy de golpear a algunos "regularidad" en el generador de números aleatorios que se supone es más "random" pero lo dudo. Para hacer la secuencia de dígitos aleatorios como sea posible, el programa recoge una de dígitos al azar a partir de un generador de números aleatorios, entonces se salta un par de números al azar y, a continuación, selecciona el siguiente. Dudo que Java generador de números aleatorios puede ser tan malo para generar una secuencia que siempre es un 10% más de lo esperado.