Método de generación de números aleatorios que suman 100 - ¿es realmente aleatorio?

Question

Estoy escribiendo un programa de computadora que implica generar 4 números aleatorios, a, b, c y d, cuya suma debería ser igual a 100.

Aquí está el método que primero ideé para lograr ese objetivo, en pseudocódigo:

Genera un número aleatorio fuera de 100. (Digamos que genera 16).
Asigna este valor como el primer número, entonces a = 16.
Resta a de 100, lo que da 84.

Genera un número aleatorio fuera de 84. (Digamos que genera 21).
Asigna este valor como el segundo número, entonces b = 21.
Resta b de 84, lo que da 63.

Genera un número aleatorio fuera de 63. (Digamos que genera 40).
Asigna este valor como el tercer número, entonces c = 40.
Resta c de 63, lo que da 23.

Asigna el resto como el cuarto número, entonces d = 23.

Sin embargo, por alguna razón tengo una sensación extraña acerca de este método. ¿Realmente estoy generando cuatro números aleatorios que suman 100 aquí? ¿Sería equivalente a mí generar cuatro números aleatorios fuera de 100 una y otra vez, y solo aceptar cuando la suma es 100? ¿O estoy creando algún tipo de sesgo al elegir un número aleatorio fuera de 100, y luego un número aleatorio fuera del resto, y así sucesivamente? Gracias.

Answer 1

No, esta no es una buena aproximación - la mitad del tiempo, el primer elemento será $50$ o más, lo cual es demasiado común. Básicamente, las probabilidades de que el primer elemento sea $100$ no deberían ser iguales a las probabilidades de que el primer elemento sea $10$. Solo hay una forma para $a=100$, pero hay muchas formas para $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 tu algoritmo no elige aleatoriamente de $1$ a algún múltiplo de $103$, no puedes obtener una probabilidad uniforme.

Un enfoque ideal. Vamos a escoger un número $x_1$ del $1$ al $103$. Luego escoge un número diferente $x_2\neq x_1$ del $1$ al $103$, luego escoge un tercer número $x_3\neq x_1,x_2$ del $1$ al $103$.

Luego ordena estos valores, de manera que $x_1

Answer 2

Generar cuatro números aleatorios entre $0$ y $1$

Sumar estos cuatro números; luego dividir cada uno de los cuatro números por la suma, multiplicar por $100$ y redondear al entero más cercano.

Verificar que los cuatro enteros suman $100$ (lo harán, dos tercios del tiempo). Si no lo hacen (errores de redondeo), intentar de nuevo...

Answer 3

Su pregunta menciona un algoritmo ineficiente que genera cuatro números independientes y uniformemente distribuidos entre los enteros de 0 a 100, y se repite hasta que su suma sea 100. Voy a asumir que está satisfecho con la distribución generada por ese algoritmo, pero no está satisfecho con el rendimiento.

Antes de analizar cómo producir la distribución de manera más eficiente, primero hay que entender cómo es la distribución.

Por construcción, es fácil ver que cada uno de $a$, $b$, $c$ y $d$ están distribuidos de manera 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 promedio de 25. El promedio se sigue del hecho de que su suma tiene que ser 100 en promedio.

Esto descarta una distribución uniforme de los números individuales (y de hecho descarta cualquier 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 son distribuidos de manera idéntica, pero no son 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$ están distribuidos de manera idéntica.

No es inmediatamente obvio si la distribución de $X” es uniforme en los enteros de 0 a 100. Sin embargo, si la distribución de$X” se puede generar eficientemente, entonces la distribución de los cuatro números se puede generar eficientemente de la siguiente manera:

• Genera $X$
• Elige $a$ de manera uniforme al azar en el rango $0$ a $X”
• Sea $b := X-a$
• Elige $c$ de manera uniforme al azar en el rango $0” a$100-X$
• Sea $d := 100-X-b’/li>

La distribución de $X”

El algoritmo original produciría $X$ como la suma de dos números uniformemente aleatorios en el rango de 0 a 100, pero descartaría cualquier resultado donde 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. Podemos analizar 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 los valores mayores que 100, la probabilidad será $\frac{1+x}{5050}$

La probabilidad de generar inmediatamente $X=x$ y $Y=100-x$ se puede entonces obtener 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)$ se puede calcular escalando el denominador de manera que la suma sea $1”

En este punto queda claro que $X” no está distribuido 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 vuelve:

• Elige $r$ de manera uniforme al azar en los enteros $[0;176850]$
• Toma el valor más pequeño de $x$ tal que $\Sigma_{i=0}^x (1+x)(101-x) \geq r”
• Elige $a$ de manera uniforme al azar en el rango $0$ a $x”
• Sea $b := x-a”
• Elige $c” de manera uniforme al azar en el rango$0$a$100-x”
• Sea $d := 100-x-b”

Answer 4

¿Son realmente un problema las limitaciones computacionales? ¿Tienes la intención de escalar esto a números más altos? ¿Se necesita lograr este método usando dados físicos, un programa para tirar dados, Excel o un lenguaje de programación?

Como señala Thomas Andrews, usar ese método tenderá hacia algo como 50/25/12/12 en comparación con 25/25/25/25.

¿Por qué no simplemente tirar 4 dados entre 0 y 100, y comprobar si suman 100? Si lo hacen, guárdalo, de lo contrario, tira de nuevo. El siguiente código en Java fue probado con 4 números hasta 1,000,000 y devolvió resultados en aproximadamente ~3 segundos. Para números más grandes, deberás ser más inteligente.

public class RollerMain {

    public static void main(String[] args) {
        while (true) {
            int firstNumber = (int)((Math.random())*101);
            int secondNumber = (int)((Math.random())*101);
            int thirdNumber= (int)((Math.random())*101);
            int fourthNumber= (int)((Math.random())*101);
            if (firstNumber + secondNumber + thirdNumber + fourthNumber == 100){
                System.out.println("primer número = "+firstNumber);
                System.out.println("segundo número = "+secondNumber );
                System.out.println("tercer número = "+thirdNumber );
                System.out.println("cuarto número = "+fourthNumber);
                break;
            }
        }
    }
}

Answer 5

Puede haber una necesidad de una especificación ligeramente más precisa de qué tipo de muestra deseas. pero para empezar, puedes sentirte menos inseguro si muestreas eligiendo tres números al azar en $[0,100] \cap \mathbb{Z}$, llamémoslos $a,b,c$ suponiendo que los has ordenado de manera que $0 \le a \le b \le c \le 100$

ahora establece: $$x_1 = a \\ x_2 = b-a \\ x_3 = c-b \\ x_4 = 100-c \\ $$ ahora tienes $$\sum_{k=1}^4 x_k = 100-c+c-b+b-a+a =100$$