Discussion :

[Dermochelys]

Bonjour,

Je ne suis pas assez fort en calculs de probabilités pour résoudre la question suivante.... Pouvez-vous m'aider me donner une idée du résultat?

J'ai 9 villes (longueurs de chaînes de caractères allant de 7 à 12)
GREENWICH
PHILADELPHIA
CAPETOWN
ELHIERRO
TELAVIV
SEVILLA
ARKHANGELSK
LAPULAPU
PORTSMOUTH

Avec ces 9 villes, je fais une chaîne de exactement 80 caractères (ni plus, ni moins). L'ordre n'est pas défini et la chaîne ci-dessous n'est qu'un exemple parmi toutes les permutations possibles de ces noms de villes.
GREENWICHELHIERROARKHANGELSKSEVILLELAPULAPUTELAVIVCAPETOWNPORTSMOUTHPHILADELPHIA

Le premier caractère de cette chaîne est le n°1 et le dernier le n°80.
Par ailleurs, j'ai une matrice d'extraction ou chaque chiffre/nombre corresponds a la position d'une lettre dans la chaîne précédente.

28/05/60/68/26/31
16/39/20/35/55/03
80/53/45/76/24/29
67/04/72/75/03/76
44/28/15/58/08/53


Ma question est quelle est la probabilité que si je trouve dans la matrice un mot de 5 lettres qui soit un nom de ville (comme Arles, par exemple) ce ne soit pas une pure coïncidence due au hasard?
Ce mot pouvant se lire soit horizontalement, soit verticalement, soit en oblique.

Je précise que ma question n'a rien à avoir avec un exercice pour l'école ou d'autres situations du genre. Elle est plutôt liéé à des jeux de cryptographie :-)

Un grand merci pour votre aide et éventuellement une réponse en pourcentage de probabilité...

[tbc92]

On va tenter de répondre, mais il y aura nécessairement beaucoup d'impasses/approximations.

Dans l'alphabet, certaines lettres sont plus 'utiles' que d'autres (le E, le S sont plus souvent utilisées que le K ou le W par exemple). Ici, tu pars d'un échantillon qui n'est pas aléatoire, donc tu auras peu de K et de W, donc tu as un échantillon 'aligné' avec le dictionnaire.
Tu disposes tes mots pour constituer une chaine numérotée de 1 à 80. Tu sélectionnes 30 lettres dans cette chaine, et tu les disposes en rectangle. Bon, on va largement simplifier, on va dire que tu sélectionnes différentes chaines de 5 mots. Je compte 40 chaines de 5 mots (40 alignements de 5 cases dans ton rectangle) ; je considère que la première colonne par exemple donne 2 mots potentiels, un de bas en haut et l'autre de haut en bas.

On a besoin d'une autre information, c'est : combien y-a-t-il de noms de villes en 5 lettres. Aucune idée, c'est dommage, c'est une information essentielle, qui va beaucoup impacter le résultat. Disons qu'il y a 300 mots valides... totalement au pif.

Décomposons l'exercice en plusieurs questions :
Q1) Si on prend 5 lettres au hasard, quelle est la probabilité que le mot formé soit un des 200 mots de la liste des villes.
5 lettres au hasard, il y a 26*26*26*26*26 mots possibles, dont seulement 200 donnent des succès, donc Probabilité = 200 /(26*26*26*26*26) = 0.0025%
Q2) Ici, les lettres de départ sont biaisées, les bonnes lettres (les voyelles , les S, T, N ... sont plus présentes que les W ou les K) , comment prendre ça en compte.
A la louche, j'estime que ça fait comme si on avait un alphabet de 17 lettres et non plus 26, et ça nous donne une probabilité de 0.021% , soit en gros 8 fois plus que le calcul précédent.
Q3) Si on considère que la proba ci-dessus est valide, quelle est la probabilité qu'aucun des 40 groupes de 5 lettres n'est un nom de ville ?
Là encore, impasse. On va considérer que les 40 résultats sont indépendants, ce qui est un peu faux (en effet, si on a eu la malchance de sélectionner un K, on a 6 mots (voire 8) qui sont 'plombés' par ce tirage.
Si on a choisi 2 E et qu'ils tombent côte à côte sur la première ligne, on a 4 mots qui sont 'plombés'.
La probabilité que le premier groupe de 5 lettres ne soit pas un nom de ville, c'est 1-0.021%=99.98%
La probabilité qu'aucun des 40 mots ne soit un nom de ville, c'est 0.9998^40=99.16%
Et donc la probabilité qu'au moins un des 40 mots soit un nom de ville est 1-99.15%=0.84%

Il y a plein d'approximations, en particulier le nombre de mots valides (j'ai pris 300, mais je n'en ai pas la moindre idée)
Si on multiplie par 2, on reste sur des nombres très petits, et ça multiplie le résultat final par 2 aussi.

[Dermochelys]

Bonjour Tbc92,

C'est une super intéressante réponse que tu me donnes là!!

Je comprends bien toutes les approximations que tu as dû faire.
Mais donc en gros, le fait de trouver un nom de ville de 5 lettres dans ce cas de figure est inférieur à 1% si on fiat cela de manière aléatoire (et en tenant compte des limitations/approximations/impasses que tu évoques)?

En final, ça me semble beaucoup comme probabilité de trouver un nom de ville, malgré tout... Ca doit venir du fait que le choix de caractères est biaisé (on n'utilise pas tout l'alphabet)

Ma compréhension te semble correcte?

Merci en tout cas pour ton aide!!

[Dermochelys]

Tiens, en te relisant, quand tu dis "Si on multiplie par 2, on reste sur des nombres très petits, et ça multiplie le résultat final par 2 aussi.", est-ce que ce ne serait pas plutôt divisé le résultat final par 2?

Car si on prends plus de villes (600 par exemple), on augmenterait ou on diminuerait la chance d'avoir une de ces villes dans notre matrice?

[tbc92]

Je pars d'une hypothèse, c'est qu'il y a 300 noms de villes en 5 lettres. A priori, tu as un 'dictionnaire' avec les noms de villes et tu peux corriger cette approximation, sinon tu vas avoir du mal à mettre en place ce jeu.
Plus il y a de noms de villes valides, plus on a de chances de croiser un nom de ville dans notre grille.
La probabilité d'avoir spécifiquement ARLES ne change pas, mais la probabilité d'avoir au moins un nom de ville augmente.

[Guesset]

Bonjour,

En oblique signifie à 45° ou -45° ? Ou est-ce que tous les angles (discrets) sont possibles ? Si oui sous quel algorithme (Bresenham, demi-point ...) ?
Le sens est à prendre en compte (par exemple horizontal signifie seulement -> ou également <-) ?

Bien sûr, les réponses peuvent changer sensiblement le nombre de configurations.

Salutations