Mi capítulo local de ACM otorga premios a las personas que vienen a las reuniones. Sin embargo, tienes una mayor probabilidad de ganar si resuelves el rompecabezas de programación (pero yo siempre resuelvo ese rompecabezas). Por lo tanto, algunas personas tienen 1 entrada, mientras que otras tienen 2. ¡Pero espera! La forma en que funciona el programa de rifa no es agregando otra entrada cuando alguien resuelve el rompecabezas. En cambio, realiza un seguimiento del número de "vidas" que tiene una persona, decrementando que si esa persona es elegida en cada pasada de su algoritmo de muestreo aleatorio. Entonces funciona así:
Doorknob: 1. xnor: 2. Justin: 2. Alex: 1. Dennis: 2.
Luego, el programa elige aleatoriamente uno de [Doorknob, xnor, Justin, Alex, Dennis]
, disminuye el número (digamos que elige Justin
):
Doorknob: 1. xnor: 2. Justin: 1. Alex: 1. Dennis: 2.
Y se repite. Si el número de "vidas" de alguien va a 0
(volvamos a elegir Justin
), se eliminan de la lista:
Doorknob: 1. xnor: 2. Alex: 1. Dennis: 2.
Esto continúa hasta que quede una persona; esa persona es la ganadora.
Ahora la verdadera pregunta es, ¿cuál era la probabilidad de que hubiera ganado?
Se le darán dos entradas:
n
. Este es el número de personas que participaron en el desafío.k
. Este es el número de personas (de esasn
) que tienen 2 vidas. Este número siempre te incluye a ti.
Entonces, si tuviera una función p
y llamara p(10, 5)
, esa sería la probabilidad de ganar el premio donde hay un total de 10 personas, 5 de las cuales solo tienen 1 vida, mientras que 5 (incluido usted) tienen 2 vidas.
Se espera que muestre la probabilidad de ganar, ya sea exactamente, o como un decimal. En cualquier caso, las respuestas deben ser precisas hasta el 4 ° lugar decimal después del punto decimal. Si redondeas a ese dígito o no, depende de ti.
Su solución puede ser una solución aleatorizado que emite la respuesta a la 4 ª posición decimal con alta probabilidad . Puede suponer que el RNG incorporado que utiliza es verdaderamente aleatorio y debe generar la respuesta correcta con al menos un 90% de probabilidad.
Además, su código solo necesita funcionar n, k <= 1000
, aunque proporcioné casos de prueba más grandes que eso para aquellos curiosos.
Casos de prueba
Nota: algunos de estos son fórmulas generales.
n, k | output
----------+---------
1, 1 | 1
2, 2 | 0.5
2, 1 | 0.75
3, 1 | 11/18 = 0.611111111
1000, 1 | 0.007485470860550352
4, 3 | 0.3052662037037037
k, k | 1/k
n, 1 | (EulerGamma + PolyGamma[1 + n])/n (* Mathematica code *)
| (γ + ψ(1 + n))/n
10, 6 | 0.14424629234373537
300, 100 | 0.007871966408910648
500, 200 | 0.004218184180294532
1000, 500 | 0.0018008560286627948
---------------------------------- Extra (not needed to be a valid answer)
5000, 601 | 0.0009518052922680399
5000, 901 | 0.0007632938197806958
Para otras verificaciones, tome p(n, 1) * n
lo siguiente:
n | output
------+---------
1 | 1
2 | 1.5
3 | 1.8333333333333335
10 | 2.928968253968254
100 | 5.1873775176396215
-------------------------- Extra (not needed to be a valid answer)
100000| 12.090146129863305
fuente
k
está desactivada por uno)Respuestas:
MATL , 42 bytes
Esto utiliza un enfoque probabilístico (Monte Carlo). El experimento se ejecuta una gran cantidad de veces, a partir de las cuales se estima la probabilidad. El número de realizaciones se selecciona para garantizar que el resultado sea correcto hasta el cuarto decimal con una probabilidad de al menos 90%. Sin embargo, esto lleva mucho tiempo y mucha memoria. En el siguiente enlace, el número de realizaciones se ha reducido en un factor de 10 6 para que el programa finalice en un tiempo razonable; y solo se garantiza que el primer decimal sea exacto con al menos un 90% de probabilidad.
EDITAR (29 de julio de 2016): debido a cambios en el idioma,
6L
debe ser reemplazado por3L
. El siguiente enlace incorpora esa modificación.Pruébalo en línea!
Antecedentes
Supongamos que p denota la probabilidad de ser calculada. El experimento descrito en el desafío se ejecutará varias veces n . Cada vez, gana el premio (" éxito ") o no. Sea N el número de éxitos. La probabilidad deseada se puede estimar a partir de N y n . Cuanto mayor sea n , más precisa será la estimación. La pregunta clave es cómo seleccionar n para cumplir con la precisión deseada, es decir, para asegurar que al menos el 90% de las veces el error sea menor que 10 −4 .
Los métodos de Monte Carlo pueden ser
Entre la segunda categoría, un método común utilizado es fijar N (número deseado de éxitos) y seguir simulando hasta que se logre ese número de éxitos . Por lo tanto, n es aleatorio. Esta técnica, llamada muestreo binomial inverso o Montecarlo binomial negativo , tiene la ventaja de que la precisión del estimador puede limitarse. Por esta razón, se usará aquí.
Específicamente, con Montecarlo negativo-binomial x = ( N −1) / ( n −1) es un estimador insesgado de p ; y la probabilidad de que x se desvíe de p en más de una relación dada puede tener límites superiores. De acuerdo con la ecuación (1) en este documento (tenga en cuenta también que se cumplen las condiciones (2)), tomar N = 2.75 · 10 8 o mayor asegura que p / x pertenece al intervalo [1.0001, 0.9999] con al menos 90% probabilidad. En particular, esto implica que x es correcto hasta el cuarto decimal con al menos un 90% de probabilidad, según se desee.
Código explicado
El código usa N =
3e8
para guardar un byte. Tenga en cuenta que realizar muchas simulaciones llevaría mucho tiempo. El código en el enlace usa N =300
, que se ejecuta en un período de tiempo más razonable (menos de 1 minuto en el compilador en línea para los primeros casos de prueba); pero esto solo asegura que el primer decimal sea correcto con una probabilidad de al menos 90%.fuente
Pyth, 34 bytes
Banco de pruebas
Define una función recursiva memorizada determinista que
g
toma n , k como argumentos.g 1000 500
regresa0.0018008560286627952
en aproximadamente 18 segundos (no incluido en el conjunto de pruebas anterior porque agota el tiempo de espera del intérprete en línea).Una traducción aproximada de Python 3 sería
fuente
JavaScript (ES6), 65 bytes
Sin embargo, no lo intentes con los números grandes; incluso f (30, 10) lleva una cantidad de tiempo notable.
fuente