Calcule probabilité somme variables aléatoires discrètes

[vincent2303]

Bonjour,

Soit P une lois discrète sur [0, 1, ..., 9]. ( cette loi est connue, je connais P(X=0), P(X=1), ...P(X=9) )
Soit X1, X2, ... , Xk k variables aléatoires mutuellement indépendantes de lois P
Soit S = X1 + X2 + .. + Xk
Soit alpha appartenant à [0, 9*k]

Je cherche un moyen de calculer P(S <= alpha).

Existe il un moyen rapide de calculer cette probabilité en python (ou existe il une formule mathématique permettant d'obtenir la fonction de répartition de S) ?

(Ordre de grandeur: Je dois répéter 50 000 fois cette opération, avec k allant de 1 à 20 000)

Merci d'avance


---- Ce que j'ai tenté ----

J'ai cherché sur google, j'ai testé: "fonction de répartition somme variables aléatoire discrete" (idem en anglais) mais je n'ai rien trouvé qui ai pu m'aider.

J'ai écris un algorithme en python qui permet de résoudre le problème que je me pose. Code:

X_law = { i: 1/10 for i in range(10) }
S_law = X_law.copy()
k = 1000
alpha = round(k*9 / 2) # Expect 0.5 as result

def sum_law(law_0, law_1):
. max_value_law_0 = max(law_0.keys())
. max_value_law_1 = max(law_1.keys())
. new_law = { value: 0 for value in range(max_value_law_0 + max_value_law_1 + 1) }

. for value_0, p_0 in law_0.items():
. for value_1, p_1 in law_1.items():
. new_law[value_0 + value_1] += p_0 * p_1
. return new_law

for i in range(0, k-1):
. S_law = sum_law(S_law, X_law)

result = sum([p for value, p in S_law.items() if value <= alpha])
print(result)

Le problème: cette algorithme a une complexité au carré de k et pour k = 1000, le temps d’execution est de 7 secondes. Or je doit répéter l’exécution 50 000 fois avec en moyenne des valeurs de k à 1000, certaines valeurs de k pouvant atteindre les 20 000.
-----

[gg0]

Bonjour.

A priori, il n'existe pas de formule pour ce genre de problème. Cependant, pour k grand, une approximation gaussienne peut donner de bons résultats et un calcul rapide : Si m est la moyenne de la loi P et s son écart type, alors S suit approximativement une loi Normale de moyenne km et de variance ks². Sans rien connaître sur P, quelques centaines suffisent pour que l'approximation soit utile. Si les valeurs de P sont à peu près réparties entre les 10 issues, une centaine devrait déjà donner des résultats utilisables. Mais c'est du calcul approché.

Cordialement.

[vincent2303]

Bonjour,

Merci de votre réponse. Effectivement je me souvenais qu'il était possible d'utiliser une approximation gaussienne pour ce problème mais je ne savais pas comment l'utiliser en pratique (à partir de quel k l'approximation devenait utile). Si pour des valeurs de k > 100 l'approximation devient utile, je pense que je vais utiliser cette méthode (et faire le calcule exacte pour les plus petites valeurs de k).

Encore merci pour votre réponse