Voici un problème que j'aimerai vous présenter. C'est un problème de calcul lié à des probabilités. J'ai une formule de calcul mais la complexité est exponentielle en fonction de la taille N du problème. Je voudrais savoir si on peut calculer plus vite.
Je vous présente ce problème en l'illustrant par un exemple simple.
Imaginons que j'ai une collection de N pièces de monnaie. Sur une seule face de chaque pièce, je note au marqueur un nombre > 0 (différent sur chacune des pièces).
Je lance mes N pièces qui ont chacune une proba de 1/2 de tomber sur la face marquée.
Je calcule le produit de tous les nombres inscrits sur les faces retournées que je note S
On peut calculer facilement la moyenne de S.
(démo par récurrence en vérifiant que la formule reste vraie en ajoutant une pièce et en faisant la moyenne sur les 2 cas équiprobable selon que cette nouvelle pièce tombe ou pas sur la face marquée)
On voit que cette formule permet un calcul rapide en O(N) opérations
Mais, je m'intéresse à la variable
Pour un cas plus simple où chaque pièce est marquée du même nombre R, je peux calculer le résultat en groupant les cas pour lesquels le même nombre de pièces est du coté marqué :
La complexité du calcul reste très raisonnable.
En revanche, si les nombres marqués sur les pièces sont différents, je ne vois pas comment calculer le résultat facilement. Je peux lister chaque issus de mon tirage de pièces, calculer T à chaque fois et faire la moyenne. Mais cela revient à traiter les
Si vous avez des idées, je suis preneur. Ca m'intéresse même d'avoir votre opinion si vous pensez qu'il n'y a pas de méthode de calcul moins complexe.
Arnaud
