Algoritmo para calcular la probabilidad de que suceda una suma de los resultados

Question

El algoritmo del que hablo me permitiría presentarlo con x número de elementos, cada uno de los cuales tiene un rango de aab con el resultado de y. Me gustaría tener un algoritmo que, cuando se presenta con los valores como se describe, genere la posibilidad de que ocurra.

Por ejemplo, para dos mueren. Ya los conozco (debido a que los resultados posibles son muy bajos). Sería capaz de decirle cada una de las posibilidades.

La configuración sería algo así como. x = 2 a = 1 b = 6. Si quisieras saber la posibilidad de que resulte en un 2. Entonces simplemente escupiría 1/36 (o su valor flotante). Si coloca 7 como la suma total, le diría 6.

Así que mi pregunta es, ¿existe una manera simple de implementar tal cosa mediante un algoritmo que ya está escrito? O bien, uno tiene que pasar por cada iteración de cada elemento para obtener el número total de combinaciones para cada valor.

La fórmula exacta también, le daría las combinaciones para hacer cada uno de los valores del 1-12.

Así que le daría una matriz de distribución con las combinaciones de cada uno en cada uno de los índices. Si lo hace 0-12. Entonces 0 tendría 0, 1 tendría 0 y 2 tendrían 1.

Siento que este es el tipo de problema que alguien más ha tenido y con el que quería trabajar y que ya lo ha hecho. Si alguien tiene una manera fácil de hacer esto más allá de simplemente pasar por todos los valores posibles, sería increíble.

No tengo idea de por qué quiero resolver este problema, pero por alguna razón hoy tuve la sensación de querer resolverlo. Y como he estado buscando en Google y usando wolfram alpha, además de probarlo yo mismo. Creo que es hora de reconocer la derrota y preguntar a la comunidad.

Me gustaría que el algoritmo esté en c, o tal vez PHP (aunque preferiría que no lo fuera, ya que es mucho más lento). La razón de c es simplemente porque quiero velocidad sin formato, y no quiero tener que lidiar con clases u objetos.

Pseudocódigo, o C es la mejor manera de mostrar su algoritmo.

Editar:

Además, si ofendí a la persona con una 'B' en su nombre debido a lo que pasa con las matemáticas lo siento. Como no quise ofender, solo quería decir que I no lo entendí. Pero la respuesta podría haber permanecido allí ya que estoy seguro de que hay personas que podrían llegar a esta pregunta y comprender las matemáticas que hay detrás.

Además, no puedo decidir por qué camino quiero codificar esto. Creo que intentaré usar ambos y luego decidiré cuál me gusta más para ver/usar dentro de mi pequeña biblioteca.

Lo último que olvidé decir es que el cálculo está a punto de ocurrir hace cuatro años. Mi comprensión de la probabilidad, las estadísticas y la aleatoriedad provienen de mi propio aprendizaje al mirar el código/lectura de wikipedia/lectura de libros.

Si alguien tiene curiosidad, es lo que provocó esta pregunta. Tenía un libro que posponía leer llamado The Drunkards Walk y luego, una vez que dije XKCD 904, decidí que era hora de finalmente leerlo. Entonces, hace dos noches, mientras iba a dormir ...Había reflexionado sobre cómo resolver esta pregunta a través de un algoritmo simple y pude pensar en uno.

Mi comprensión del código de codificación proviene de jugar con otros programas, ver lo que sucedió cuando rompí algo, y luego probar mis cosas mientras reviso la documentación para las funciones de compilación. Entiendo la notación de O grande al leer sobre wikipedia (tanto como uno puede por eso), y el pseudo código era porque es muy similar a python. Yo mismo, no puedo escribir pseudo código (o dice que los profesores en la universidad). Seguí recibiendo notas como "haz que sea menos como el código real lo hagas más como un seudo código". Esa cosa no ha cambiado.

Editar 2: En caso de que alguien que busque esta pregunta simplemente quería el código rápidamente. Lo he incluido a continuación. Está licenciado bajo LGPLv3 ya que estoy seguro de que existen equivalentes de código cerrado de este código.

Debe ser bastante portátil ya que está escrito completamente en c. Si uno quisiera convertirlo en una extensión en cualquiera de los varios idiomas que están escritos en c, debería tomar muy poco esfuerzo hacerlo. Elegí 'marcar' el primero que se vinculó con "Ask Dr. Math" como la respuesta ya que fue la implementación que he usado para esta pregunta.

El primer nombre de archivo es "sum_probability.c"

#include <math.h> 
#include <stdlib.h> 
#include <stdio.h> 
#include <limits.h> 

/*! 
* file_name: sum_probability.c 
*  
* Set of functions to calculate the probabilty of n number of items adding up to s 
* with sides x. The question that this program relates to can be found at the url of 
* http://stackoverflow.com/questions/6394120/ 
*  
*  Copyright 2011, Macarthur Inbody 
*  
* This program is free software: you can redistribute it and/or modify 
* it under the terms of the Lesser GNU General Public License as published by 
* the Free Software Foundation, either version 3 of the License, or 
* (at your option) any later version. 
* 
* This program is distributed in the hope that it will be useful, 
* but WITHOUT ANY WARRANTY; without even the implied warranty of 
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 
* GNU General Public License for more details. 
* 
* You should have received a copy of the Lesser GNU General Public License 
* along with this program. If not, see <http://www.gnu.org/licenses/lgpl-3.0.html>. 
*  
* 2011-06-20 06:03:57 PM -0400 
*  
* These functions work by any input that is provided. For a function demonstrating it. 
* Please look at the second source file at the post of the question on stack overflow. 
* It also includes an answer for implenting it using recursion if that is your favored 
* way of doing it. I personally do not feel comfortable working with recursion so that is 
* why I went with the implementation that I have included. 
* 
*/ 

/* 
* The following functions implement falling factorials so that we can 
* do binomial coefficients more quickly. 
* Via the following formula. 
* 
* K 
* PROD (n-(k-i))/i 
* i=1; 
* 
*/ 

//unsigned int return 
unsigned int m_product_c(int k, int n){ 
    int i=1; 
    float result=1; 
    for(i=1;i<=k;++i){ 
     result=((n-(k-i))/i)*result; 
    } 
    return result; 
} 

//float return 
float m_product_cf(float n, float k){ 
    int i=1; 
    float result=1; 
    for(i=1;i<=k;++i){ 
     result=((n-(k-i))/i)*result; 
    } 
    return result; 
} 


/* 
* The following functions calculates the probability of n items with x sides 
* that add up to a value of s. The formula for this is included below. 
* 
* The formula comes from. http://mathforum.org/library/drmath/view/52207.html 
* 
*s=sum 
*n=number of items 
*x=sides 
*(s-n)/x 
* SUM (-1)^k * C(n,k) * C(s-x*k-1,n-1) 
* k=0 
* 
*/ 

float chance_calc_single(float min, float max, float amount, float desired_result){ 
    float range=(max-min)+1; 
    float series=ceil((desired_result-amount)/range); 
    float i; 
    --amount; 
    float chances=0.0; 
    for(i=0;i<=series;++i){ 
     chances=pow((-1),i)*m_product_cf(amount,i)*m_product_cf(desired_result-(range*i)-1,amount)+chances; 
    } 
    return chances; 
} 

Y aquí es el archivo que muestra la aplicación como dije en el archivo anterior.

#include "sum_probability.c" 

/* 
* 
* file_name:test.c 
* 
* Function showing off the algorithms working. User provides input via a cli 
* And it will give you the final result. 
* 
*/ 
int main(void){ 
     int amount,min,max,desired_results; 
     printf("%s","Please enter the amount of items.\n"); 
     scanf("%i",&amount); 
     printf("%s","Please enter the minimum value allowed.\n"); 
     scanf("%i",&min); 
     printf("%s","Please enter the maximum value allowed.\n"); 
     scanf("%i",&max); 
     printf("%s","Please enter the value you wish to have them add up to. \n"); 
     scanf("%i",&desired_results); 
     printf("The total chances for %i is %f.\n", desired_results, chance_calc_single(min, max, amount, desired_results)); 
} 

Answer 1

En primer lugar, no necesita preocuparse por el rango de a a b. Puede simplemente restar a*x de y y pretender que el rango va desde 0 hasta b-a. (Debido a que cada elemento contribuye al menos a la suma a ... Así se puede restar de que a una vez para cada uno de sus elementos x.)

En segundo lugar, tenga en cuenta que lo que realmente están tratando de hacer es recuento la número de formas de lograr una suma particular. La probabilidad es solo ese conteo dividido por un exponencial simple (b-a+1)^x.

Este problema fue cubierto por "Ask Dr. Math" hace alrededor de una década:

http://mathforum.org/library/drmath/view/52207.html

Su formulación está asumiendo dados numerados de 1 a X, por lo que utilizar su respuesta, es probable que quieren cambie su rango por a-1 (en lugar de a) para convertirlo a esa forma.

Su derivación utiliza funciones de generación que creo que merecen una pequeña explicación. La idea es definir un polinomio f(z) tal que el coeficiente en z^n es el número de formas de rodar n. Para un dado de 6 caras, por ejemplo, esta es la función generadora:

z + z^2 + z^3 + z^4 + z^5 + z^6 

... porque no hay una manera de rodar cada número del 1 al 6, y cero formas de rodar cualquier otra cosa.

Ahora, si tiene dos funciones generadoras g(z) y h(z) para dos juegos de dados, resulta que la función de generación para la unión de estos conjuntos es sólo el producto de g y h. (Mirar a la operación de "multiplicar dos polinomios" por un tiempo para convencerse de que esto es cierto.) Por ejemplo, para los dos dados, sólo podemos cuadrar la expresión anterior para obtener:

z^2 + 2z^3 + 3z^4 +4z^5 + 5z^6 + 6z^7 + 5z^8 + 4z^9 + 3z^10 + 2z^11 + z^12 

Aviso cómo podemos leer el número de combinaciones directamente fuera de los coeficientes: 1 forma de obtener un 2 (1*z^2), 6 maneras de obtener un 7 (6*z^7), etc.

El cubo de la expresión nos daría la función de generación de tres dados ; el cuarto poder, cuatro dados; y así.

El poder de esta formulación viene cuando escribes las funciones de generación en forma cerrada, multiplicas y luego las expandes nuevamente usando Binomial Theorem. Me inclino por la explicación del Dr. Math para los detalles.

Answer 2

Para obtener todas las posibilidades, usted podría hacer un mapa de valores:

for (i=a to b) { 
for (j=a to b) { 
    map.put(i+j, 1+map.get(i+j)) 
} 
} 

Para una manera más eficiente para contar sumas, podría utilizar el patrón 6 de 7, 5 de 6, 4 5 de , 3 4's, 2 3's, 1 dos.

El patrón se mantiene para la cuadrícula n x n, habrá n (n + 1) 's, con una posibilidad menos para una suma 1 mayor o menor.

Esto contará las posibilidades, por ejemplo, Count (6, 1/2/3/4/5/6) dará posibilidades de sumas de dados.

import math 
def Count(poss,sumto): 
    return poss - math.fabs(sumto-(poss+1)); 

Editar: En C esto sería:

#include <stdio.h> 
#include <stdlib.h> 
#include <math.h>; 

int count(int poss, int sumto) 
{ 
    return poss - abs(sumto-(poss+1)); 
} 

int main(int argc, char** argv) { 
    printf("With two dice,\n"); 
    int i; 
    for (i=1; i<= 13; i++) 
    { 
     printf("%d ways to sum to %d\n",count(6,i),i); 
    } 
    return (EXIT_SUCCESS); 
} 

da:

With two dice, 
0 ways to sum to 1 
1 ways to sum to 2 
2 ways to sum to 3 
3 ways to sum to 4 
4 ways to sum to 5 
5 ways to sum to 6 
6 ways to sum to 7 
5 ways to sum to 8 
4 ways to sum to 9 
3 ways to sum to 10 
2 ways to sum to 11 
1 ways to sum to 12 
0 ways to sum to 13 

Answer 3

teoría de los números, las estadísticas y la combinatoria llevan a creer que para llegar a un valor numérico para la probabilidad de un evento - bueno usted debe saber 2 cosas:

• el número de resultados posibles
• dentro del conjunto de resultados totales cuántos equivalen al resultado 'y' cuyo valor de probabilidad busca.

En pseudocódigo:

numPossibleOutcomes = calcNumOutcomes(x, a, b); 
numSpecificOutcomes = calcSpecificOutcome(y); 
probabilityOfOutcome = numSpecificOutcomes/numPossibleOutcomes; 

A continuación, sólo codificar hasta las 2 funciones a partir del cual debe ser fácil.

Answer 4

Digamos que f(a, b, n, x) representa el número de formas en que puede seleccionar n números entre ayb, que suman un total de x.

continuación, observe que:

f(a, b, n, x) = f(0, b-a, n, x-n*a) 

De hecho, acaba de tomar una forma de lograr la suma de x y de cada uno de los n números restar a, entonces la suma total será x - n*a y cada uno de ellos será entre 0 y ba.

Por lo tanto, es suficiente para escribir el código para encontrar f(0, m, n, x).

Ahora observar que, todas las formas de lograr el objetivo, de manera que el último número es c es:

f(0, m, n-1, x-c) 

De hecho, tenemos n-1 números de la izquierda y quieren que la suma total sea x-c. entonces tenemos una fórmula recursiva:

f(0,m,n,x) = f(0,m,n-1,x) + f(0,m,n-1,x-1) + ... + f(0,m,n-1,x-m) 

donde los sumandos de la derecha corresponden al último número que es igual a 0, 1, ..., m

Ahora se puede poner en práctica que el uso de la recursividad, pero esto será demasiado lento.

Sin embargo, hay un truco llamado recursión memorada, es decir, guarda el resultado de la función, para que no tenga que volver a calcularlo (para los mismos argumentos).

La recursión memorada tendrá una complejidad de O(m * n), porque ese es el número de parámetros de entrada diferentes que necesita calcular y guardar.

Una vez que ha calculado el recuento, debe dividir por el número total de posiblidades, que es (m + 1) * n para obtener la probabilidad final.