Problema de combinatoria de un concurso.

Question

Los enteros $1, 2, 3, 4, 5, 6, 7, 8, 9, 10$ están escritos en una pizarra. Cada día, un profesor elige uno de los enteros uniformemente al azar y se disminuye por $1$. Sea X el valor esperado del número de días que deben transcurrir antes de que ya no hay enteros positivos en el tablero. Estimación de $X$

La respuesta es dada a $120.7528$.

Lo resolví de la siguiente manera y me pregunto si es a la derecha.

Deje $X_i$ ser una variable aleatoria que denota el número de ensayos requeridos para golpear a 0. El discreto de valores que puede tomar son: $(1,2,.. i,0)$ donde puedo club todos los que no son enteros positivos en los ensayos a 0.

Para $X_1$, el espacio muestral es ${0,1}$. En realidad, debe estar representado por la distribución hipergeométrica con el maestro llamativo por cada entero por 1. Como una aproximación como el número de ensayos puede ser infinito, distribución geométrica se utiliza. Por lo tanto la probabilidad de éxito de $X_1$ es $\frac{1}{10}.\frac{1}{2} = \frac{1}{20}$. La probabilidad de fallo es $1-p_{success} = \frac{19}{20}$.

Similarmente para $X_2$, el espacio muestral es $(0,1,2)$ y la probabilidad de éxito de $X_2$ es $\frac{1}{10}.\frac{2}{3} = \frac{2}{30}$. y que el fracaso es $= \frac{28}{30}$.

Y así, por $X_{10}$, el espacio muestral es $(0,1,2,3,..,10)$ y la probabilidad de éxito de $X_{10}$ es $\frac{1}{10}.\frac{10}{11} = \frac{10}{110}$ y que el fracaso es $= \frac{100}{110}$.

Vamos a definir el $X$ como el número total de ensayos requeridos para el maestro para derribar todos los enteros a 0. A continuación, $X = X_1+X_2+\cdots+X_{10}$

$E(X) = E(X_1+X_2+\cdots+X_{10}) = E(X_1)+E(X_2)+\cdots+E(X_{10})$

$E(X_i) = \frac{1-p_i}{p_i}$

Hice el cálculo y me tocó muy de cerca la respuesta de $119.2897$ que es $1$ menos que el concurso de respuesta $120.7528$.

Quiero saber si el enfoque es correcto?. No hay ninguna solución, así que no sé cuál es la estrategia que han tomado.

Answer 1

La siguiente solución confirma la respuesta de $120.7528$, pero se puede utilizar más de la maquinaria que es apropiado para un concurso.

Una forma alternativa de ver el problema es que tenemos diez papeleras y se lanza una sucesión de bolas en los recipientes, uno a la vez, con cada bin elegido de forma independiente y con la misma probabilidad. Deje $T$ el número de balones lanzados cuando primero tenemos $n$ bolas en bin $n$ para todos los $n=1,2,3,\dots,10$. Queremos encontrar el valor esperado de $T$.

Para este fin, vamos a $a_n$ el número de secuencias de bin selecciones de satisfacer la restricción de que bin $n$ contiene al menos $n$ bolas para todas las $n$. Deje $f(x)$ ser la exponencial de generación de función (EGF) de $a_n$. El FEAG de la secuencia de las bolas que caen en una sola bandeja $n$, ya que el reciclaje debe contener, al menos, $n$ bolas, es $$\frac{1}{n!} x^n + \frac{1}{(n+1)!}x^{n+1} + \frac{1}{(n+2)!}x^{n+2} + \dots = e^x - \sum_{i=0}^n \frac{1}{i!} x^i$$ La secuencia de todas las bolas, es el producto con el sello de las secuencias para cada uno de los contenedores, por lo que $$f(x) = \prod_{n=0}^9 \left( e^x - \sum_{i=0}^n \frac{1}{i!} x^i \right)$$ Este EGF cuenta el aceptable secuencias de bola de lanzamientos. Lo que realmente nos interesa es el asociado probabilidades; pero dado que el FEAG del número aceptable de secuencias, el EGF de los asociados probabilidades, en el que cada bola es lanzada dentro de reciclaje $n$ con una probabilidad de $1/10$, es simplemente $f(x/10)$. I. e., si $p_n$ es la probabilidad de que una secuencia de $n$ tiros satisface el relleno requisito para todos los recipientes, a continuación, el EGF de $p_n$ es $f(x/10)$.

Si queremos saber la probabilidad de que una secuencia ¿ no satisfacer el relleno de restricción, que la probabilidad es $q_n = 1-p_n$, que tiene el EGF $g(x) = e^x-f(x/10)$. Otra manera de ver la $q_n$ es que es la probabilidad de que $T >n $, donde $T$ es el número de balones lanzados cuando el relleno requisito de que los contenedores se reunieron por primera vez. Así $$E(T) = \sum_{n=0}^{\infty} P(T>n) = \sum_{n=0}^{\infty} q_n$$ Podemos utilizar el siguiente truco para extraer esta infinita suma del FEAG de $q_n$. Porque $$\int_0^{\infty} x^n e^{-x} \;dx = n!$$ tenemos $$\sum_{n=0}^{\infty} q_n = \int_0^{\infty} g(x) \; e^{-x} \; dx $$

La fórmula para $g(x)$ es bastante complicado, por lo que la posibilidad de calcular esta integral por la mano es difícil de entender, pero una integración numérica usando Mathematica es fácil, con el resultado de $$E(T) = 120.75280$$

Answer 2

No es una respuesta, pero es demasiado largo para un comentario:

Monte Carlo muestra que la respuesta 120.7528 es correcta:

 import java.util.HashMap;
import java.util.Map;
import java.util.Random;

public class SolutionCounter {

    public static int numDays(int maxNum) {
        Map<Integer, Integer> values = new HashMap<>();
        for(int i = 1; i <= maxNum; i++) {
            values.put(i, i);
        }
        Random rnd = new Random();
        int count = 0;
        while(values.size() > 0) {
            int pos = rnd.nextInt(10) + 1;
            if(values.containsKey(pos)) {
                int value = values.get(pos) - 1;
                if(value == 0) {
                    values.remove(pos);
                }
                else {
                    values.put(pos, value);                 
                }
            }
            count++;
        }
        return count;
    }

    public static void main(String[] args) {
        int runs = 0;
        long total = 0;
        while(true) {
            runs++;
            total += numDays(10);
            if(runs % 1000000 == 0) {
                String msg = String.format("Average after %d runs: %.6f", runs, (total / (double) runs));
                System.out.println(msg);
            }
        }
    }
}
 

Resultados después de millones de carreras:

 Average after 1000000 runs: 120.732686
Average after 2000000 runs: 120.758270
Average after 3000000 runs: 120.749915
Average after 4000000 runs: 120.757830
Average after 5000000 runs: 120.759283
Average after 6000000 runs: 120.756646
Average after 7000000 runs: 120.755833
Average after 8000000 runs: 120.754364
Average after 9000000 runs: 120.754940
Average after 10000000 runs: 120.752258
Average after 11000000 runs: 120.748632
Average after 12000000 runs: 120.751920
Average after 13000000 runs: 120.753491
Average after 14000000 runs: 120.751542
Average after 15000000 runs: 120.751762
Average after 16000000 runs: 120.751637
Average after 17000000 runs: 120.753422
Average after 18000000 runs: 120.752132
Average after 19000000 runs: 120.753649
Average after 20000000 runs: 120.755102
Average after 21000000 runs: 120.754852
Average after 22000000 runs: 120.755027
Average after 23000000 runs: 120.755376
Average after 24000000 runs: 120.755810
 

Sin embargo, todavía estoy tratando de entender qué está mal con tu método.