Tirages avec remise

Réponses à toutes vos questions de la 2nde à la Terminale toutes séries
Stubbs
Membre Naturel
Messages: 18
Enregistré le: 17 Sep 2017, 10:23

Tirages avec remise

par Stubbs » 03 Sep 2019, 12:39

Bonjour à toutes et à tous,

Nous jetons X fois N balles dans K urnes. Après chaque itération, nous retirons les urnes qui ne sont pas vides. Quelle est la quantité minimale d'urnes pour que le risque d’avoir un bac vide à la fin soit supérieur à Y% ?

Un grand merci d'avance !



GaBuZoMeu
Habitué(e)
Messages: 6016
Enregistré le: 05 Mai 2019, 11:07

Re: Tirages avec remise

par GaBuZoMeu » 03 Sep 2019, 15:52

Pas tout à fait évident qu'on puisse trouver une réponse simple.
Je suppose que les lancers possibles des boules dans les urnes sont équiprobables ?
Parmi ces lancers, le nombre de ceux qui atteignent exactement une partie de urnes parmi les est le nombre de surjections d'un ensemble à éléments dans un ensemble à éléments, donné par une formule bien connue faisant intervenir le principe d'inclusion-exclusion.
Est-ce une question que tu te poses ou un exercice qui t'es posé (auquel cas on peut se dire qu'il y a une réponse pas trop compliquée) ?

Stubbs
Membre Naturel
Messages: 18
Enregistré le: 17 Sep 2017, 10:23

Re: Tirages avec remise

par Stubbs » 03 Sep 2019, 16:21

Les lancers sont équiprobables, oui.

Mon niveau en mathématiques est malheureusement assez bas, il m'est donc impossible en l'état de comprendre ce à quoi tu fais référence, haha.

C'est une question que je me pose dans le cadre d'un projet perso.

Au cas où cela pourrait aider, on peut fixer Y à 100%.

GaBuZoMeu
Habitué(e)
Messages: 6016
Enregistré le: 05 Mai 2019, 11:07

Re: Tirages avec remise

par GaBuZoMeu » 03 Sep 2019, 17:17

Tu te poses peut-être un problème qui dépasse tes capacités, alors.

Je n'ai pas de formule, mais un code (en SageMath) qui donne la proba qu'il reste au moins une urne vide après x tours, avec n boules et en partant de k urnes.

Code: Tout sélectionner
# compte les surjections de n sur q
def surj(n,q) :
    return add((-1)^(q-i)*binomial(q,i)*i^n for i in range(q+1))

# proba qu'il reste q urnes vides après lancer de n boules dans k urnes
def proba(n,k,q) :
    return surj(n,k-q)*binomial(k,q)/k^n

# prend le nombre n de boules et la liste L des probas
# qu'il y ait 1,2,3,... urnes et retourne la liste des
# probas qu'il y ait 1,2,3,... urnes vides après le
# lancer de n boules
def tour(n,L) :
    k=len(L)
    return [add(L[i]*proba(n,i+1,j+1) for i in range(j,k)) for j in range(k)]

# prend le nombre n de boules, le nombre k d'urnes
# au départ et le nombre x de tours de lancers,
# et retourne la liste des probabs qu'il reste
# 1,2,...,k urnes vides après x tours de lancers
def reste(n,k,x) :
    L=(k-1)*[0]+[1]
    for i in range(x) :
        L=tour(n,L)
    return L

# prend le nombre n de boules, le nombre k d'urnes
# au départ et le nombre x de tours de lancers,
# et retourne la probabilité qu'il reste au moins
# une urne vide après x tours de lancers
def probareste(n,k,x) :
    return add(reste(n,k,x))


Par exemple, pour 4 boules et 10 urnes :
Code: Tout sélectionner
for i in range(7) :
    print "proba qu'il reste une urne vide après",i,\
    "tours :", probareste(4,10,i).n(10)

donne :
Code: Tout sélectionner
proba qu'il reste une urne vide après 0 tours : 1.0
proba qu'il reste une urne vide après 1 tours : 1.0
proba qu'il reste une urne vide après 2 tours : 1.0
proba qu'il reste une urne vide après 3 tours : 0.65
proba qu'il reste une urne vide après 4 tours : 0.040
proba qu'il reste une urne vide après 5 tours : 0.00025
proba qu'il reste une urne vide après 6 tours : 2.4e-7


Fixer Y à 100% me semble complètement idiot, désolé de te le dire : il est clair que dès que x fois n est supérieur ou égal à k, il y a une probabilité non nulle qu'il ne reste aucune urne vide.

PS. Le code que j'ai donné plus haut, c'est essentiellement du python. Avec quelques petits ajouts (expliquer binomial, add) et modifications à la marge, on a un vrai code python que voici :

Code: Tout sélectionner
# coefficients binomiaux
def binomial(n, k):
    if 0 <= k <= n:
        ntok = 1
        ktok = 1
        for t in range(1, min(k, n - k) + 1):
            ntok *= n
            ktok *= t
            n -= 1
        return ntok // ktok
    else:
        return 0

# somme des nombres d'une liste
def add(L):
    S=0
    for l in L : S+=l
    return S

# compte les surjections de n sur q
def surj(n,q) :
    return add([(-1)**(q-i)*binomial(q,i)*i**n for i in range(q+1)])

# proba qu'il reste q urnes vides après lancer de n boules dans k urnes
def proba(n,k,q) :
    return surj(n,k-q)*binomial(k,q)/k**n

# prend le nombre n de boules et la liste L des probas
# qu'il y ait 1,2,3,... urnes et retourne la liste des
# probas qu'il y ait 1,2,3,... urnes vides après le
# lancer de n boules
def tour(n,L) :
    k=len(L)
    return [add([L[i]*proba(n,i+1,j+1) for i in range(j,k)]) for j in range(k)]

# prend le nombre n de boules, le nombre k d'urnes
# au départ et le nombre x de tours de lancers,
# et retourne la liste des probabs qu'il reste
# 1,2,...,k urnes vides après x tours de lancers
def reste(n,k,x) :
    L=(k-1)*[0]+[1]
    for i in range(x) :
        L=tour(n,L)
    return L

# prend le nombre n de boules, le nombre k d'urnes
# au départ et le nombre x de tours de lancers,
# et retourne la probabilité qu'il reste au moins
# une urne vide après x tours de lancers
def probareste(n,k,x) :
    return add(reste(n,k,x))

GaBuZoMeu
Habitué(e)
Messages: 6016
Enregistré le: 05 Mai 2019, 11:07

Re: Tirages avec remise

par GaBuZoMeu » 03 Sep 2019, 18:58

Il est instructif de faire quelques expériences : on constate que le passage de la situation où on est quasi-sûr d'avoir au moins une urne vide à celle où on est quasi-sûr ne n'en avoir aucune se fait très rapidement. Par exemple, pour 20 boules et 120 urnes :

proba qu'il reste une urne vide après 5 tours : 1.00000000000000
proba qu'il reste une urne vide après 6 tours : 0.999999999999996
proba qu'il reste une urne vide après 7 tours : 0.991642082631848
proba qu'il reste une urne vide après 8 tours : 0.137325455252893
proba qu'il reste une urne vide après 9 tours : 0.0000256339653729359

On passe de plus de 99% pour 7 tours à moins de 3 pour 100000 pour 9 tours.

GaBuZoMeu
Habitué(e)
Messages: 6016
Enregistré le: 05 Mai 2019, 11:07

Re: Tirages avec remise

par GaBuZoMeu » 04 Sep 2019, 00:27

Je précise que les résultats que je donne ne sont bien sûr pas des simulations, mais des résultats exacts correspondant aux données du problème. Ils reposent tout bêtement sur des calculs de dénombrement (nombre de cas favorables / nombre de cas totaux), puisque Stubbs a bien explicité l'hypothèse d'équiprobabilité.

La procédure reste(n,k,x) est celle qui donne le plus d'informations : étant donné le nombre de boules n, le nombre d'urnes au départ k, et le nombre de tours de lancers x, elle renvoie la liste des probabilités exactes pour qu'il reste 1 urne vide, 2, 3 etc.
Par exemple reste(4,15,5) - 4 boules, 15 urnes, 5 tours de lancers - renvoie
Code: Tout sélectionner
[262463183261841957740693574439/1684976604586659191808000000000,
 300541752318615126800841114661/13479812836693273534464000000000,
 2940907301575323007492135321/1497756981854808170496000000000,
 9956847451424466151353727/93609811365925510656000000000,
 2107891037980516069651/599102792741923268198400000,
 46428834951715344041/665669769713248075776000000,
 14057061918646519/17466553724254322688000000,
 176198408611/34114362742684224000000,
 5107/303870831264000000,
 1/46796108014656000,
 0,
 0,
 0,
 0,
 0]

On lit ainsi dans cette liste qu'il y a très exactement une probabilité de
9956847451424466151353727/93609811365925510656000000000
pour qu'il reste 4 urnes vides après le 5e tour de lancers.

Stubbs
Membre Naturel
Messages: 18
Enregistré le: 17 Sep 2017, 10:23

Re: Tirages avec remise

par Stubbs » 04 Sep 2019, 10:04

GaBuZoMeu a écrit:Tu te poses peut-être un problème qui dépasse tes capacités, alors.

Largement, oui. D'où ma présence.

GaBuZoMeu a écrit:Fixer Y à 100% me semble complètement idiot, désolé de te le dire : il est clair que dès que x fois n est supérieur ou égal à k, il y a une probabilité non nulle qu'il ne reste aucune urne vide.

Ne sois pas désolé, ce n'est pas si étonnant étant donné ma faible compréhension des probabilités. Lorsque je simule un scénario un million de fois et que j'en fais la moyenne, j'arrive clairement à un stade où on est “certain” d'avoir une urne vide à la fin. Mauvais raisonnement.

GaBuZoMeu a écrit:Il est instructif de faire quelques expériences : on constate que le passage de la situation où on est quasi-sûr d'avoir au moins une urne vide à celle où on est quasi-sûr ne n'en avoir aucune se fait très rapidement.

Tu mets justement le doigt sur ce pourquoi j'ai besoin de la réponse à cette question :)

GaBuZoMeu a écrit:Je précise que les résultats que je donne ne sont bien sûr pas des simulations, mais des résultats exacts correspondant aux données du problème

Je vais tenter de porter ton code pyton en javascript, puisque c'est ce que j'utilise. Ça représente déjà une grande avancée pour la résolution de mon problème. Un grand merci pour le temps investi dans tes réponses !

Le problème restant est qu'il faut simuler avec plusieurs valeurs pour K jusqu'à trouver une réponse satisfaisante. Je vais voir ce que ça donne !

GaBuZoMeu
Habitué(e)
Messages: 6016
Enregistré le: 05 Mai 2019, 11:07

Re: Tirages avec remise

par GaBuZoMeu » 04 Sep 2019, 10:33

Stubbs a écrit:
GaBuZoMeu a écrit:Fixer Y à 100% me semble complètement idiot, désolé de te le dire : il est clair que dès que x fois n est supérieur ou égal à k, il y a une probabilité non nulle qu'il ne reste aucune urne vide.

Ne sois pas désolé, ce n'est pas si étonnant étant donné ma faible compréhension des probabilités. Lorsque je simule un scénario un million de fois et que j'en fais la moyenne, j'arrive clairement à un stade où on est “certain” d'avoir une urne vide à la fin. Mauvais raisonnement.

Il ne s'agit pas ici de probabilité, mais de bon sens.
Si à chaque tour les boules arrivent dans des urnes différentes, quand c'est possible, alors dès que x (le nombre de tours) fois n (le nombre de boules) atteint ou dépasse k (le nombre d'urnes), il n'y a plus d'urne vide. La probabilité qu'il n'y ait plus d'urne vide est strictement positive si nx>=k et nulle si nx<k.
Par ailleurs, au moins une urne est éliminée à chaque tour (et il se peut qu'une seule soit éliminée, si toutes les boules arrivent dans la même urne). Donc la probabilité qu'il n'y ait plus d'urne vide est <1 si x<k, et =1 si x=k.

GaBuZoMeu a écrit:Il est instructif de faire quelques expériences : on constate que le passage de la situation où on est quasi-sûr d'avoir au moins une urne vide à celle où on est quasi-sûr ne n'en avoir aucune se fait très rapidement.

Tu mets justement le doigt sur ce pourquoi j'ai besoin de la réponse à cette question :)

Peux-tu en dire plus sur ta problématique, ou c'est secret d'état?

GaBuZoMeu a écrit:Je précise que les résultats que je donne ne sont bien sûr pas des simulations, mais des résultats exacts correspondant aux données du problème

Je vais tenter de porter ton code pyton en javascript, puisque c'est ce que j'utilise. Ça représente déjà une grande avancée pour la résolution de mon problème. Un grand merci pour le temps investi dans tes réponses !

Le problème restant est qu'il faut simuler avec plusieurs valeurs pour K jusqu'à trouver une réponse satisfaisante. Je vais voir ce que ça donne !


Mon code est loin d'être optimisé.
En fait, ce qu'on étudie ici est une chaîne de Markov. Les états correspondent au nombre d'urnes vides. Le calcul de la matrice de transition entre états est essentiellement ce que fait ma procédure tour(n,L). En fait, je ferais mieux de calculer la matrice et ensuite d'en calculer la puissance voulue. Avec mon code tel qu'il est écrit, je recalcule la matrice de transition à chaque tour, ce qui est une perte de temps. Après, je ne suis pas convaincu que javascript soit ce qu'on fait de mieux pour manipuler des matrices (par exemple, les multiplier). Tu tiens vraiment à javascript ?

Sylviel
Modérateur
Messages: 6466
Enregistré le: 20 Jan 2010, 14:00

Re: Tirages avec remise

par Sylviel » 04 Sep 2019, 11:47

Après, je ne suis pas convaincu que javascript soit ce qu'on fait de mieux pour manipuler des matrices


Tu fais dans l'euphémisme :gene:
Merci de répondre aux questions posées, ce sont des indications pour vous aider à résoudre vos exercices.

Stubbs
Membre Naturel
Messages: 18
Enregistré le: 17 Sep 2017, 10:23

Re: Tirages avec remise

par Stubbs » 04 Sep 2019, 12:15

GaBuZoMeu a écrit:Il ne s'agit pas ici de probabilité, mais de bon sens.

Bien entendu.

GaBuZoMeu a écrit:Peux-tu en dire plus sur ta problématique, ou c'est secret d'état?

Loin de là, haha. Je développe pour un vieux jeu par navigateur un calculateur de défense. Il faut notamment, dans un cas spécifique, construire suffisamment d'un certain type d'unité pour en stopper un autre. Je m'explique :

Un combat est composé de 6 tours (mais ça pourrait peut-être changer dans le futur). À chaque tour, les unités du défenseur et de l'attaquant se tirent dessus en même temps et aléatoirement. À la fin de chaque tour, les unités détruites sont retirées avant le tour suivant. L'attaquant gagne s'il ne reste plus aucune unités adverses à la fin du combat. S'il en reste, c'est le match nul.

Dans le cas présent, les unités de défense ne font aucun dégât aux unités adverses, N reste fixe. Par contre, les unités ennemies détruisent en un coup les défenses.

De part ma configuration serveur, le code doit être exécuter côté client. Javascript est la meilleur option pour ce faire, et d'autant plus que c'est le langage que je maitrise le mieux.

GaBuZoMeu
Habitué(e)
Messages: 6016
Enregistré le: 05 Mai 2019, 11:07

Re: Tirages avec remise

par GaBuZoMeu » 04 Sep 2019, 14:08

Merci, je comprends mieux la problématique.

J'ai modifié mon code Python 3 dans l'esprit chaîne de Markov, mais en évitant de faire appel au paquet numpy.linalg pour permettre éventuellement une traduction plus facile en javascript. Ça va nettement plus vite que le précédent, par exemple pour 120 urnes et 20 boules.


Code: Tout sélectionner
# coefficients binomiaux
def binomial(n, k):
    if 0 <= k <= n:
        ntok = 1
        ktok = 1
        for t in range(1, min(k, n - k) + 1):
            ntok *= n
            ktok *= t
            n -= 1
        return ntok // ktok
    else:
        return 0

# somme des nombres d'une liste
def addlist(L):
    S=0
    for l in L : S+=l
    return S

# compte les surjections de n sur q
def surj(n,q) :
    return addlist([(-1)**(q-i)*binomial(q,i)*i**n for i in range(q+1)])

# proba qu'il reste q urnes vides après lancer de n boules dans k urnes,
# avec traitement spécial du cas k=0
def proba(n,k,q) :
    if k==0 :
        if q==0: return 1
        else : return 0
    else :
        return surj(n,k-q)*binomial(k,q)/k**n

# matrice de transition de la chaîne de Markov
# comme liste de listes
def transition(n,k) :
    return [[proba(n,i,j) for i in range(k+1)] for j in range(k+1)]

# ersatz de multiplication matrice-vecteur
def multmatvect(A,V) :
    d=len(V)
    return [addlist([A[i][j]*V[j] for j in range(d)]) for i in range(d)]

# prend le nombre n de boules, le nombre k d'urnes
# au départ et le nombre x de tours de lancers,
# et retourne la liste des probas qu'il reste
# 0,1,2,...,k urnes vides après x tours de lancers
def reste(n,k,x) :
    A=transition(n,k)
    L=k*[0]+[1]
    for i in range(x) :
        L=multmatvect(A,L)
    return L

# prend le nombre n de boules, le nombre k d'urnes
# au départ et le nombre x de tours de lancers,
# et retourne la probabilité qu'il ne reste plus
# d'urne vide après x tours de lancers
def probaelimine(n,k,x) :
    return reste(n,k,x)[0]

GaBuZoMeu
Habitué(e)
Messages: 6016
Enregistré le: 05 Mai 2019, 11:07

Re: Tirages avec remise

par GaBuZoMeu » 04 Sep 2019, 15:19

Par exemple, on obtient rapidement la liste des probabilités d'élimination des urnes pour n=10 boules, x=6 tours, et k urnes au départ, avec k variant de 30 à 60 :

Code: Tout sélectionner
k= 30  :  (0.9999976271689872,)
k= 31  :  (0.9999919716319614,)
k= 32  :  (0.9999744791666196,)
k= 33  :  (0.9999237589619842,)
k= 34  :  (0.9997859539210946,)
k= 35  :  (0.99943531732955,)
k= 36  :  (0.998600280284522,)
k= 37  :  (0.9967400497244271,)
k= 38  :  (0.9928657180242075,)
k= 39  :  (0.9853263956327388,)
k= 40  :  (0.9716281944763874,)
k= 41  :  (0.9484111415517404,)
k= 42  :  (0.911743699645405,)
k= 43  :  (0.8578571637572017,)
k= 44  :  (0.784294054181758,)
k= 45  :  (0.6912024261774197,)
k= 46  :  (0.5822758924919857,)
k= 47  :  (0.46478360711051236,)
k= 48  :  (0.3483837873513694,)
k= 49  :  (0.2429319844756179,)
k= 50  :  (0.1560345472492654,)
k= 51  :  (0.09131951274309069,)
k= 52  :  (0.04810690054960892,)
k= 53  :  (0.02248761858425984,)
k= 54  :  (0.009166804586803674,)
k= 55  :  (0.003187398578702116,)
k= 56  :  (0.0009178652319919577,)
k= 57  :  (0.00020987901015420132,)
k= 58  :  (3.568232982519628e-05,)
k= 59  :  (4.004652037074188e-06,)
k= 60  :  (2.2225415310903611e-07,)


Stubbs
Membre Naturel
Messages: 18
Enregistré le: 17 Sep 2017, 10:23

Re: Tirages avec remise

par Stubbs » 04 Sep 2019, 20:35

C'est vraiment top ! Encore merci.

Ici, je pourrai par exemple choisir de m'arrêter à la valeur 54. Avec de plus grandes valeurs par contre, N = 10.000.000 par exemple, chaque cas n'est pas testable un à un. Un algorithme de recherche adapté est obligatoire.

GaBuZoMeu
Habitué(e)
Messages: 6016
Enregistré le: 05 Mai 2019, 11:07

Re: Tirages avec remise

par GaBuZoMeu » 04 Sep 2019, 21:41

Euh ... 10 millions de boules, tu es sérieux ? Ton jeu gère ça ?

Stubbs
Membre Naturel
Messages: 18
Enregistré le: 17 Sep 2017, 10:23

Re: Tirages avec remise

par Stubbs » 04 Sep 2019, 22:47

Ce n'est pas non plus monnaie courrante, mais largement, ouaip :) Lors d'un très gros combat, l'issue peut mettre jusqu'à plusieurs dizaines de secondes pour être générée.

GaBuZoMeu
Habitué(e)
Messages: 6016
Enregistré le: 05 Mai 2019, 11:07

Re: Tirages avec remise

par GaBuZoMeu » 05 Sep 2019, 00:26

En tout cas, même avec n= 10 millions, tu est sûr qu'avec k=60 millions il restera des urnes non remplies si tu fais 6 tours. :mrgreen:

Stubbs
Membre Naturel
Messages: 18
Enregistré le: 17 Sep 2017, 10:23

Re: Tirages avec remise

par Stubbs » 05 Sep 2019, 09:14

C'est sûr, mais ce serait un gros gaspillage de ressources du jeu (et moins drôle aussi :p ).

GaBuZoMeu
Habitué(e)
Messages: 6016
Enregistré le: 05 Mai 2019, 11:07

Re: Tirages avec remise

par GaBuZoMeu » 05 Sep 2019, 11:49

On peut prendre les choses par un autre bout.
Si est très grand (ton 10 000 000) et avec entre 5 et 6 (on reste dans l'idée de 6 tours), alors l'espérance du nombre de défenses non touchées après un tour de tir est , ce qui fait à peu près , disons à la louche entre et fois .
On peut recommencer pour le deuxième tour, etc.. Bien entendu ce calcul n'est absolument pas correct, mais ça peut donner des idées pour un calcul plus correct.

Stubbs
Membre Naturel
Messages: 18
Enregistré le: 17 Sep 2017, 10:23

Re: Tirages avec remise

par Stubbs » 05 Sep 2019, 13:18

Intéressant !

Reste à définir précisément “très grand “, car j'imagine que ça ne fonctionnera pas avec de petites valeurs de N. Aussi, A pourrait être de l'ordre de 3.7/3.75 sur des valeurs pareilles. Du moins, avec mes imparfaites simulations.

Afin d'élargir mes connaissances, peux-tu me dire ce que représente ta première formule et pourquoi tu la simplifie en passant à la deuxième ?

GaBuZoMeu
Habitué(e)
Messages: 6016
Enregistré le: 05 Mai 2019, 11:07

Re: Tirages avec remise

par GaBuZoMeu » 05 Sep 2019, 15:58

Je calcule l''espérance du nombre de cibles épargnées après un tour, en fonction de le nombre de balles et le nombre de cibles.
Pour cela j'introduis les variables aléatoires pour qui valent 1 si la cible n) est épargnée et 0 si elle est atteinte. La somme est le nombre de cibles épargnées. L'espérance de est la probabilité d'être épargnée par les balles, c'est (chaque cible a la probabilité d'être touchée par une balle, et les balles touchent les cibles de façon indépendante). L'espérance du nombre de cibles épargnées est la somme des espérances des , c'est donc . Ceci, quels que soient et .

Ensuite, si est grand, est très proche de et donc est très proche de .


Il peut être intéressant de noter que majore la probabilité qu'il existe au moins une cible épargnée. Par exemple, avec et , la probabilité qu'il reste au moins une cible épargnée est à peu près de 1 pour mille.

 

Retourner vers ✎✎ Lycée

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 31 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite