proba : des boules et des paires

[zyket]

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
-----

[zyket]

un petit up

[invitea3eb043e]

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.

[danyvio]

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 C²_2p façons de tirer un couple quelconque.

[A voir en vidéo sur Futura]

[zyket]

Merci,

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

[invite51d17075]

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

[danyvio]

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....

[invite51d17075]

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 !

[zyket]

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 ...

[invite51d17075]

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.

[zyket]

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

[inviteea028771]

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?

[invite51d17075]

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 ?

[inviteea028771]

Yup, simulation informatique.

Voici le code (en C) :

 Cliquez pour afficher

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main()
{
    int size, number, count, n, i;
    int * list;
    srand(time(NULL));

    printf("Taille : ");
    scanf("%d",&size);
    printf("Nombre de tirages : ");
    scanf("%d",&number);

    list = malloc(size * sizeof(int) );
    for (i=0;i<size; i++)
    {
        list[i] = i+1;
    }

    count = 0;

    for (n=0; n<number; n++)
    {
        for(i=size-1;i>0;i--)
        {
            int j = (RAND_MAX-rand())/((double)RAND_MAX+1)*(i+1);
            int tmp = list[j];
            list[j] = list[i];
            list[i] = tmp;
        }

        for(i=0; i<size; i+=2)
        {
            if (list[i] == list[i+1]+1 || list[i] == list[i+1]-1)
            {
                count++;
                break;
            }
        }
    }

    printf("Valeurs : %d / %d\n", number-count, number);
    printf("Proba : %f", 1-(double)count/number);

    return 0;
}

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) )

[zyket]

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.

[invite51d17075]

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 ).

[inviteea028771]

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

(1,2)(3,4)(5,6) : non
(1,2)(3,5)(4,6) : non
(1,2)(3,6)(4,5) : non
(1,3)(2,4)(5,6) : non
(1,3)(2,5)(4,6) : oui
(1,3)(2,6)(4,5) : non
(1,4)(2,3)(5,6) : non
(1,4)(2,5)(3,6) : oui
(1,4)(2,6)(3,5) : oui
(1,5)(2,3)(4,6) : non
(1,5)(2,4)(3,6) : oui
(1,5)(2,6)(3,4) : non
(1,6)(2,3)(4,5) : non
(1,6)(2,4)(3,5) : oui
(1,6)(2,5)(3,4) : non

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

 Cliquez pour afficher

(1,2)(3,4)(5,6)(7,8) : non
(1,2)(3,4)(5,7)(6,8) : non
(1,2)(3,4)(5,8)(6,7) : non
(1,2)(3,5)(4,6)(7,8) : non
(1,2)(3,5)(4,7)(6,8) : non
(1,2)(3,5)(4,8)(6,7) : non
(1,2)(3,6)(4,5)(7,8) : non
(1,2)(3,6)(4,7)(5,8) : non
(1,2)(3,6)(4,8)(5,7) : non
(1,2)(3,7)(4,5)(6,8) : non
(1,2)(3,7)(4,6)(5,8) : non
(1,2)(3,7)(4,8)(5,6) : non
(1,2)(3,8)(4,5)(6,7) : non
(1,2)(3,8)(4,6)(5,7) : non
(1,2)(3,8)(4,7)(5,6) : non
(1,3)(2,4)(5,6)(7,8) : non
(1,3)(2,4)(5,7)(6,8) : oui 1
(1,3)(2,4)(5,8)(6,7) : non
(1,3)(2,5)(4,6)(7,8) : non
(1,3)(2,5)(4,7)(6,8) : oui 2
(1,3)(2,5)(4,8)(6,7) : non
(1,3)(2,6)(4,5)(7,8) : non
(1,3)(2,6)(4,7)(5,8) : oui 3
(1,3)(2,6)(4,8)(5,7) : oui 4
(1,3)(2,7)(4,5)(6,8) : non
(1,3)(2,7)(4,6)(5,8) : oui 5
(1,3)(2,7)(4,8)(5,6) : non
(1,3)(2,8)(4,5)(6,7) : non
(1,3)(2,8)(4,6)(5,7) : oui 6
(1,3)(2,8)(4,7)(5,6) : non
(1,4)(2,3)(5,6)(7,8) : non
(1,4)(2,3)(5,7)(6,8) : non
(1,4)(2,3)(5,8)(6,7) : non
(1,4)(2,5)(3,6)(7,8) : non
(1,4)(2,5)(3,7)(6,8) : oui 7
(1,4)(2,5)(3,8)(6,7) : non
(1,4)(2,6)(3,5)(7,8) : non
(1,4)(2,6)(3,7)(5,8) : oui 8
(1,4)(2,6)(3,8)(5,7) : oui 9
(1,4)(2,7)(3,5)(6,8) : oui 10
(1,4)(2,7)(3,6)(5,8) : oui 11
(1,4)(2,7)(3,8)(5,6) : non
(1,4)(2,8)(3,5)(6,7) : non
(1,4)(2,8)(3,6)(5,7) : oui 12
(1,4)(2,8)(3,7)(5,6) : non
(1,5)(2,3)(4,6)(7,8) : non
(1,5)(2,3)(4,7)(6,8) : non
(1,5)(2,3)(4,8)(6,7) : non
(1,5)(2,4)(3,6)(7,8) : non
(1,5)(2,4)(3,7)(6,8) : oui 13
(1,5)(2,4)(3,8)(6,7) : non
(1,5)(2,6)(3,4)(7,8) : non
(1,5)(2,6)(3,7)(4,8) : oui 14
(1,5)(2,6)(3,8)(4,7) : oui 15
(1,5)(2,7)(3,4)(6,8) : non
(1,5)(2,7)(3,6)(4,8) : oui 16
(1,5)(2,7)(3,8)(4,6) : oui 17
(1,5)(2,8)(3,4)(6,7) : non
(1,5)(2,8)(3,6)(4,7) : oui 18
(1,5)(2,8)(3,7)(4,6) : oui 19
(1,6)(2,3)(4,5)(7,8) : non
(1,6)(2,3)(4,7)(5,8) : non
(1,6)(2,3)(4,8)(5,7) : non
(1,6)(2,4)(3,5)(7,8) : non
(1,6)(2,4)(3,7)(5,8) : oui 20
(1,6)(2,4)(3,8)(5,7) : oui 21
(1,6)(2,5)(3,4)(7,8) : non
(1,6)(2,5)(3,7)(4,8) : oui 22
(1,6)(2,5)(3,8)(4,7) : oui 23
(1,6)(2,7)(3,4)(5,8) : non
(1,6)(2,7)(3,5)(4,8) : oui 24
(1,6)(2,7)(3,8)(4,5) : non
(1,6)(2,8)(3,4)(5,7) : non
(1,6)(2,8)(3,5)(4,7) : oui 25
(1,6)(2,8)(3,7)(4,5) : non
(1,7)(2,3)(4,5)(6,8) : non
(1,7)(2,3)(4,6)(5,8) : non
(1,7)(2,3)(4,8)(5,6) : non
(1,7)(2,4)(3,5)(6,8) : oui 26
(1,7)(2,4)(3,6)(5,8) : oui 27
(1,7)(2,4)(3,8)(5,6) : non
(1,7)(2,5)(3,4)(6,8) : non
(1,7)(2,5)(3,6)(4,8) : oui 28
(1,7)(2,5)(3,8)(4,6) : oui 29
(1,7)(2,6)(3,4)(5,8) : non
(1,7)(2,6)(3,5)(4,8) : oui 30
(1,7)(2,6)(3,8)(4,5) : non
(1,7)(2,8)(3,4)(5,6) : non
(1,7)(2,8)(3,5)(4,6) : oui 31
(1,7)(2,8)(3,6)(4,5) : non
(1,8)(2,3)(4,5)(6,7) : non
(1,8)(2,3)(4,6)(5,7) : non
(1,8)(2,3)(4,7)(5,6) : non
(1,8)(2,4)(3,5)(6,7) : non
(1,8)(2,4)(3,6)(5,7) : oui 32
(1,8)(2,4)(3,7)(5,6) : non
(1,8)(2,5)(3,4)(6,7) : non
(1,8)(2,5)(3,6)(4,7) : oui 33
(1,8)(2,5)(3,7)(4,6) : oui 34
(1,8)(2,6)(3,4)(5,7) : non
(1,8)(2,6)(3,5)(4,7) : oui 35
(1,8)(2,6)(3,7)(4,5) : non
(1,8)(2,7)(3,4)(5,6) : non
(1,8)(2,7)(3,5)(4,6) : oui 36
(1,8)(2,7)(3,6)(4,5) : non

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?

[invite51d17075]

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.

[inviteea028771]

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

 Cliquez pour afficher

(1,2)(3,4) non
(1,2)(4,3) non
(1,3)(2,4) oui
(1,3)(4,2) oui
(1,4)(2,3) non
(1,4)(3,2) non
(2,1)(3,4) non
(2,1)(4,3) non
(2,3)(1,4) non
(2,3)(4,1) non
(2,4)(1,3) oui
(2,4)(3,1) oui
(3,1)(2,4) oui
(3,1)(4,2) oui
(3,2)(1,4) non
(3,2)(4,1) non
(3,4)(1,2) non
(3,4)(2,1) non
(4,1)(2,3) non
(4,1)(3,2) non
(4,2)(1,3) oui
(4,2)(3,1) oui
(4,3)(1,2) non
(4,3)(2,1) non

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

[invite51d17075]

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

[invite51d17075]

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.

[zyket]

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 ?

[invite51d17075]

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.

[zyket]

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 ?

[invite51d17075]

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 )

[inviteea028771]

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

Nombre de tirages : 10000
2       :       1.000000
3       :       2.504800
4       :       3.255000
5       :       4.668300
6       :       5.523400
7       :       6.821100
8       :       7.704300
9       :       8.867800
10      :       9.793700
11      :       10.960000
12      :       11.989800
13      :       13.086300
14      :       13.997300
15      :       15.101900
16      :       16.056200
17      :       17.177500
18      :       18.120200
19      :       19.220400
20      :       20.241000
21      :       21.261300
22      :       22.217500
23      :       23.240300
24      :       24.234800
25      :       25.333500
26      :       26.312100
27      :       27.318800
28      :       28.358100
29      :       29.526500
30      :       30.287600
31      :       31.466200
32      :       32.455200
33      :       33.522600
34      :       34.267000
35      :       35.457400
36      :       36.521000
37      :       37.511100
38      :       38.431900
39      :       39.559900
40      :       40.511100
41      :       41.592700
42      :       42.606400
43      :       43.591200
44      :       44.505600
45      :       45.568600
46      :       46.496000
47      :       47.601700
48      :       48.599300
49      :       49.624800
50      :       50.641900
51      :       51.572800
52      :       52.617400
53      :       53.760600
54      :       54.624100
55      :       55.619900
56      :       56.716800
57      :       57.699100
58      :       58.685800
59      :       59.773800
60      :       60.797500
61      :       61.721400
62      :       62.854800
63      :       63.895600
64      :       64.740600
65      :       65.869400
66      :       66.728400
67      :       67.763700
68      :       68.882600
69      :       69.854100
70      :       70.915300
71      :       71.902600
72      :       72.786100
73      :       73.857600
74      :       74.847600
75      :       75.866700
76      :       76.877800
77      :       77.999400
78      :       78.890300
79      :       79.953800
80      :       80.780700
81      :       81.877600
82      :       82.968700
83      :       83.899400
84      :       84.934300
85      :       85.926800
86      :       87.011400
87      :       87.706600
88      :       88.868200
89      :       89.912500
90      :       90.949300
91      :       92.036200
92      :       92.916700
93      :       94.006300
94      :       94.889300
95      :       96.135500
96      :       96.937500
97      :       97.840200
98      :       98.794000
99      :       99.981800

Process returned 0 (0x0)   execution time : 86.998 s
Press any key to continue.

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

 Cliquez pour afficher

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef struct
{
    int debut, fin;
} Boule;

void swap( Boule * boule1, Boule * boule2 )
{
    int a,b;
    a = boule1->debut;
    b = boule1->fin;
    boule1->debut = boule2->debut;
    boule1->fin = boule2->fin;
    boule2->debut = a;
    boule2->fin = b;
}

int contigu( Boule * boule1, Boule * boule2)
{
    return boule1->debut == boule2->fin + 1 || boule2->debut == boule1->fin + 1;
}

Boule * init(int size)
{
    int i;
    Boule * list = malloc(size * sizeof(Boule));
    for (i=0; i<size; i++)
    {
        list[i].debut = i+1;
        list[i].fin = i+1;
    }
    return list;
}

int MC2(int size, int number)
{
    int count, n, i, j, lenght;
    Boule * list;
    count = 0;

    for (n=0; n<number; n++)
    {
        list = init(size);
        lenght = size;

        while( lenght > 1 )
        {

            for(i=lenght-1; i>0; i--)
            {
                int j = (RAND_MAX-rand())/((double)RAND_MAX+1)*(i+1);
                swap(&list[i], &list[j]);
            }

            int t = 0;
            for(i=0; i+1<lenght; i+=2)
            {
                if (contigu( &list[i], &list[i+1] ))
                {
                    if (list[i].debut == list[i+1].fin + 1)
                    {
                        list[i].debut = list[i+1].debut;
                    }
                    else
                    {
                        list[i].fin = list[i+1].fin;
                    }

                    for (j=i+2; j<lenght; j++)
                    {
                        list[j-1]=list[j];
                    }
                    i--;
                    t++;
                }
            }
            lenght-=t;
            count++;
        }
        free(list);
    }
    return count;
}

int main(void)
{
    int size, number;

    srand(time(NULL));

    printf("Nombre de tirages : ");
    scanf("%d",&number);

    for ( size=2; size<100; size++)
    {
        count = MC2(size, number);
        printf("%d\t:\t%f\n", size, (double)count/number );
    }

    return 0;
}

[zyket]

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

[zyket]

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

[invite51d17075]

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

[invitedf478b73]

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.