$n$ errores moviéndose en una línea

Question

Tengo una línea de $n$ bugs, donde no $2$ bugs tienen el mismo tamaño. Todos se mueven en la misma dirección. Si el error más grande está detrás de un error más pequeño, se va a comer el error más pequeño. ¿Cuál es la expectativa de que el número de errores a la izquierda después de un largo tiempo suficiente?

No estoy seguro de cómo acercarse a este. De $n=1, 2, 3, 4$ supongo que la respuesta podría ser$$ 2- \frac{1}{n!} $$, pero no estoy seguro de si esto es correcto, y cómo se derivan de este.

Por ejemplo, cuando se $n=3$, si mis errores son $a,b,c$ donde $a>b>c$, suponiendo que se mueve de izquierda a derecha, a continuación, tengo el siguiente $6$ de las situaciones.

• $a,b,c$ - 1 a la izquierda
• $a,c,b$ - 1 a la izquierda
• $b,c,a$ - 2 a la izquierda
• $b,a,c$ - 2 a la izquierda
• $c,a,b$ - 2 a la izquierda
• $c,b,a$ - 3 a la izquierda

a continuación, la expectativa es 1*2/6+ 2*3/6 + 3*1/6 = 11/6 = 2-1/3!

Answer 1

Divertido pregunta!

El cálculo para los tres primeros de las expectativas es correcta, pero su adivinado fórmula no es. Aquí es un enfoque posible. Será el punto de que a algunos frescos recursos en línea a lo largo del camino.

Permítanme llamar al número esperado que después de $e(n)$. Deje $B$ ser el big fat tipo que se come a todo el mundo en frente de él. Entonces la probabilidad de que $B$ es en cualquier lugar de la secuencia es $1/n$, y si él está en su lugar $i$, entonces el número de supervivientes en sí mismo es más lo que sucede detrás de él, que es sólo una pregunta acerca de las permutaciones de los restantes $i-1$ errores. Así, se obtiene la fórmula recursiva $$ e(n) = \frac{1}{n}\sum_{i=0}^{n-1}(1+e(i)) = 1+ \frac{1}{n}\sum_{i=1}^{n-1}e(i). $$

Editar: Ver lulu y Cristiano Blatter las respuestas para la solución a esta recursividad! Se puede demostrar fácilmente que esa es la solución utilizando la serie de la identidad entre armónica de los números $$ \sum_{k=1}^n H_k = (n+1)(H_{n+1}-1). $$

Here is MAGMA code, which you can paste in the online calculator to compute this sequence:

function prob(n)
if n lt 2 then return n; end if;
return 1/n*&+[1+prob(i): i in [0..n-1]];
end function;

Now you can say

[prob(i): i in [1..10]];

and get the sequence

$$ 1, 3/2, 11/6, 25/12, 137/60, 49/20, 363/140, 761/280, 7129/2520, 7381/2520,... $$ Si se multiplica esto por $n!$, se obtiene un número entero secuencia:

$$ 1, 3, 11, 50, 274, 1764, 13068, 109584, 1026576, 10628640,... $$ La enciclopedia de secuencias de enteros reconoce esto como secuencia A000254, y le da varias interpretaciones. Es por ejemplo el número total de ciclos en todas las permutaciones de $\{1,\ldots,n\}$, y es fácil demostrar (ejercicio!) que eso es lo que debería ser para su rompecabezas.

Answer 2

El uso de la Linealidad:

(suponga que no hay dos hormigas tienen el mismo tamaño)

Deje $X_i$ ser la variable de indicador para la $i^{th}$ ant. Por lo tanto $X_i=1$ si $i^{th}$ ant sobrevive a este proceso, y $X_i=0$ lo contrario.

Desde el más grande de la primera $i$ hormigas tiene la misma probabilidad de estar en cualquiera de los $i$ ranuras vemos que $$E[X_i]=\frac 1i$$

De ello se deduce que la respuesta es $$E=E\left[ \sum X_i\right]=\sum E[X_i]=\sum_{i=1}^n\frac 1{i}$$

Por lo tanto la respuesta es solo el $n^{th}$ Número Armónico.

Answer 3

Aquí hay otra forma de ver que la respuesta es el número armónico$H_n=1+{1\over2}+{1\over3}+\cdots+{1\over n}$.

Construya la alineación de errores comenzando con los más grandes y terminando con los más pequeños al encajar cada error en algún lugar de la alineación existente. Cada nuevo error sobrevive si y solo si ingresa al final de la línea. Entonces el$k$% error sobrevive con la probabilidad$1/k$, existiendo$k$ posiciones para colocarlo. (Tenga en cuenta que el número total de alineaciones es$1\times2\times3\times\cdots\times n=n!$).

Answer 4

Denote por$E(n)$ el número esperado de hormigas supervivientes. Si la hormiga más pequeña es la última en la línea, sobrevivirá. Si no, ciertamente se comerá y no tendrá efecto en la cantidad de hormigas supervivientes. Se deduce que$$E(n)={1\over n}\bigl(1+E(n-1)\bigr)+{n-1\over n}E(n-1)={1\over n}+E(n-1)\ .$ $ Esto lleva a$$E(n)=H(n):=\sum_{k=1}^n{1\over k}\ .$ $

Answer 5

Tenga en cuenta que el error más grande se comerá todo lo que está delante de él. Por lo tanto, si el más grande está en la posición$n-k$ - th, se comerá todos los errores que se encuentren y dejará atrás$k$ errores. Estos$n-k$% bugs se comerán entre sí exactamente de la misma manera, como en la situación, donde solo hay$n-k$ bugs y dejan el más grande.

El error más grande se puede colocar en cada posición con la probabilidad$\frac{1}{n}$, por lo que el valor esperado de los errores restantes es:

ps