proba : des boules et des paires
Répondre à la discussion
Page 1 sur 2 1 DernièreDernière
Affichage des résultats 1 à 30 sur 40

proba : des boules et des paires



  1. #1
    zyket

    proba : des boules et des paires


    ------

    Bonjour,

    je cherche à résoudre un problème de proba que je me pose. Le voici :

    Imaginons une urne remplie de n boules numérotées de 1 à n, n entier naturel pair.
    Je prélève au hasard une première boule, puis une 2ème. Je les mets côte à côte pour former ce que j'appellerai une paire.
    Je prélève au hasard une troisième boule, puis une 4ème. Je les mets côte à côte pour former une deuxième paire.
    Et ainsi de suite jusqu'à ...
    Je prélève au hasard une (n-1)ième boule, puis la (n)ième. Je les mets côte à côte pour former la (n/2) ième paire.

    Au cours de cette première phase je cherche à trouver la probabilité, p, d'avoir au moins une paire dont les numéros se suivent (par ordre croissant ou décroissant peu importe), que je nommerai paire valide.
    Je me doute que l’événement ''avoir au moins une paire valide'' est l'événement complémentaire de ''n'avoir aucune paire valide''. Cet événement ''n'avoir aucune paire valide'', a une probabilité que je noterai (p_n)^0, que l'on peut lire comme : probabilité d'avoir 0 paire parmi n boules.
    Dans ces conditions on a : p=1- (p_n)^0

    Mon problème est : comment calculer (p_n)^0 ?

    En pièce jointe au format pdf, le début de mon raisonnement.

    Merci de vos lumières

    -----
    Images attachées Images attachées

  2. #2
    zyket

    Re : proba : des boules et des paires

    un petit up

  3. #3
    Jeanpaul

    Re : proba : des boules et des paires

    Pourquoi considérer le problème à 3 boules puisque n est pair ?
    Il vaudrait mieux chercher une récurrence entre 2 p boules et 2p+2 boules
    Supposons alors qu'on a 2p+2 boules. Au 1er tirage, on peut tirer une boule entre 1 et 2 p ou alors la boule 2p+1 ou la boule 2p+2 avec des probas évidentes.
    On analyse alors ces 3 cas : si la 1ère est entre 1 et 2p, la seconde peut être entre 1 et 2p et ça marche avec une proba Q(p), ou alors c'est la boule 2p+1 ou la boule 2p+2 et c'est raté pour cette paire.
    Et on reprend l'arbre.
    C'est un peu lourd quand même.
    Une autre approche serait un processus de Monte Carlo sur ordinateur, faire la manip quelques milliers de fois et analyser le nombre de fois où ça marche. Ca ne doit pas être trop dur à programmer.

  4. #4
    danyvio

    Re : proba : des boules et des paires

    Je ne suis pas allé jusqu'au bout du problème, mais je le poserais ainsi : avec 2p boules, combien y a t-il de couples de boules comportant deux numéros consécutifs (CDBC2NC) ? Et combien de façons de tirer un couple quelconque de boules ?
    Ex : si on a 4 boules, on a 3 CDBC2NC, et 6 façons de tirer un couple.
    En fait on a 2p -1 façons de tirer un CDBC2NC (il suffit d'aligner les boules bien ordonnées par n° pour s'en convaincre...) et C22p façons de tirer un couple quelconque.
    Dernière modification par danyvio ; 17/11/2011 à 10h28.
    On trouve des chercheurs qui cherchent ; on cherche des chercheurs qui trouvent !

  5. A voir en vidéo sur Futura
  6. #5
    zyket

    Re : proba : des boules et des paires

    Merci,

    cette façon de faire à l'air très prometteuse

  7. #6
    ansset
    Animateur Mathématiques

    Re : proba : des boules et des paires

    j'aime auss la démarche de Danyvio.
    mais j'ai cru lire "au moins un couple" , et pas un "seul couple".

  8. #7
    danyvio

    Re : proba : des boules et des paires

    Je reviens, en précisant que ma démarche est une approche. En fait, c'est plus compliqué qu'il n'y paraît,car chaque tirage crée une rupture dans la série numérotée. Si je tire les boules 25 et 26, il n'est plus possible de tirer ensuite 24/25 ni 26/27. Idem si on tire des boules non "adjacentes" comme par ex 25 et 50, les tirages 24/25 25/26, 49/50 50/51 deviennent évidemment impossibles.
    Mon post initial #4 répond bien à la question suivante : étant donné 2p boules, quelle est la proba de tirer, au premier tirage une paire de boules numérotées consécutivement. Ensuite ça se complique....
    On trouve des chercheurs qui cherchent ; on cherche des chercheurs qui trouvent !

  9. #8
    ansset
    Animateur Mathématiques

    Re : proba : des boules et des paires

    bien d'accord,
    l'itération n'est pas facile, mais comme je suis un peu maso, je vais regarder ça ce soir.
    car effectivement, à chaque qu'on prend un couple,on fait des dommages collatéraux sur d'autres couples possibles ( bon ou pas )
    mais je te sens motivé Danyvio !

  10. #9
    zyket

    Re : proba : des boules et des paires

    Bonjour,

    à partir de l'idée de danivio et en reprenant sa terminologie explicite, je me suis intéressé aux nombres de Couples De Boules Comportants 2 Numéros Concécutifs (CDBC2NC) dans des séries possibles de 6 boules.

    J'ai construit les séries à partir d'un arbre dont les numéros de chaque arborescence partant d'un numéro sont rangés l'un au dessus de l'autre par ordre croissant :
    Par exemple de la première boule n°1 partent 5 branches aboutissant respectivement aux numéros rangés les uns au dessus des autres dans l'ordre 2 ; 3 ; 4 ; 5 ; 6
    De la première boule n°3 partent 5 branches aboutissant respectivement aux numéros rangés les uns au dessus des autres dans l'ordre 1 ; 2 ; 4 ; 5 ; 6

    En lisant les résultats de haut en bas on obtient une colonne de séries dont voici toutes les séries commençant par 12.... (24 au total)

    123456 3 Couples De Boules Contenant 2 Numéros Concécutifs 1-2 3-4 5-6
    123465 3 CDBC2NC 1-2 3-4 6-5
    123546 1 CDBC2NC 1-2 35 46
    123564 1 CDBC2NC 1-2 35 64
    123645 2 CDBC2NC 1-2 36 4-5
    123654 2 CDBC2NC 1-2 36 5-4

    124356
    124365
    124536
    124563
    124635
    124653

    125346
    125364
    125436
    125463
    125634
    125643

    126345
    126354
    126435
    126453
    126534
    126543

    On constate que tous les groupes de six séries ont chacun 2 séries avec 3 CDBC2NC, 2 séries avec 2 CDBC2NC et 2 séries avec 1 CDBC2NC

    Pour les séries commençant par 16... tous les groupes de six séries ont chacun 2 séries avec 2 CDBC2NC, 2 séries avec 1 CDBC2NC, 2 séries avec 0 CDBC2NC

    On constate donc que le nombre de CDBC2NC dans une série dépend des premiers numéros.

    Mais de toutes ces constatations je n'arrive à tirer aucune loi ...

  11. #10
    ansset
    Animateur Mathématiques

    Re : proba : des boules et des paires

    non, je crains que la combinatoire ne devienne infernale à un certain rang.
    car il faut reprendre tous les tirages antérieurs pour savoir si un couple est possible et/ou il est valable.
    seule solution pour moi
    la dernière suggestion de JeanPaul:
    Une autre approche serait un processus de Monte Carlo sur ordinateur, faire la manip quelques milliers de fois et analyser le nombre de fois où ça marche. Ca ne doit pas être trop dur à programmer.

  12. #11
    zyket

    Re : proba : des boules et des paires

    Une autre approche serait un processus de Monte Carlo sur ordinateur, faire la manip quelques milliers de fois et analyser le nombre de fois où ça marche. Ca ne doit pas être trop dur à programmer.
    Peut être, mais c'est au dessus de mes capacités

  13. #12
    Tryss

    Re : proba : des boules et des paires

    Je pense qu'il n'y a pas de formule simple pour calculer cette probabilité (avec des coefficients binomiaux, des puissances...)

    Sinon par la méthode de Monte-Carlo, je trouve que la probabilité de n'avoir aucune paire valide est a peu près constante quelque soit le nombre de boules (pour un nombre de boules assez grand) et qu'elle vaut environ 36%. Quelqu'un peut confirmer ce résultats?

  14. #13
    ansset
    Animateur Mathématiques

    Re : proba : des boules et des paires

    Citation Envoyé par Tryss Voir le message
    Je pense qu'il n'y a pas de formule simple pour calculer cette probabilité (avec des coefficients binomiaux, des puissances...)

    Sinon par la méthode de Monte-Carlo, je trouve que la probabilité de n'avoir aucune paire valide est a peu près constante quelque soit le nombre de boules (pour un nombre de boules assez grand) et qu'elle vaut environ 36%. Quelqu'un peut confirmer ce résultats?
    oui, pour la convergence.
    car si la proba P(n) est celle de n'avoir aucune paire valide.
    alors au rang n+1 , ( sachant qu'au rang P : aucune paire ) on ajoute une toute petite possibilité d'avoir une paire miraculeuse.
    soit
    avec les paires 2n;2n+1 soit 2n+1;2n+2,
    estimation rapide ( à vérifier ) cette possiblité est certainement en k/n² avec k pas calculé mais probablement indépendant de n ( pour n grand bien sur )
    donc P(n+1)=P(n)*(1-k/n²)
    de toute façon P(n) est strictement décroissante et minorée donc convergente.
    (même si on est en 1/n et pas selon moi en 1/n²)

    par contre, d'ou vient ton 36%, tu as fais une petite simulation informatique avec par ex n=10 ?
    Dernière modification par ansset ; 20/11/2011 à 20h17.

  15. #14
    Tryss

    Re : proba : des boules et des paires

    Yup, simulation informatique.

    Voici le code (en C) :
     Cliquez pour afficher


    Sur 10 millions de tirages, on a :
    Pour n = 3, on est à 33.3% (la valeur exacte est 1/3)
    Pour n = 10, on est à 34.8% (la valeur exacte est 47/135)
    Pour n = 20, on est à 35.8%
    Pour n = 50, on est à 36.4%
    Pour n = 100, on est à 36.6%
    Pour n = 250, on est à 36.7%

    Après ça commence à prendre un peu de temps (même si l'algo est en O(n*tirages) )

  16. #15
    zyket

    Re : proba : des boules et des paires

    Je suis content

    donner du fil à retordre à plus calé que vous est toujours un petit moment de plaisir

    Si je comprends bien : la probabilité, que j'ai noté , de tirer une série de boules numérotées parmi n numéros, ne comportant aucun couple de boules comportant 2 numéros consécutifs, tend vers une limite (dixit ansset) qui semble proche de 37% (dixit Tryss) quand n tend vers un nombre très grand.

    En conséquence la probabilité de tirer une série de n boules comportant au moins un CDBC2NC serait de : 1-36%=64%

    Maintenant, puisque je tiens des esprits forts sous la main, j'ose profiter de la situation pour corser mon problème.

    La deuxième phase de ma manip consiste à remplacer chaque CDBC2NC de ma série par une unique boule sur laquelle on marque les numéros consécutifs.

    Je remets le tout dans l'urne qui comporte donc des boules avec un numéro et éventuellement (avec une proba de 64%) au moins 1 boule comportant 2 numéros consécutifs. Je retire une série de n-(nombre de couples) boules que je dispose par paires comme dans mon premier post.

    Je réitère la phase (la deuxième) qui consiste à remplacer chaque CDBCdesNC par une unique boule. Par exemple : je tire la boule unique qui avait remplacé le couple 2;3 et ensuite je tire la boule 4. Je remplace ce couple par l'unique boule (2;3;4)
    De plus si par chance un couple du type (boule unique (5;6); boule unique (7;8)), par exemple, se forme, ce couple est remplacé par la boule unique (5;6;7;8)

    Dans ces conditions, si je mets 1 seconde pour tirer une série de boules, au bout de combien de temps puis-je espérer constituer la boule (1;2;3;.....;n-1;n) ?

    Je compte sur vous, car à mon grand désespoir je ne sais pas programmer.

  17. #16
    ansset
    Animateur Mathématiques

    Re : proba : des boules et des paires

    pardon tryss, j'ai du mal à comprendre pourquoi P(n) serait croissante ?
    c'est même contre-intuitif pour moi.
    ( p(2) par exemple vaut 10/24 ).
    Dernière modification par ansset ; 21/11/2011 à 11h13.

  18. #17
    Tryss

    Re : proba : des boules et des paires

    Heu non, p(2) (ce que j’appelai p(4)) vaut 1/3. voici les 3 cas possibles (à une permutation près des couples et de l'ordre des couples) :
    (1,2)(3,4) : non
    (1,3)(2,4) : oui
    (1,4)(2,3) : non

    p(3) vaut 1/3 aussi (avec 15 cas différents):
     Cliquez pour afficher


    p(4) vaut 12/35 (avec 105 cas différents):
     Cliquez pour afficher


    La probabilité n'est donc pas décroissante.


    Sinon Zyket, je m'attelle à ton problème, cependant il y a un point flou : quand le nombre de boules n'est pas pair, que se passe t'il pour la dernière boule? On l'oublie?

  19. #18
    ansset
    Animateur Mathématiques

    Re : proba : des boules et des paires

    Citation Envoyé par Tryss Voir le message
    Heu non, p(2) (ce que j’appelai p(4)) vaut 1/3. voici les 3 cas possibles (à une permutation près des couples et de l'ordre des couples) :
    (1,2)(3,4) : non
    (1,3)(2,4) : oui
    (1,4)(2,3) : non
    il y a 2n! suites de nb possibles
    et sur les 24, 10 ne sont pas bons ( au sens pas de solution de paire admissible )
    ça se fait à la main d'ailleurs.
    il faut revoir ton algorithme.
    Dernière modification par ansset ; 21/11/2011 à 16h26.

  20. #19
    Tryss

    Re : proba : des boules et des paires

    Huh... voici les 24 suites avec les 8 suites qui ne contiennent pas de paire valable :

     Cliquez pour afficher

    Quelles sont les 2 autres suites qui ne contiennent pas de paires valables ?

  21. #20
    ansset
    Animateur Mathématiques

    Re : proba : des boules et des paires

    j'ai rien dis,
    suis allé trop vite !

  22. #21
    ansset
    Animateur Mathématiques

    Re : proba : des boules et des paires

    bonjour zytnet, Tryss, bonjour tous.
    j'y revient parceque j'aime bien les casse-tête !
    dans un message précédent, j'ai cru montrer que P(n) était décroissante.
    ( grosse faute )si l'on en crois l'algo de Tryss, pour lequel je n'ai pas vu d'erreur.
    en revanche, j'ai compris la miènne et ça me permet d'avancer un peu.

    mon erreur fatale fut de considérer qu'une paire 2n+1,2n+2 pouvait permettre de rajouter une paire valide.
    ce qui est juste et calculable.
    MAIS
    en revanche ( moi qui fut parmi ceux qui ont dénoncé le caractère infernale de la combinatoire ( shame on me )), j'ai oublié de tenir compte du fait que l'introduction des boule (2n+1 et 2n+2) par exemple au rang k, et l de la suite perturbait toute la suite des couples suivant ( sauf si 2n+1;2n+2 sont collés dans la même paire ).
    ce qui me trotte c'est donc qu'il y a plus de chance de casser au moins un couple que d'en creer un neuf !!!! simplement en déplaçant d'un (demi)rang le reste.
    puisque Tryss montre que la suite est croissante pour P(n).
    j'essaye de voir si cela est démontrable !
    bref , maintenant que l'on a une idée de la convergence, j'aimerai pouvoir au moins l'encadrer au plus prèt.
    je sais, je sais, suis maso de nature.
    Dernière modification par ansset ; 22/11/2011 à 11h21.

  23. #22
    zyket

    Re : proba : des boules et des paires

    Bonjour à tous,

    je suis avec attention toutes vos recherches et essaye d'en comprendre quelques bribes.

    J'essaye de comprendre la démarche d'anssett qui cherche, si j'ai bien compris, à partir d'un rang n pair, à voir comment ''l'injection'' de deux numéros consécutifs perturbe la série de couples possibles. A priori, une fois les deux nouveaux numéros insérer, à part les couples limitrophes des ces nouvelles boules les autres couples ne devraient pas être perturbés, non ?

  24. #23
    ansset
    Animateur Mathématiques

    Re : proba : des boules et des paires

    non, malheureusement, pas uniquement les couples limitrophes.
    effectivement, si un nouveau numéro se mele au milieu d'une liste, alors toute la suite suivante est "décalé" donc à revoir.
    Dernière modification par ansset ; 22/11/2011 à 18h58.

  25. #24
    zyket

    Re : proba : des boules et des paires

    En effet, donc l'effet de la ''pertubation'' dépend de ''l'écart'' entre les deux boules insérées. Ou dit d'une autre façon : seule la liste de numéros compris entre ces deux boules est perturbée, n'est-ce pas ?

  26. #25
    ansset
    Animateur Mathématiques

    Re : proba : des boules et des paires

    c'est ce qu'il me semble, sauf, si les 2 forment une paire soudée bien calée au milieu ( prob très faible )

  27. #26
    Tryss

    Re : proba : des boules et des paires

    Sinon pour ton second problème zyket, je trouve que l'espérance du nombre de tirages en partant de n boules est grosso-modo égale à n (si tu as moins de 200 boules c'est compris entre n-1 et n+1).

    Calcul exact pour n=4:

    Lorsque l'on a 4 boules , on a :
    1/3 de passer à 2 boules (tirage (1,2)(3,4) )
    1/3 de passer à 3 boules (tirage (1,4)(2,3) )
    1/3 de rester à 4 boules (tirage (1,3)(2,4) )

    Lorsque l'on a 3 boules, on a :
    2/3 de passer à 2 boules (tirages (1,2-3)(4) et (2-3,4)(1) )
    1/3 de rester à 3 boules (tirage (1,4)(2-3) )

    Lorsqu'il ne reste que 2 boules, on passe nécessairement à 1 boule au coup d'après


    Pour arriver a 1 boule en exactement n coups, il y a 2 types de chemins : ceux qui passent par 3 et ceux qui ne passent pas par 3.
    a) Si on ne passe pas par 3, alors il faut rester n-2 fois en 4 puis aller en 2. La probabilité d'un tel chemin est alors de :

    b) Si on passe par 3, on reste k fois en 4 avant de passer en 3 et ça détermine complètement le chemin. La probabilité d'un tel chemin est alors de :

    De plus il y en a n-2 différents.

    La probabilité d'arriver à 1 boule en exactement n coups est alors de :


    L'espérance du nombre de coups est donc égale à :



    Par simulation j'obtiens les résultats suivants :
     Cliquez pour afficher


    Et le code (un peu plus long, vu que c'est plus compliqué à simuler) :
     Cliquez pour afficher

  28. #27
    zyket

    Re : proba : des boules et des paires

    Merci beaucoup, je me plonge dans tes démonstrations et vais tenter de les comprendre.

  29. #28
    zyket

    Re : proba : des boules et des paires

    Grâce à un arbre de proba je crois avoir bien compris le point a) et te crois volontiers pour le point b) (surtout pour n-2 chemins possibles ??)

    Je constate quelque chose de sûrement trivial en écrivant la proba des deux types de chemins possibles :

    a) En ne passant pas par 3 boules, la probabilité d'un tel chemin est comme tu l'écris de qu'on peut écrire qui fait apparaître la probabilité de toutes les branches du chemin (même la dernière qui vaut 1). L'addition des exposants de tous les facteurs de ce produit nous donne bien le nombre de coups.

    b) Idem pour la formule en passant par 3 boules

    Mais comme je l'annonçai c'est trivial.

    Par contre quelque chose qui est moins trivial pour moi, c'est la notion d'espérance en proba. Mes années d'études sont loin derrière moi et un petit rappel me ferait du bien pour que je puisse comprendre le début et en fait le propos du post.

    Merci

  30. #29
    ansset
    Animateur Mathématiques

    Re : proba : des boules et des paires

    pour le premier, je laisse tomber,
    même d'essayer de passer de n à n+1 donne une combinatoire digne d'un camion de doliprane

  31. #30
    invite91724928

    Re : proba : des boules et des paires

    Salut à vous,
    Je crois qu'il existe une formule pour calculer cette probabilité, déjà on a une information sur le nombre de tous les cas possibles, si j'arrive à un résultat correct je le posterai.

Page 1 sur 2 1 DernièreDernière

Discussions similaires

  1. Des boules, des tores et des cylindres
    Par Médiat dans le forum Science ludique : la science en s'amusant
    Réponses: 15
    Dernier message: 19/05/2011, 19h42
  2. exercice proba boules
    Par invite05f200e5 dans le forum Mathématiques du collège et du lycée
    Réponses: 1
    Dernier message: 22/04/2009, 19h29
  3. Proba: une boite contenant N boules
    Par invitee9380279 dans le forum Mathématiques du collège et du lycée
    Réponses: 5
    Dernier message: 11/08/2008, 17h17