Étrange phénomène probabiliste

[amine2684]

Bonjour !
Voilà , j'ai fais une petite expérience sur PC , le résultat m'a quelque peu surpris !
j'ai écris une procédure qui génère des listes de taille aléatoire inférieur à 100 000 d'entiers aléatoires aussi inférieurs à 100 000 .
Puis j'ai écris un petit programme qui cherche si x appartient à une liste générée aléatoirement ;
et enfin un dernier qui compte au bout de combien de listes aléatoires générées , l'entier x apparait dans l'une d'elles .

J'ai fais l'expérience 8 fois et voici les résultats :
165405
164884
165361
165461
165452
165423
165094
165394

Ça tourne toujours autours de 165 000 !! alors que les listes sont aléatoires !!
Quelqu'un aurait une explication ?

P.S : j'utilise Caml light comme langage de programmation .
-----

[amine2684]

Et pour ceux qui veulent le code , le voilà :


(* générateur aléatoire de liste de taille au max N dont les valeurs sont inf à p *)
let liste N p=
let i = ref (random__int N) and l = ref [] in
while !i >= 0 do
l := (random__int p) :: !l ; i := !i-1 done ;
!l ;;

(*tri fusion sur liste*)
let rec decoupe = fun
|[] -> ([] , [] )
|[a] -> ([a] , [] )
|(a::b::l) -> let d = decoupe l in ( a:: (fst d) , b:: (snd d)) ;;

let rec fusionne = fun
| l [] -> l
| [] l -> l
| (a::l) (b::v) when a <= b -> a :: (fusionne l (b::v) )
| (a::l) (b::v) -> b :: ( fusionne (a::l) v) ;;

let rec tri l =
match l with
| [] -> []
| [a] -> [a]
| [a;b] when a <= b -> [a;b]
| [a;b] -> [b;a]
| l ->
let L = decoupe l in
fusionne (tri (fst L)) (tri (snd L)) ;;

(*recherche dichotomique dans une liste triée*)
let rec dico x = function
|[] -> false
|[a] when a <> x -> false
| [a] when a = x -> true
| l -> let (l1,l2) = decoupe l in (dico x l1) or (dico x l2) ;;

(* test si une valeur x est présente dans une liste aléatoire tq N = 100000 et p = 100000*)
let test =
let l = liste 100000 100000 in
let t = tri l in
dico 777 (*c'est lui x *) t ;;

(* compte au bout de combien de listes générées on trouve x *)
let combien =
let i = ref 0 in
while not test do begin i := !i + 1 ; print_int !i ; print_string " " end ;done ;
!i ;;

[invite986312212]

salut,

quelle est la loi de la taille d'une liste? et comment remplis-tu une liste aléatoire? (désolé je ne sais pas lire ton code)

[God's Breath]

j'ai écris une procédure qui génère des listes de taille aléatoire inférieur à 100 000

Bonjour ambrosio,

Si j'ai bien compris, la taille des listes est aléatoire.

[A voir en vidéo sur Futura]

[invite986312212]

quoi qu'il en soit je pense qu'il doit s'agir d'une erreur de programmation. Le langage est trop exotique pour moi pour que je puisse voir où elle se situe, mais je fais le raisonnement suivant: si tes expériences (tirer une liste aléatoire et vérifier si un nombre donné s'y trouve) sont indépendantes et de même loi, alors le nombre d'essais avant un succès (le nombre est dans la liste) doit suivre la loi exponentielle de moyenne l'inverse de la probabilité pour ce nombre de se trouver dans la liste. Au passage, on voit que cette probabilité serait autour de 1/165000, ce qui est très petit (donc tes listes très courtes en moyenne, moins de 1 je pense). Mais surtout, la variance de la loi exponentielle est telle que tu ne pourrais tomber 8 fois de suite sur des nombres si proches.

[amine2684]

Oui la taille des listes est aléatoire inférieure à 100 000 . (Tiens je devrais faire des expériences en faisant varier ce 100 000 pour voir ce que ça donne )

le nombre d'essais avant un succès (le nombre est dans la liste) doit suivre la loi exponentielle de moyenne l'inverse de la probabilité pour ce nombre de se trouver dans la liste.

Ambrosio , désolé pour mon manque de culture dans le domaine , mais c'est quoi cette loi exponentielle ?
Au passage ,je suis en classes prepas MP et je trouve vraiment dommage que les probabilités soient complétement absentes de notre programme !

[invited4aa25f8]

Il faut se méfier avec les générateurs pseudo-aléatoires des langages.
A une échelle statistique, on a facilement ce genre d'aberrations qui apparaissent.

Je ne connais pas le générateurs de ton language, mais ils ont tous les mêmes défauts en général. Je t'ai trouvé une excellent explication ici
http://www.alrj.org/docs/algo/random.php

[invite986312212]

Ambrosio , désolé pour mon manque de culture dans le domaine , mais c'est quoi cette loi exponentielle ?

désolé je m'ai gourré, je voulais parler de la loi géométrique (ou de Pascal). La loi exponentielle en est en quelque sorte la version continue. La loi géométrique, c'est la loi du nombre d'échecs observés avant d'obtenir un succès, dans une suite d'expériences aléatoires conduisant soit à un succès soit à un échec, indépendantes et de même loi. Par exemple dans une suite de jeu de pile ou face, si on appelle succès l'obtention de face, c'est le nombre de résultats pile avant le premier résultat face. Ce nombre peut être nul et il n'y a pas de borne supérieure. Si la probabilité du succès à chaque expérience est p, on montre facilement que la probabilité de k échecs est p(1-p)^k.

[S321]

Bonsoir.
En tant qu'utilisateur de Caml je dois vous avertir que votre programme ne fonctionne pas. Je veux dire que le code que vous nous fournissez est bugué (et très inesthétique mais j'y reviendrai ^^), votre fonction "combien" tente d'afficher des centaines de milliers de nombres. En fait elle affiche tous les nombres entre 1 et 165000, elle s'arrête ensuite car il n'y a alors tous simplement plus de place dans l'afficheur pour écrire un caractère de plus.

Je vais reprendre vos programmes un par un en passant en revu chaque détail. J'espère que ça pourra vous être profitable.

La fonction liste est l'exemple typique de la mauvaise utilisation de Caml. Ce n'est pas un langage impératif et ça fait mauvais genre de l'utiliser comme tel. Ne jamais, au grand jamais, faire de référence sur des listes. Vous pouvez très bien faire le même programme de manière récursive, je vous propose par exemple ceci (avec une fonction interne qui permet de faciliter la gestion des arguments de la fonction) :
let liste N p= let i = (random__int N) in
let rec interne = fun
|0 l->l
|n l-> interne (n-1) ((random__int p)::l)
in interne i [];;

Pour la fonction decoupe, elle fonctionne tout à fait mais je trouve juste dommage d'écrire "let d= decoupe l". d sera alors un couple et vous avez besoin d'utiliser les fonction fst et snd pour accéder à chacun de ses éléments. Autant écrire directement "let (c,d)=decoupe l". Ça vous facilitera d'autant plus la vie lorsque vous travaillerez avec des triplets .

Dans la fonction tri, les lignes
"| [a;b] when a <= b -> [a;b]
| [a;b] -> [b;a]"
sont superfétatoires. Le cas d'une liste à deux éléments est déjà gérée par la dernière ligne. Elle sera coupée en deux listes d'un élément qui seront alors fusionnées en une liste ordonnées, aucun problème.

Là on commence à arriver aux véritables problèmes de votre programme. Votre recherche dichotomique est fausse. Non seulement il y a un h au "dicho" de "dichotomie", mais vous ne vous servez pas du fait que vous coupez votre liste en deux.
Vous coupez effectivement la liste en deux, mais vous faites la recherche dans chacune des deux parties.

L'intérêt de travailler avec des listes triées est que vous n'avez pas besoin de parcourir toute la liste pour faire une recherche dedans.
Dans votre cas vous n'auriez pas besoin d'avoir recours à tous ses artifice, vous ne faite qu'une seule recherche dans chacune de vos listes. Vous perdez plus de temps à les trier que vous n'en gagnez en accélérant la recherche (et encore faudrait-il que vous accélériez vraiment votre recherche).

La recherche dichotomique n'est pas adaptée à la structure de liste car il est difficile de faire une bonne fonction de découpe (la votre ne convient pas).
Le principe est de couper votre liste en deux parties de même tailles. La sous-liste "gauche" contient les plus petits éléments de la listes et la sous-liste "droite" contient les plus grand. Si x est plus grand que le premier élément de la liste droite alors il ne peut pas être dans la liste gauche et donc il suffit de limiter la recherche à la partie droite de la liste.
Inversement si x est strictement plus petit que le premier élément de la liste droite on peut limiter la recherche à la partie gauche.

Lorsqu'on travail avec des listes triées, pour construire ces sous-listes gauche et droite, il suffit de couper la liste originelle au milieu. Mais il est très difficile de trouver le milieu d'une liste, la structure n'est pas du tout adaptée (et l'opération est gourmande en temps de calcul). C'est pourquoi on ne fait jamais de recherche dichotomique sur des listes, plutôt sur des tableaux.

En fait, vous pouvez tout supprimer à partir de (*tri fusion*) et remplacer simplement par un programme du genre :
let rec recherche x= function
|[]->false
|t::q when t=x-> true
|t::q-> recherche x q;;

Ensuite on peut récrire la fonction test bien plus simplement car il n'y a plus besoin de faire de tri :
let test =
let l = liste 100000 100000 in
recherche 777 l ;;
Je souligne au passage qu'avec cette version du programme les opérations s'effectuent quasi instantanément ce qui n'était pas le cas avec votre version ^^.

Voici donc maintenant la version finale de la fonction "combien". Je l'écris sous forme récursive car j'évite autant que possible les programmes en impératif.
let combien =
let rec aux i =function
|true -> i
|false -> let l= liste 10000 10000 in aux (i+1) (recherche 777 l)
in aux 1 test;;

Vous remarquerez que je n'ai pas écris "|false ->aux (i+1) test". C'est à cause de cette erreur que votre programme bouclait. Caml ne réévalue pas test. Pour Caml "test" est un booléen et il en a déjà calculé la valeur qu'il conserve en mémoire. Même si cette valeur résulte d'une expérience aléatoire, ce n'est pas son problème.

On trouve rarement plus de 10 comme résultat ce qui me semble un peu plus correcte que vos valeurs ^^.

En espérant avoir pu vous aider.

[amine2684]

Merci S321 pour ton analyse détaillée sur le code. Je sais qu'il faut de la patience pour lire en détail un code et le corriger , je t'en suis reconnaissant : ça m'a aidé de voir mes erreurs de codage .
J'ai rectifié ce que tu m'as dis et t'as raison ca dépasse rarement 10 ce qui est plus rassurant
Puis pour le tri dichotomique , c'est vrai que sur des listes c'est pas top !
Merci pour tout tes précieux conseils