@ZS La formule que tu cherches est la suivante. Pour 0=<k=<n des entiers, je note C(n, k) le coefficient binomial (k parmis n). La probabilité P(n, m) d'arriver à mettre au moins n marqueurs en ayant m manas au départ est donné par :
P(n, m) = 1 - 2^(2-2n-m) x sum(i = 0,...,n-1; C(2n+m-1, i))
Démonstration : On trouve la relation de récurrence vérifiée par les P(n, m), et on vérifie aisément que l'expression proposée vérifie la même relation de récurence tout en remplissant les mêmes conditions initiales.
Démonstration 2 : Nan, en fait, c'est une blague, je ne suis pas du tout assez fort pour résoudre la relation de récurence à 2 paramètres que tu as calculée brute force style. J'ai résolu le problème autrement. L'idée, c'est que le nombre de manas que tu as après les pile ou face suit ce qu'on appelle une marche aléatoire. Un peu de littérature à ce sujet
ici.
Donc j'appelle S_k le nombre de manas que tu as après k lancers de pièce, en particulier S_0 = m. J'appelle X_k = 1 ou -1 le résultat du k-ième lancer, de sorte que :
S_k = m + sum(i=1,...,k; X_k)
Si un lancer X_k donne 1, j'appelle ça une montée, sinon c'est une descente. Je cherche donc à calculer la probabilité d'avoir au moins n montées avant que ma marche aléatoire S_k ne s'annule.
Je fixe maintenant le nombre de lancers de pièce à 2n + m - 1. Il est possible que mon jeu se termine avant, mais ce n'est pas grave, je lance les pièces jusqu'à la fin quitte à ce que mon nombre virtuel de mana S_k soit négatif si jamais il s'annule avant, ce sera commode pour calculer la formule. Pourquoi ce nombre? Il est suffisament grand pour que si je n'ai pas obtenu au moins mes n montées, alors forcément S_(2n + m - 1) est négatif. Il est suffisament petit pour que si j'ai obtenu mes n montées avant que S_k ne s'annule, alors S_k ne s'est jamais annulé lors de mes 2n + m - 1 lancers, puisqu'il n'y a pas la place pour redescendre à 0 après n montées.
On obtient donc que les suites de lancers qui ne me permettent pas d'avoir n montées avant de perdre tout mon mana (c'est-à-dire annuler S_k) sont exactement celles qui annulent S_k quelque part dans mes 2n + m - 1 tirages. Je vais donc compter le nombre de ces suites ce qui me permettra de calculer la probabilité de l'événement complémentaire à celui qui m'intéresse. Parmis elles, il y a d'un côté celles qui finissent à un total S_(2n + m - 1) négatif et de l'autre celles qui finissent à un total positif mais s'annulent entre-temps.
D'après le petit papier que j'ai mis en lien plus haut, le nombre de suites qui aboutissent à un total S_(2n + m - 1) égal à S entier pair est nul. Le nombre qui aboutissent à un total égal à S entier impair négatif S = -(2j + 1) est donné par un nombre binomial C(2n+m-1, i) en notant i = (2n + m - 1 + S - m) / 2 le nombre de montées correspondant. D'après le principe de réflexion, c'est le théorème 1.2 du petit papier, le nombre de suites qui aboutissent à un total positif impair S = 2j + 1 mais annulent S_k entre-temps est exactement le nombre de suite qui aboutissent au total -S que je viens de calculer.
On introduit la probabilité 2^(1-2n-m) que chacune des suites individuellement a de se produire, on somme et on obtient la zolie formule que j'ai exhibée en haut de mon post, aux erreurs bêtes d'inattention près bien sûr.