"Francois Grieu" a écrit dans le message de news:
"Acetonik" a écrit:j'ajoute qu'il y a 110 375 347 398 090 219 solutions entieres positives
En réalité il faut envisager encore bien plus de 16-uplets pour ne retenir
que les solutions qui conviennent même si l'on peut forcer quelques boucles
à se terminer sous certaines conditions ....
- on peut se restreindre aux solutions avec M1>=M2>=M3..>=M16, ce qui
gagne 13 ordres de grandeur;
Oui, mais il faut alors tester le nombre de répétions des Mj (et
ces test prennent du temps!!)
on obtient par exemple: en tenant compte de l'ordre:
avec ordre w1=(28,10,10,5,5,5,5,2,2,2,1,1,1,1,1,1)
p(w1)== 80! / (28!10!10!5!5!5!5!2!2!2!1!1!1!1!1.1!)*( 1/16)^80
et
sans ordre w2={28,10,10,5,5,5,5,2,2,2,1,1,1,1,1,1}
p(w2)== 16!/ (1!2!4!3!6!)*p(w1)
- et on n'est intéressé que par les solutions qui donnent X>65, ce qui
gagne encore 6 ordres de grandeur
Oui mais il faut trier les (m1,m2,....m16) qui donnent X>65 de façon
efficace...
Toujours pour K, j'obtiens P(X>65) en valeur exacte, pour les valeurs :
N= 3,4,5,6,7,8,9,10,11,12,13 ( en moins de 2 heures pour N).
Le temps de calcul est en gros multiplié par 2 à chaque valeur suivante de N
par exemple:
N p(X>65) 887189 / 4398046511104 = 4,749196933*10^-6
N p(X>65)8098927 / 35184372088832 = 3,925007576*10^-6
Il semble bien qu'il soit impossible d'envisager d'aller jusqu'à N...
(cela me rappelle un peu le problème des grains de blé sur l'échiquier)
Je serais d'ailleurs curieux de savoir jusqu'à quelle valeur de N vous
pouvez aller en un temps raisonnable, disons en gros 2 heures , sachant que
cela dépend bien sûr des processeurs (1733Mhz pour moi)
"Francois Grieu" <fgrieu@gmail.com> a écrit dans le message de news:
17e5f820-1eda-408b-ae46-c90be3b0d5fd@u29g2000pro.googlegroups.com...
"Acetonik" a écrit:
j'ajoute qu'il y a 110 375 347 398 090 219 solutions entieres positives
En réalité il faut envisager encore bien plus de 16-uplets pour ne retenir
que les solutions qui conviennent même si l'on peut forcer quelques boucles
à se terminer sous certaines conditions ....
- on peut se restreindre aux solutions avec M1>=M2>=M3..>=M16, ce qui
gagne 13 ordres de grandeur;
Oui, mais il faut alors tester le nombre de répétions des Mj (et
ces test prennent du temps!!)
on obtient par exemple: en tenant compte de l'ordre:
avec ordre w1=(28,10,10,5,5,5,5,2,2,2,1,1,1,1,1,1)
p(w1)== 80! / (28!10!10!5!5!5!5!2!2!2!1!1!1!1!1.1!)*( 1/16)^80
et
sans ordre w2={28,10,10,5,5,5,5,2,2,2,1,1,1,1,1,1}
p(w2)== 16!/ (1!2!4!3!6!)*p(w1)
- et on n'est intéressé que par les solutions qui donnent X>65, ce qui
gagne encore 6 ordres de grandeur
Oui mais il faut trier les (m1,m2,....m16) qui donnent X>65 de façon
efficace...
Toujours pour K, j'obtiens P(X>65) en valeur exacte, pour les valeurs :
N= 3,4,5,6,7,8,9,10,11,12,13 ( en moins de 2 heures pour N).
Le temps de calcul est en gros multiplié par 2 à chaque valeur suivante de N
par exemple:
N p(X>65) 887189 / 4398046511104 = 4,749196933*10^-6
N p(X>65)8098927 / 35184372088832 = 3,925007576*10^-6
Il semble bien qu'il soit impossible d'envisager d'aller jusqu'à N...
(cela me rappelle un peu le problème des grains de blé sur l'échiquier)
Je serais d'ailleurs curieux de savoir jusqu'à quelle valeur de N vous
pouvez aller en un temps raisonnable, disons en gros 2 heures , sachant que
cela dépend bien sûr des processeurs (1733Mhz pour moi)
"Francois Grieu" a écrit dans le message de news:
"Acetonik" a écrit:j'ajoute qu'il y a 110 375 347 398 090 219 solutions entieres positives
En réalité il faut envisager encore bien plus de 16-uplets pour ne retenir
que les solutions qui conviennent même si l'on peut forcer quelques boucles
à se terminer sous certaines conditions ....
- on peut se restreindre aux solutions avec M1>=M2>=M3..>=M16, ce qui
gagne 13 ordres de grandeur;
Oui, mais il faut alors tester le nombre de répétions des Mj (et
ces test prennent du temps!!)
on obtient par exemple: en tenant compte de l'ordre:
avec ordre w1=(28,10,10,5,5,5,5,2,2,2,1,1,1,1,1,1)
p(w1)== 80! / (28!10!10!5!5!5!5!2!2!2!1!1!1!1!1.1!)*( 1/16)^80
et
sans ordre w2={28,10,10,5,5,5,5,2,2,2,1,1,1,1,1,1}
p(w2)== 16!/ (1!2!4!3!6!)*p(w1)
- et on n'est intéressé que par les solutions qui donnent X>65, ce qui
gagne encore 6 ordres de grandeur
Oui mais il faut trier les (m1,m2,....m16) qui donnent X>65 de façon
efficace...
Toujours pour K, j'obtiens P(X>65) en valeur exacte, pour les valeurs :
N= 3,4,5,6,7,8,9,10,11,12,13 ( en moins de 2 heures pour N).
Le temps de calcul est en gros multiplié par 2 à chaque valeur suivante de N
par exemple:
N p(X>65) 887189 / 4398046511104 = 4,749196933*10^-6
N p(X>65)8098927 / 35184372088832 = 3,925007576*10^-6
Il semble bien qu'il soit impossible d'envisager d'aller jusqu'à N...
(cela me rappelle un peu le problème des grains de blé sur l'échiquier)
Je serais d'ailleurs curieux de savoir jusqu'à quelle valeur de N vous
pouvez aller en un temps raisonnable, disons en gros 2 heures , sachant que
cela dépend bien sûr des processeurs (1733Mhz pour moi)
On tire N fois un entier supposé équidistribué de 1 à K;
on compte le nombre Mj d'occurrences de chaque valeur;
on calcule
X = Somme (Mj - N/K)^2 * K/N
j=1..K
On demande la probabilité p(65) que X>65 (événement improbable
correspondant à une distribution irrégulière des Mj).
La source du problème (section E.6 page 30 de [trngk31e])
indique
p ~= 3,8*10^-7
On tire N fois un entier supposé équidistribué de 1 à K;
on compte le nombre Mj d'occurrences de chaque valeur;
on calcule
X = Somme (Mj - N/K)^2 * K/N
j=1..K
On demande la probabilité p(65) que X>65 (événement improbable
correspondant à une distribution irrégulière des Mj).
La source du problème (section E.6 page 30 de [trngk31e])
indique
p ~= 3,8*10^-7
On tire N fois un entier supposé équidistribué de 1 à K;
on compte le nombre Mj d'occurrences de chaque valeur;
on calcule
X = Somme (Mj - N/K)^2 * K/N
j=1..K
On demande la probabilité p(65) que X>65 (événement improbable
correspondant à une distribution irrégulière des Mj).
La source du problème (section E.6 page 30 de [trngk31e])
indique
p ~= 3,8*10^-7
"Francois Grieu" a écritOn tire N fois un entier supposé équidistribué de 1 à K;
on compte le nombre Mj d'occurrences de chaque valeur;
on calcule
X = Somme (Mj - N/K)^2 * K/N
j=1..K
On demande la probabilité p(65) que X>65 (événement improbable
correspondant à une distribution irrégulière des Mj).
La source du problème (section E.6 page 30 de [trngk31e])
indique
p ~= 3,8 10^-7
Apres amélioration de mon programme , j'ai réussi.....
(j'avais pourtant fortement douté)
"Il semble bien qu'il soit impossible d'envisager d'aller
jusqu'à N"
P(X>65) a pour valeur EXACTE:
39666854199103933259671012362705671426849338
9896476347154445973084777301080583869173137
----------------------------------------------------------
10429624198832568761694441924656016184583518175
56959360325703910069443225478828393565899456512
p ~= 3,803287007 10^-7
ce qui confirme la source du problème.....
"Francois Grieu" <fgrieu@gmail.com> a écrit
On tire N fois un entier supposé équidistribué de 1 à K;
on compte le nombre Mj d'occurrences de chaque valeur;
on calcule
X = Somme (Mj - N/K)^2 * K/N
j=1..K
On demande la probabilité p(65) que X>65 (événement improbable
correspondant à une distribution irrégulière des Mj).
La source du problème (section E.6 page 30 de [trngk31e])
indique
p ~= 3,8 10^-7
Apres amélioration de mon programme , j'ai réussi.....
(j'avais pourtant fortement douté)
"Il semble bien qu'il soit impossible d'envisager d'aller
jusqu'à N"
P(X>65) a pour valeur EXACTE:
39666854199103933259671012362705671426849338
9896476347154445973084777301080583869173137
----------------------------------------------------------
10429624198832568761694441924656016184583518175
56959360325703910069443225478828393565899456512
p ~= 3,803287007 10^-7
ce qui confirme la source du problème.....
"Francois Grieu" a écritOn tire N fois un entier supposé équidistribué de 1 à K;
on compte le nombre Mj d'occurrences de chaque valeur;
on calcule
X = Somme (Mj - N/K)^2 * K/N
j=1..K
On demande la probabilité p(65) que X>65 (événement improbable
correspondant à une distribution irrégulière des Mj).
La source du problème (section E.6 page 30 de [trngk31e])
indique
p ~= 3,8 10^-7
Apres amélioration de mon programme , j'ai réussi.....
(j'avais pourtant fortement douté)
"Il semble bien qu'il soit impossible d'envisager d'aller
jusqu'à N"
P(X>65) a pour valeur EXACTE:
39666854199103933259671012362705671426849338
9896476347154445973084777301080583869173137
----------------------------------------------------------
10429624198832568761694441924656016184583518175
56959360325703910069443225478828393565899456512
p ~= 3,803287007 10^-7
ce qui confirme la source du problème.....
Dans l'article <4911882f$0$885$,
"Acetonik" a écrit:"Francois Grieu" a écritOn tire N fois un entier supposé équidistribué de 1 à K;
on compte le nombre Mj d'occurrences de chaque valeur;
on calcule
X = Somme (Mj - N/K)^2 * K/N
j=1..K
On demande la probabilité p(65) que X>65
P(X>65) a pour valeur EXACTE:
39666854199103933259671012362705671426849338
9896476347154445973084777301080583869173137
----------------------------------------------------------
10429624198832568761694441924656016184583518175
56959360325703910069443225478828393565899456512
p ~= 3,803287007 10^-7
ce qui confirme la source du problème.....
Merci pour ce résultat !
De mon côté j'ai fait des explorations; comme vous, j'explore
toutes les combinaisons avec les Mj triés, mais je le fait en C
avec des flottants pour les parties manipulant des grands nombres.
Je n'ai donc pas le résultat exact, seulement une approximation
(et je dois être attentif à la stabilité numérique); par contre
j'y gagne en vitesse et parvient à traiter des N et K un peu plus
grands:
K N temps boucles P(X>65)
16 64 <1 s 1031391 4,89630 10^-7
16 80 3 s 6882999 3,80329 10^-7
16 96 15 s 36435710 2,83146 10^-7
16 112 62 s 161410965 2,43287 10^-7
16 128 230 s 620457761 1,98582 10^-7
16 144 7273 s 2123574123 1,79699 10^-7
32 64 <2 s 1706159
32 96 190 s 107608848
note: le temps comprends le calcul et la production d'un
fichier tabulant P(X>V) pour tous les V possibles, sur
un PC portable un peu essouflé (Pentium M 1,5 GHz).
De tout ceci on peut retenir que l'approximation du problème
par une distribution du khideux n'est PAS justifiée, loin
de là, puisque pour K cela donne P(X>65) ~= 3,41694 10^-8.
Cette approximation est par contre justifiée dans la zone
K>=8, N/K>=5, P(X>V) > 0,05
Dans l'article <4911882f$0$885$ba4acef3@news.orange.fr>,
"Acetonik" a écrit:
"Francois Grieu" <fgrieu@gmail.com> a écrit
On tire N fois un entier supposé équidistribué de 1 à K;
on compte le nombre Mj d'occurrences de chaque valeur;
on calcule
X = Somme (Mj - N/K)^2 * K/N
j=1..K
On demande la probabilité p(65) que X>65
P(X>65) a pour valeur EXACTE:
39666854199103933259671012362705671426849338
9896476347154445973084777301080583869173137
----------------------------------------------------------
10429624198832568761694441924656016184583518175
56959360325703910069443225478828393565899456512
p ~= 3,803287007 10^-7
ce qui confirme la source du problème.....
Merci pour ce résultat !
De mon côté j'ai fait des explorations; comme vous, j'explore
toutes les combinaisons avec les Mj triés, mais je le fait en C
avec des flottants pour les parties manipulant des grands nombres.
Je n'ai donc pas le résultat exact, seulement une approximation
(et je dois être attentif à la stabilité numérique); par contre
j'y gagne en vitesse et parvient à traiter des N et K un peu plus
grands:
K N temps boucles P(X>65)
16 64 <1 s 1031391 4,89630 10^-7
16 80 3 s 6882999 3,80329 10^-7
16 96 15 s 36435710 2,83146 10^-7
16 112 62 s 161410965 2,43287 10^-7
16 128 230 s 620457761 1,98582 10^-7
16 144 7273 s 2123574123 1,79699 10^-7
32 64 <2 s 1706159
32 96 190 s 107608848
note: le temps comprends le calcul et la production d'un
fichier tabulant P(X>V) pour tous les V possibles, sur
un PC portable un peu essouflé (Pentium M 1,5 GHz).
De tout ceci on peut retenir que l'approximation du problème
par une distribution du khideux n'est PAS justifiée, loin
de là, puisque pour K cela donne P(X>65) ~= 3,41694 10^-8.
Cette approximation est par contre justifiée dans la zone
K>=8, N/K>=5, P(X>V) > 0,05
Dans l'article <4911882f$0$885$,
"Acetonik" a écrit:"Francois Grieu" a écritOn tire N fois un entier supposé équidistribué de 1 à K;
on compte le nombre Mj d'occurrences de chaque valeur;
on calcule
X = Somme (Mj - N/K)^2 * K/N
j=1..K
On demande la probabilité p(65) que X>65
P(X>65) a pour valeur EXACTE:
39666854199103933259671012362705671426849338
9896476347154445973084777301080583869173137
----------------------------------------------------------
10429624198832568761694441924656016184583518175
56959360325703910069443225478828393565899456512
p ~= 3,803287007 10^-7
ce qui confirme la source du problème.....
Merci pour ce résultat !
De mon côté j'ai fait des explorations; comme vous, j'explore
toutes les combinaisons avec les Mj triés, mais je le fait en C
avec des flottants pour les parties manipulant des grands nombres.
Je n'ai donc pas le résultat exact, seulement une approximation
(et je dois être attentif à la stabilité numérique); par contre
j'y gagne en vitesse et parvient à traiter des N et K un peu plus
grands:
K N temps boucles P(X>65)
16 64 <1 s 1031391 4,89630 10^-7
16 80 3 s 6882999 3,80329 10^-7
16 96 15 s 36435710 2,83146 10^-7
16 112 62 s 161410965 2,43287 10^-7
16 128 230 s 620457761 1,98582 10^-7
16 144 7273 s 2123574123 1,79699 10^-7
32 64 <2 s 1706159
32 96 190 s 107608848
note: le temps comprends le calcul et la production d'un
fichier tabulant P(X>V) pour tous les V possibles, sur
un PC portable un peu essouflé (Pentium M 1,5 GHz).
De tout ceci on peut retenir que l'approximation du problème
par une distribution du khideux n'est PAS justifiée, loin
de là, puisque pour K cela donne P(X>65) ~= 3,41694 10^-8.
Cette approximation est par contre justifiée dans la zone
K>=8, N/K>=5, P(X>V) > 0,05
"Francois Grieu" a écrit dans le message de news:Dans l'article <4911882f$0$885$,
"Acetonik" a écrit:"Francois Grieu" a écritOn tire N fois un entier supposé équidistribué de 1 à K;
on compte le nombre Mj d'occurrences de chaque valeur;
on calcule
X = Somme (Mj - N/K)^2 * K/N
j=1..K
On demande la probabilité p(65) que X>65
[...]P(X>65) a pour valeur EXACTE:
39666854199103933259671012362705671426849338
9896476347154445973084777301080583869173137
----------------------------------------------------------
10429624198832568761694441924656016184583518175
56959360325703910069443225478828393565899456512
p ~= 3,803287007 10^-7
ce qui confirme la source du problème.....
Merci pour ce résultat !
J'explore toutes les combinaisons avec les Mj triés, en C avec
des flottants pour les parties manipulant des grands nombres.
Je n'ai donc pas le résultat exact, seulement une approximation
(et je dois être attentif à la stabilité numérique); par contre
j'y gagne en vitesse et parvient à traiter des N et K un peu plus
grands:
K N temps boucles P(X>65)
16 64 <1 s 1031391 4,89630 10^-7
16 80 3 s 6882999 3,80329 10^-7
16 96 15 s 36435710 2,83146 10^-7
16 112 62 s 161410965 2,43287 10^-7
16 128 230 s 620457761 1,98582 10^-7
16 144 7273 s 2123574123 1,79699 10^-7
32 64 <2 s 1706159
32 96 190 s 107608848
note: le temps comprends le calcul et la production d'un
fichier tabulant P(X>V) pour tous les V possibles, sur
un PC portable un peu essouflé (Pentium M 1,5 GHz).
Ces réponses approchées, dont on ne pourrait déterminer à priori
la précision, sont intéressantes dans la mesure où on a pu les
comparer avec un calcul exact.
Il faut reconnaitre cependant qu'il n'est possible d'obtenir la
distribution exacte (probabilité donnée sous forme fractionnaire)
de la variable discrète X, en un temps raisonnable, que pour des
valeurs fixées de N et K assez petites.De tout ceci on peut retenir que l'approximation du problème
par une distribution du khideux n'est PAS justifiée, loin
de là, puisque pour K cela donne P(X>65) ~= 3,41694 10^-8.
Cette approximation est par contre justifiée dans la zone
K>=8, N/K>=5, P(X>V) > 0,05
Le programme que nous avons généré (je dis "le" parce qu'ils me
semblent équivalents: l'un en valeur exacte , l'autre en valeur
approchée) peut être utilisé en théorie pour toutes valeurs
entières strictement positives de N et K afin de calculer P[X>x]
pour tout x réel.
Je dirais cependant pour ma part que:
- si N/K> , il faut utiliser le fait que X suit
approximativement une loi du "khi deux" ( ce qui est classique)
- si 5<= N/K <10 il est de loin préférable d'utiliser le
programme précédent ( cas N , K par exemple).
-si 0<N/K<5 le programme donne P[X>x] , mais effectuer un
test statistique dans ces conditions ne semble peu judicieux.
"Francois Grieu" <fgrieu@gmail.com> a écrit dans le message de news:
fgrieu-5F8D0A.10111610112008@news-3.proxad.net...
Dans l'article <4911882f$0$885$ba4acef3@news.orange.fr>,
"Acetonik" a écrit:
"Francois Grieu" <fgrieu@gmail.com> a écrit
On tire N fois un entier supposé équidistribué de 1 à K;
on compte le nombre Mj d'occurrences de chaque valeur;
on calcule
X = Somme (Mj - N/K)^2 * K/N
j=1..K
On demande la probabilité p(65) que X>65
[...]
P(X>65) a pour valeur EXACTE:
39666854199103933259671012362705671426849338
9896476347154445973084777301080583869173137
----------------------------------------------------------
10429624198832568761694441924656016184583518175
56959360325703910069443225478828393565899456512
p ~= 3,803287007 10^-7
ce qui confirme la source du problème.....
Merci pour ce résultat !
J'explore toutes les combinaisons avec les Mj triés, en C avec
des flottants pour les parties manipulant des grands nombres.
Je n'ai donc pas le résultat exact, seulement une approximation
(et je dois être attentif à la stabilité numérique); par contre
j'y gagne en vitesse et parvient à traiter des N et K un peu plus
grands:
K N temps boucles P(X>65)
16 64 <1 s 1031391 4,89630 10^-7
16 80 3 s 6882999 3,80329 10^-7
16 96 15 s 36435710 2,83146 10^-7
16 112 62 s 161410965 2,43287 10^-7
16 128 230 s 620457761 1,98582 10^-7
16 144 7273 s 2123574123 1,79699 10^-7
32 64 <2 s 1706159
32 96 190 s 107608848
note: le temps comprends le calcul et la production d'un
fichier tabulant P(X>V) pour tous les V possibles, sur
un PC portable un peu essouflé (Pentium M 1,5 GHz).
Ces réponses approchées, dont on ne pourrait déterminer à priori
la précision, sont intéressantes dans la mesure où on a pu les
comparer avec un calcul exact.
Il faut reconnaitre cependant qu'il n'est possible d'obtenir la
distribution exacte (probabilité donnée sous forme fractionnaire)
de la variable discrète X, en un temps raisonnable, que pour des
valeurs fixées de N et K assez petites.
De tout ceci on peut retenir que l'approximation du problème
par une distribution du khideux n'est PAS justifiée, loin
de là, puisque pour K cela donne P(X>65) ~= 3,41694 10^-8.
Cette approximation est par contre justifiée dans la zone
K>=8, N/K>=5, P(X>V) > 0,05
Le programme que nous avons généré (je dis "le" parce qu'ils me
semblent équivalents: l'un en valeur exacte , l'autre en valeur
approchée) peut être utilisé en théorie pour toutes valeurs
entières strictement positives de N et K afin de calculer P[X>x]
pour tout x réel.
Je dirais cependant pour ma part que:
- si N/K> , il faut utiliser le fait que X suit
approximativement une loi du "khi deux" ( ce qui est classique)
- si 5<= N/K <10 il est de loin préférable d'utiliser le
programme précédent ( cas N , K par exemple).
-si 0<N/K<5 le programme donne P[X>x] , mais effectuer un
test statistique dans ces conditions ne semble peu judicieux.
"Francois Grieu" a écrit dans le message de news:Dans l'article <4911882f$0$885$,
"Acetonik" a écrit:"Francois Grieu" a écritOn tire N fois un entier supposé équidistribué de 1 à K;
on compte le nombre Mj d'occurrences de chaque valeur;
on calcule
X = Somme (Mj - N/K)^2 * K/N
j=1..K
On demande la probabilité p(65) que X>65
[...]P(X>65) a pour valeur EXACTE:
39666854199103933259671012362705671426849338
9896476347154445973084777301080583869173137
----------------------------------------------------------
10429624198832568761694441924656016184583518175
56959360325703910069443225478828393565899456512
p ~= 3,803287007 10^-7
ce qui confirme la source du problème.....
Merci pour ce résultat !
J'explore toutes les combinaisons avec les Mj triés, en C avec
des flottants pour les parties manipulant des grands nombres.
Je n'ai donc pas le résultat exact, seulement une approximation
(et je dois être attentif à la stabilité numérique); par contre
j'y gagne en vitesse et parvient à traiter des N et K un peu plus
grands:
K N temps boucles P(X>65)
16 64 <1 s 1031391 4,89630 10^-7
16 80 3 s 6882999 3,80329 10^-7
16 96 15 s 36435710 2,83146 10^-7
16 112 62 s 161410965 2,43287 10^-7
16 128 230 s 620457761 1,98582 10^-7
16 144 7273 s 2123574123 1,79699 10^-7
32 64 <2 s 1706159
32 96 190 s 107608848
note: le temps comprends le calcul et la production d'un
fichier tabulant P(X>V) pour tous les V possibles, sur
un PC portable un peu essouflé (Pentium M 1,5 GHz).
Ces réponses approchées, dont on ne pourrait déterminer à priori
la précision, sont intéressantes dans la mesure où on a pu les
comparer avec un calcul exact.
Il faut reconnaitre cependant qu'il n'est possible d'obtenir la
distribution exacte (probabilité donnée sous forme fractionnaire)
de la variable discrète X, en un temps raisonnable, que pour des
valeurs fixées de N et K assez petites.De tout ceci on peut retenir que l'approximation du problème
par une distribution du khideux n'est PAS justifiée, loin
de là, puisque pour K cela donne P(X>65) ~= 3,41694 10^-8.
Cette approximation est par contre justifiée dans la zone
K>=8, N/K>=5, P(X>V) > 0,05
Le programme que nous avons généré (je dis "le" parce qu'ils me
semblent équivalents: l'un en valeur exacte , l'autre en valeur
approchée) peut être utilisé en théorie pour toutes valeurs
entières strictement positives de N et K afin de calculer P[X>x]
pour tout x réel.
Je dirais cependant pour ma part que:
- si N/K> , il faut utiliser le fait que X suit
approximativement une loi du "khi deux" ( ce qui est classique)
- si 5<= N/K <10 il est de loin préférable d'utiliser le
programme précédent ( cas N , K par exemple).
-si 0<N/K<5 le programme donne P[X>x] , mais effectuer un
test statistique dans ces conditions ne semble peu judicieux.
"Francois Grieu" a écrit dans le message de news:Dans l'article <4911882f$0$885$,
"Acetonik" a écrit:"Francois Grieu" a écritOn tire N fois un entier supposé équidistribué de 1 à K;
on compte le nombre Mj d'occurrences de chaque valeur;
on calcule
X = Somme (Mj - N/K)^2 * K/N
j=1..K
On demande la probabilité p(65) que X>65
[...]P(X>65) a pour valeur EXACTE:
39666854199103933259671012362705671426849338
9896476347154445973084777301080583869173137
----------------------------------------------------------
10429624198832568761694441924656016184583518175
56959360325703910069443225478828393565899456512
p ~= 3,803287007 10^-7
ce qui confirme la source du problème.....
Merci pour ce résultat !
J'explore toutes les combinaisons avec les Mj triés, en C avec
des flottants pour les parties manipulant des grands nombres.
Je n'ai donc pas le résultat exact, seulement une approximation
(et je dois être attentif à la stabilité numérique); par contre
j'y gagne en vitesse et parvient à traiter des N et K un peu plus
grands:
K N temps boucles P(X>65)
16 64 <1 s 1031391 4,89630 10^-7
16 80 3 s 6882999 3,80329 10^-7
16 96 15 s 36435710 2,83146 10^-7
16 112 62 s 161410965 2,43287 10^-7
16 128 230 s 620457761 1,98582 10^-7
16 144 7273 s 2123574123 1,79699 10^-7
32 64 <2 s 1706159
32 96 190 s 107608848
note: le temps comprends le calcul et la production d'un
fichier tabulant P(X>V) pour tous les V possibles, sur
un PC portable un peu essouflé (Pentium M 1,5 GHz).
Ces réponses approchées, dont on ne pourrait déterminer à priori
la précision, sont intéressantes dans la mesure où on a pu les
comparer avec un calcul exact.
Il faut reconnaitre cependant qu'il n'est possible d'obtenir la
distribution exacte (probabilité donnée sous forme fractionnaire)
de la variable discrète X, en un temps raisonnable, que pour des
valeurs fixées de N et K assez petites.De tout ceci on peut retenir que l'approximation du problème
par une distribution du khideux n'est PAS justifiée, loin
de là, puisque pour K cela donne P(X>65) ~= 3,41694 10^-8.
Cette approximation est par contre justifiée dans la zone
K>=8, N/K>=5, P(X>V) > 0,05
Le programme que nous avons généré (je dis "le" parce qu'ils me
semblent équivalents: l'un en valeur exacte , l'autre en valeur
approchée) peut être utilisé en théorie pour toutes valeurs
entières strictement positives de N et K afin de calculer P[X>x]
pour tout x réel.
Je dirais cependant pour ma part que:
- si N/K> , il faut utiliser le fait que X suit
approximativement une loi du "khi deux" ( ce qui est classique)
- si 5<= N/K <10 il est de loin préférable d'utiliser le
programme précédent ( cas N , K par exemple).
-si 0<N/K<5 le programme donne P[X>x] , mais effectuer un
test statistique dans ces conditions ne semble peu judicieux.
"Francois Grieu" <fgrieu@gmail.com> a écrit dans le message de news:
fgrieu-5F8D0A.10111610112008@news-3.proxad.net...
Dans l'article <4911882f$0$885$ba4acef3@news.orange.fr>,
"Acetonik" a écrit:
"Francois Grieu" <fgrieu@gmail.com> a écrit
On tire N fois un entier supposé équidistribué de 1 à K;
on compte le nombre Mj d'occurrences de chaque valeur;
on calcule
X = Somme (Mj - N/K)^2 * K/N
j=1..K
On demande la probabilité p(65) que X>65
[...]
P(X>65) a pour valeur EXACTE:
39666854199103933259671012362705671426849338
9896476347154445973084777301080583869173137
----------------------------------------------------------
10429624198832568761694441924656016184583518175
56959360325703910069443225478828393565899456512
p ~= 3,803287007 10^-7
ce qui confirme la source du problème.....
Merci pour ce résultat !
J'explore toutes les combinaisons avec les Mj triés, en C avec
des flottants pour les parties manipulant des grands nombres.
Je n'ai donc pas le résultat exact, seulement une approximation
(et je dois être attentif à la stabilité numérique); par contre
j'y gagne en vitesse et parvient à traiter des N et K un peu plus
grands:
K N temps boucles P(X>65)
16 64 <1 s 1031391 4,89630 10^-7
16 80 3 s 6882999 3,80329 10^-7
16 96 15 s 36435710 2,83146 10^-7
16 112 62 s 161410965 2,43287 10^-7
16 128 230 s 620457761 1,98582 10^-7
16 144 7273 s 2123574123 1,79699 10^-7
32 64 <2 s 1706159
32 96 190 s 107608848
note: le temps comprends le calcul et la production d'un
fichier tabulant P(X>V) pour tous les V possibles, sur
un PC portable un peu essouflé (Pentium M 1,5 GHz).
Ces réponses approchées, dont on ne pourrait déterminer à priori
la précision, sont intéressantes dans la mesure où on a pu les
comparer avec un calcul exact.
Il faut reconnaitre cependant qu'il n'est possible d'obtenir la
distribution exacte (probabilité donnée sous forme fractionnaire)
de la variable discrète X, en un temps raisonnable, que pour des
valeurs fixées de N et K assez petites.
De tout ceci on peut retenir que l'approximation du problème
par une distribution du khideux n'est PAS justifiée, loin
de là, puisque pour K cela donne P(X>65) ~= 3,41694 10^-8.
Cette approximation est par contre justifiée dans la zone
K>=8, N/K>=5, P(X>V) > 0,05
Le programme que nous avons généré (je dis "le" parce qu'ils me
semblent équivalents: l'un en valeur exacte , l'autre en valeur
approchée) peut être utilisé en théorie pour toutes valeurs
entières strictement positives de N et K afin de calculer P[X>x]
pour tout x réel.
Je dirais cependant pour ma part que:
- si N/K> , il faut utiliser le fait que X suit
approximativement une loi du "khi deux" ( ce qui est classique)
- si 5<= N/K <10 il est de loin préférable d'utiliser le
programme précédent ( cas N , K par exemple).
-si 0<N/K<5 le programme donne P[X>x] , mais effectuer un
test statistique dans ces conditions ne semble peu judicieux.
"Francois Grieu" a écrit dans le message de news:Dans l'article <4911882f$0$885$,
"Acetonik" a écrit:"Francois Grieu" a écritOn tire N fois un entier supposé équidistribué de 1 à K;
on compte le nombre Mj d'occurrences de chaque valeur;
on calcule
X = Somme (Mj - N/K)^2 * K/N
j=1..K
On demande la probabilité p(65) que X>65
[...]P(X>65) a pour valeur EXACTE:
39666854199103933259671012362705671426849338
9896476347154445973084777301080583869173137
----------------------------------------------------------
10429624198832568761694441924656016184583518175
56959360325703910069443225478828393565899456512
p ~= 3,803287007 10^-7
ce qui confirme la source du problème.....
Merci pour ce résultat !
J'explore toutes les combinaisons avec les Mj triés, en C avec
des flottants pour les parties manipulant des grands nombres.
Je n'ai donc pas le résultat exact, seulement une approximation
(et je dois être attentif à la stabilité numérique); par contre
j'y gagne en vitesse et parvient à traiter des N et K un peu plus
grands:
K N temps boucles P(X>65)
16 64 <1 s 1031391 4,89630 10^-7
16 80 3 s 6882999 3,80329 10^-7
16 96 15 s 36435710 2,83146 10^-7
16 112 62 s 161410965 2,43287 10^-7
16 128 230 s 620457761 1,98582 10^-7
16 144 7273 s 2123574123 1,79699 10^-7
32 64 <2 s 1706159
32 96 190 s 107608848
note: le temps comprends le calcul et la production d'un
fichier tabulant P(X>V) pour tous les V possibles, sur
un PC portable un peu essouflé (Pentium M 1,5 GHz).
Ces réponses approchées, dont on ne pourrait déterminer à priori
la précision, sont intéressantes dans la mesure où on a pu les
comparer avec un calcul exact.
Il faut reconnaitre cependant qu'il n'est possible d'obtenir la
distribution exacte (probabilité donnée sous forme fractionnaire)
de la variable discrète X, en un temps raisonnable, que pour des
valeurs fixées de N et K assez petites.De tout ceci on peut retenir que l'approximation du problème
par une distribution du khideux n'est PAS justifiée, loin
de là, puisque pour K cela donne P(X>65) ~= 3,41694 10^-8.
Cette approximation est par contre justifiée dans la zone
K>=8, N/K>=5, P(X>V) > 0,05
Le programme que nous avons généré (je dis "le" parce qu'ils me
semblent équivalents: l'un en valeur exacte , l'autre en valeur
approchée) peut être utilisé en théorie pour toutes valeurs
entières strictement positives de N et K afin de calculer P[X>x]
pour tout x réel.
Je dirais cependant pour ma part que:
- si N/K> , il faut utiliser le fait que X suit
approximativement une loi du "khi deux" ( ce qui est classique)
- si 5<= N/K <10 il est de loin préférable d'utiliser le
programme précédent ( cas N , K par exemple).
-si 0<N/K<5 le programme donne P[X>x] , mais effectuer un
test statistique dans ces conditions ne semble peu judicieux.
