Probleme de probabilite

[quabe]

J`ai un ensemble de cardinal n.
Je connais exactement la probabilite d`avoir un nombre ayant certaines carateristiques. Mettons par exemple :15 pour cent.
Sauf que ces nombres sont regroupes par intervalle (l`intervalle est inconnu)

Exemple :

{0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,....,0,0,1,1,1,1,1,1,1,1,1,1,1,1, 0,0,0,...,0,0}
Les 1 sont regroupes souvent par intervalle de meme taille, les 0 en revanche peuvent avoir parmi eux des 1 isoles.
Mon probleme est le suivant :
- connaissant avec exactitude la probabilite globale d`avoir un 1 dans cet ensemble
- sachant que les 1 se retrouvent souvent groupes par intervalle de meme taille
- y a-t-il un algorithme qui permet de maniere efficiente (certaine je dirai) de detecter un 1 avec une probabilite k fois superieure a la probabilite globale? de quoi dependrait k?

Merci pour toute aide ou tuyau (document a lire etc..).

[lyceen95]

J'ai un intervalle [1, n]
Pour tous les entiers de cet intervalle j'ai un certain indicateur qui vaut 0 ou 1.
Je connais précisément le nombre d'entiers qui donnent 0 et qui donnent 1. Environ 15% des entiers donnent 1.
La répartition n'est pas aléatoire du tout. Les 1 sont soit isolé ( un 1 parmi plein de 0) , soit dans des intervalles de longueur fixe L , mais L est inconnu.

Etc etc.

Essayons de mettre des valeurs pour se fixer les idées.
Disons n = 100000. (en dessous de 100000, chercher à optimiser l'algo, on s'en moque un peu).
Disons qu'on a 15000 1 et donc 85000 0.
Disons que L vaut 50.
Et disons que sur les 15000 1, il y en a 14900 qui sont dans des groupes et 100 qui sont isolés.
14900 nombres qui sont dans des groupes de 50, ça veut dire 298 groupes.
Tous les 1 isolés, je les retire purement et simplement. Pour simplifier.
Il me reste donc 99900 nombres : 298 groupes de 50 1 et forcément 298 groupes de 0 ( ou 299 groupes ... )
Les groupes de 0 ont donc en moyenne une longueur de 85000/298 = 285.

Je choisis un nombre A totalement au hasard. Si ce nombre donne 1, c'est fini, j'ai de la chance.
Si ce nombre est très près de n, je vais chercher d'autres nombres plus petits que A, sinon je vais chercher d'autres nombres plus grands que A.
Je me mets dans cette 2ème hypothèse, je cherche d'autres nombres d'autres plus grands que A.

A a donné un 0, pas de chance.
Je vais tester A+L ; Si A+L donne également 0 je suis sûr que entre A et A+L, il n'y a que des 0, puisque les 1 sont regroupés en groupes de longueur L.
Et je recommence, en ajoutant L autant de fois que nécessaire. Le Premier groupe de 1, je suis sûr de le toucher, je suis sur de ne pas sauter par dessus, parce que je fais des sauts de longueur L et ce groupe de 1 a une longueur L.

Avec mes valeurs L=50, et la longueur moyenne d'un groupe de 0 est de 285. Donc, si mon 1er tirage est tombé vers le centre d'un groupe de 0, il me faudra 3 ou 4 essais pour atteindre le prochain groupe de 1.

J'ai 'neutralisé' tous les 1 isolés pour le raisonnement, mais ça reste complètement valable avec ces 1 isolés.

On prend un nombre A au hasard, puis on prend tous les A+kL, L étant la longueur fixe des groupes de 1.

Bien sûr, on suppose L connu !
Si L n'est pas connu, on doit bien en avoir une estimation. Et on va prendre un L un peu plus petit que cette estimation.

[quabe]

Merci beaucoup.
Avec ton explication, on peut enfin resoudre des problemes tres ardus. On peut connaitre de maniere tres precise la taille de l`intervalle.
On en reparlera plus tard.