Este grupo de especialistas pasados muchos días de trabajo y de recopilar de información, encontramos la respuesta, deseamos que te sea útil en tu proyecto.
Solución:
No, este no es un buen enfoque: la mitad de las veces, el primer elemento será $ 50 $ o más, lo cual es demasiado a menudo. Esencialmente, las probabilidades de que el primer elemento sea $ 100 $ no deberían ser las mismas que las probabilidades de que el primer elemento sea $ 10 $. Solo hay una forma de $ a = 100 $, pero hay muchas formas de $ a = 10 $.
El número de tales sumas $ 100 = a + b + c + d $ con $ a, b, c, d geq 0 $ enteros, es: $ binom 100 + 3 3 $. Si su algoritmo no elige al azar entre $ 1 $ y un múltiplo de $ 103 $, no puede obtener una probabilidad uniforme.
Un enfoque ideal. Elija un número $ x_1 $ de $ 1 $ a $ 103 $. Luego, elija un número diferente $ x_2 neq x_1 $ de $ 1 $ a $ 103 $, luego elija un tercer número $ x_3 neq x_1, x_2 $ de $ 1 $ a $ 103 $.
Luego ordene estos valores, de modo que $ x_1
Genere cuatro números aleatorios entre $ 0 $ y $ 1 $
Suma estos cuatro números; luego divida cada uno de los cuatro números por la suma, multiplique por $ 100 $ y redondee al número entero más cercano.
Compruebe que los cuatro números enteros sumen $ 100 $ (lo harán, dos tercios del tiempo). Si no lo hacen (errores de redondeo), inténtelo de nuevo …
Su pregunta menciona un algoritmo ineficiente que genera cuatro números independientes y distribuidos uniformemente entre los números enteros de 0 a 100 y se repite hasta que su suma sea 100. Asumiré que está satisfecho con la distribución generada por ese algoritmo, pero no está satisfecho con la rendimiento.
Antes de ver cómo producir la distribución de manera más eficiente, primero hay que entender cómo se ve la distribución.
Por construcción, es fácil ver que cada $ a $, $ b $, $ c $ y $ d $ están distribuidos de forma idéntica. También es fácil ver que no son independientes debido a que su suma es constante. Lo que ya sabemos sobre su distribución es que tiene un valor mínimo de 0, un valor máximo de 100 y un valor medio de 25. El promedio se deriva del hecho de que su suma debe ser 100 en promedio.
Esto descarta una distribución uniforme de los números individuales (y de hecho descarta toda distribución simétrica). Esto significa que su algoritmo más eficiente, que genera $ a $ uniformemente, producirá una distribución diferente.
Hacia un algoritmo eficiente
Si definimos $ X = a + b $ y preguntamos cómo es la distribución de $ X $, encontraremos algo interesante. La distribución claramente no depende de qué par de los cuatro números sumamos. Entonces, los seis pares posibles están distribuidos de manera idéntica, pero no independientes. Esta distribución tiene un mínimo de 0, un máximo de 100 y un promedio de 50. Y la distribución tiene que ser simétrica porque $ X $ y $ 100-X $ se distribuyen de forma idéntica.
No es inmediatamente obvio si la distribución de $ X $ es uniforme entre los números enteros de 0 a 100. Sin embargo, si la distribución de $ X $ se puede generar de manera eficiente, entonces la distribución de los cuatro números se puede generar de manera eficiente de la siguiente manera:
- Generar $ X $
- Elija $ a $ uniformemente aleatorio en el rango de $ 0 $ a $ X $
- Sea $ b: = Xa $
- Elija $ c $ uniformemente al azar en el rango de $ 0 $ a $ 100-X $
- Sea $ d: = 100-Xb $
La distribución de X
El algoritmo original produciría $ X $ como la suma de dos números aleatorios uniformemente en el rango de $ 0 $ a $ 100 $, pero descartaría cualquier resultado en el que la suma total fuera diferente de $ 100 $.
Un algoritmo diferente podría generar $ X $ y $ Y $ de acuerdo con esta distribución y descartar el resultado si $ X + Y neq 100 $. Esto es útil porque la generación de $ X $ y $ Y $ se puede simplificar.
Si $ X $ es mayor que 100, se puede descartar inmediatamente. Analizamos fácilmente cuál es la nueva distribución antes de verificar la suma de $ X $ y $ Y $. La probabilidad inicial de un resultado $ x in [0;100]$ sería $ frac 1 + x 10000 $, pero cuando descartamos valores mayores que 100, la probabilidad será $ frac 1 + x 5050 $.
La probabilidad de generar inmediatamente $ X = x $ y $ Y = 100-x $ se puede calcular como $ frac 1 + x 5050 cdot frac 1+ (100-x) 5050 = frac (1 + x) (101-x) 5050 ^ 2 $ La probabilidad de $ P (X = x wedge Y = 100-x) $ puede calcularse simplemente escalando el denominador de manera que la suma será $ 1 $
En este punto, está claro que $ X $ no se distribuye uniformemente. Pero también nos da una forma de construir $ X $ directamente.
Para generar la distribución de $ X $ directamente, necesitamos una fórmula para $ P (X leq x) $. Esta fórmula será:
$$ P (X leq x) = frac Sigma_ i = 0 ^ x (1 + x) (101-x) k = frac -2x ^ 3 + 297x ^ 2 + 905x + 606 6k $$
Como sabemos que $ P (X leq 100) = 1 $, podemos deducir que $ k = 176851 $.
Con esto el algoritmo se convierte en:
- Elija $ r $ uniformemente aleatorio de los enteros $[0;176850]PS
- Tome el menor $ x $ tal que $ Sigma_ i = 0 ^ x (1 + x) (101-x) geq r $
- Elija $ a $ uniformemente aleatorio en el rango $ 0 $ a $ x $
- Sea $ b: = xa $
- Elija $ c $ uniformemente al azar en el rango de $ 0 $ a $ 100-x $
- Sea $ d: = 100-xb $
Te mostramos las reseñas y valoraciones de los usuarios
No se te olvide comunicar este escrito si lograste el éxito.