Hay 53 unicornios corriendo en un orden aleatorio a velocidades únicas. Una bruja malvada lanza un hechizo que enfurece a los unicornios de tal manera que cuando uno atrapa a otro se lo come e imita la velocidad del unicornio comido. ¿Cuántos unicornios esperas sobrevivir?

Answer 1

Hay 53 unicornios corriendo en un orden aleatorio a velocidades únicas. Una bruja malvada lanza un hechizo que enfurece a los unicornios de tal manera que cuando uno atrapa a otro se lo come e imita la velocidad del unicornio comido. ¿Cuántos unicornios esperas sobrevivir?

Siempre generalizar. Entonces supongamos que hay n unicornios.

Eliminé mi respuesta parcial. Aquí hay una nueva respuesta que completa algunos detalles en la brillante respuesta de Dylan Shoemaker.

El resultado no depende de las velocidades y distancias reales. Esto solo afecta cuando se come un unicornio (y cuál se lo come). Para cada par de unicornios, todo lo que necesitamos saber es si el que está adelante es más rápido. Esto quedará claro en el próximo párrafo.

Podemos determinar si un unicornio en particular sobrevive. Imagina que eres uno de los unicornios. Estás a salvo a menos que tú, o cualquier unicornio delante de ti, sea más lento que el que está detrás de ti. Pero los unicornios detrás del que tienes detrás no tienen ningún efecto en tu supervivencia. ¿Por qué? Porque si el que está detrás de ti más rápido, cualquier unicornio que esté delante de él (o uno que se lo haya comido) debe alcanzarlo y consumirlo, y cualquier unicornio sobreviviente en el medio (algunos de ellos pueden haber comido otros). Sin embargo, si el que está detrás de usted es más lento que todos los que están delante (incluido usted), no puede alcanzar a ninguno.

Como señaló Dylan (y como en mi respuesta eliminada) obtendremos el mismo número de sobrevivientes si el unicornio que atrapa desaparece en lugar de comerse a su desafortunado predecesor. El argumento es muy similar, pero el criterio es que sobrevives si y solo si eres más lento que todos los que están delante de ti. De ahora en adelante usaré esta formulación.

Dylan dice que su probabilidad de supervivencia es [matemática] \ frac1k [/ matemática] donde [matemática] k [/ matemática] es su posición espacial. (Eso es lo que me perdí en mi respuesta.) ¿Por qué? Es igualmente probable que su velocidad esté en cualquier lugar de la lista de velocidades de los unicornios en las posiciones [matemática] k-1 [/ matemática] delante de usted. Hay k posibilidades igualmente probables (incluso en la parte delantera o trasera).

(Esto conduce a un algoritmo de simulación eficiente. Simplemente hacemos una pasada por la lista de velocidades haciendo un seguimiento de los más pequeños hasta ahora y eliminando y contando cada uno que es mayor que el mínimo).

Finalmente, si, para cada unicornio, definimos una variable aleatoria que es [matemática] 1 [/ matemática] para supervivencia y [matemática] 0 [/ matemática] de lo contrario, el valor esperado de esto es la probabilidad de supervivencia. Y el valor esperado de la suma es la suma de los valores esperados (independientemente del hecho de que las variables no son independientes).

Esto lleva a la respuesta de Dylan [matemática] E = 1 + \ frac12 + \ frac13 +… + \ frac1 {53} [/ matemática].

¿Podemos también obtener la varianza? El valor esperado del cuadrado del número de sobrevivientes es la suma de los cuadrados más el doble de la suma de todos los productos cruzados. Entonces, necesitamos la probabilidad de supervivencia conjunta de cada par de unicornios. Si está en la posición [matemáticas] i [/ matemáticas] y yo estoy detrás de usted en la posición [matemáticas] j [/ matemáticas], entonces su probabilidad de supervivencia es [matemáticas] \ frac1i [/ matemáticas] y depende de su supervivencia, la mía es [matemática] \ frac1 {j-i + 1} [/ matemática]. Entonces, la probabilidad de supervivencia conjunta es [matemática] \ frac1 {i (j-i + 1)} [/ matemática].

Podemos escribir todas estas probabilidades como una matriz simétrica, e incluir el término [matemáticas] j = i [/ matemáticas] en el producto cruzado da la diagonal.

La suma de todos estos elementos es la suma esperada de cuadrados. Solo necesitamos restar el cuadrado del valor esperado. Este es un resultado estándar: [matemáticas] E [(X- \ mu) ^ 2] = E [X ^ 2] – \ mu ^ 2 [/ matemáticas]. Y si [matemáticas] X = \ sum_ {i = 1} ^ n {X_i} [/ matemáticas] entonces [matemáticas] E [X ^ 2] = \ sum_ {i = 1} ^ n {E [X_i ^ 2] } + 2 \ sum_ {i = 1} ^ {n-1} {[\ sum_ {j = 2} ^ n {E [X_iX_j]}} [/ math] donde [math] X_i = 1 [/ math] if el [math] i [/ math] th unicornio es más lento que todo esto delante de él y [math] 0 [/ math] de lo contrario.

Al usar la oficina abierta, obtuve una desviación estándar de [matemáticas] 3.6460 [/ matemáticas] y una media de [matemáticas] 4.5569 [/ matemáticas], por lo que la distribución es bastante variable. La desviación estándar parece ser el doble de la simulación y aún no tengo una explicación para esto. Sospecho que podría ser porque la distribución tiene una cola muy larga. Quizás se necesita una muestra muy grande para obtener una buena aproximación de la varianza. Pruebe 1000000 en lugar de 10000.

Answer 2

Un genio de las matemáticas probablemente resolvería esto en 10 segundos, pero como era un tipo de computadora, decidí ir con fuerza bruta.

Así que aquí está mi pensamiento:

Se supone que las distancias entre los unicornios son cero, por lo que también asumo que el unicornio más rápido siempre será el primero en engullir al que está delante de él.

Si el unicornio más rápido también es el que encabeza la manada, es un hogar libre y vive feliz (¿enfurecido?) Para siempre.

Escribí un script simple de Python que simula esto y ejecuté 10,000 simulaciones.

importar al azar
num_survivors = []
para i en rango (10000):
velocidades = lista (rango (1,54))
random.shuffle (velocidades)
sobrevivientes = []
mientras que las velocidades:
índice_máximo = speed.index (máx. (velocidades))
si el índice más rápido + 1 == len (velocidades):
survivors.append (speed.pop (rapid_index)) # Home gratis
más:
velocidades.pop (índice_máximo) # Gobble gobble
num_survivors.append (len (sobrevivientes))
print (sum (num_survivors) / len (num_survivors)) # Expectativa

Salida: 4.5498

Aquí está la distribución del número o sobrevivientes:

Answer 3

Comencemos mirando un caso más simple. Si observamos los últimos 2 unicornios exclusivamente, hay un 50% de posibilidades de que solo el último unicornio en el emparejamiento sobreviva (si el primer unicornio es más lento que el último), y un 50% de posibilidades de que ambos unicornios sobrevivan (si el último unicornio es más lento que el primero). También tenga en cuenta que si un unicornio alcanza y se come al que está delante de él, se hereda la velocidad más lenta y es como si el unicornio más lento sobreviviera y no el más rápido (por lo que podemos fingir que el unicornio más rápido muere por completo si se pone al día a un unicornio más lento).

A partir de este pequeño caso, podemos razonar que un unicornio sobrevivirá si y solo si es más lento que todos los demás unicornios frente a él. Por ejemplo, supongamos que tenemos un paquete de k unicornios y los numeramos en orden de 1 a k según su posición inicial en la línea (1 corresponde al primer unicornio en línea yk corresponde al último). El unicornio en la posición k sobrevivirá si y solo si tiene la velocidad mínima de cualquiera de los k unicornios (es decir, más lento que todos los unicornios k-1 frente a él). La probabilidad de que el unicornio en la posición k tenga la velocidad mínima de un paquete aleatorio de k unicornios es [matemática] \ frac {1} {k} [/ matemática] ya que el paquete tendrá una velocidad mínima única de k unicornios totales .

Por lo tanto, para cada unicornio en línea, podemos decir que el unicornio sobrevivirá con probabilidad [math] \ frac {1} {i} [/ math] donde i es la posición del unicornio en línea como se definió anteriormente. La definición de expectativa matemática dicta que si queremos encontrar el número esperado de sobrevivientes, podemos sumar la probabilidad de supervivencia para cada unicornio individual en la línea. Esto nos da [matemáticas] \ sum_ {i = 1} ^ {53} \ frac {1} {i} \ aproximadamente 4.5569 [/ matemáticas] sobrevivientes, lo que corresponde con la aproximación de Håkon Hapnes Strand usando Python.

Answer 4

A2A : hay 53 unicornios corriendo en orden aleatorio a velocidades únicas. Una bruja malvada lanza un hechizo que enfurece a los unicornios de tal manera que cuando uno atrapa a otro se lo come e imita la velocidad del unicornio comido. ¿Cuántos unicornios esperas sobrevivir?

Con 10 millones de iteraciones, el número promedio de unicornios supervivientes fue de 4.557 con una desviación estándar de 1.712.

$ python
>>> de importación aleatoria aleatoria
>>> def sim ():
… Velocidad1, n = aleatorio (), 1
… Para _ en xrange (52):
… velocidad2 = aleatorio ()
… si velocidad2 … Velocidad1, n = velocidad2, n + 1
… volver n
…
>>> de matemáticas import sqrt
>>> def ShowDist (nSim, nLo, nHi, nLoops = 10000): # 2017-12-21
… #SBn: muestra la distribución de la simulación dentro del rango especificado
… D, s1, s2, fLoops = [0] * (nHi-nLo + 1), 0, 0, float (nLoops)
… para _ en xrange (nLoops):
… DVal = nSim ()
… S1 + = dVal; s2 + = dVal * dVal
… Si nLo <= dVal <= nHi:
… D [dVal-nLo] + = 1
… para i en xrange (len (D)):
… D [i] / = fLoops
… Avg = s1 / fLoops
… Std = sqrt ((s2 + avg * avg * nLoops-2 * avg * s1) / fLoops)
… imprima ‘Promedio: {}, SDv: {}’. Formato (promedio, estándar)
… para i en xrange (len (D)):
… Imprima el formato ‘{}, {}’. (I + nLo, D [i] * 100.0)
…
>>> ShowDist (sim, 1, 10, 10000000)
Promedio: 4.5569771, SDv: 1.7115345191
1, 1.88886
2, 8.55498
3, 17.88337
4, 23.20485
5, 21.08504
6, 14.44406
7, 7.7841
8, 3.40898
9, 1.23954
10, 0.37971

Nota : La función general ShowDist (realmente escrita por los suyos) se puede usar para mostrar muchas simulaciones diferentes. Cualquiera en Quora es libre de usarlo como está; sin embargo, a menos que proporcionen un enlace que dé crédito, es plagio.