Question de combinaison / probabilité simple basée sur la longueur de la chaîne et les caractères possibles

En supposant un "caractère aléatoire complet" et une chaîne de 20 caractères, chaque caractère pouvant être l'un des 62 caractères possibles:

Quel est le nombre total de combinaisons possibles? (Deviner 20 à la puissance de 62.)
De plus, si de nouvelles chaînes sont sélectionnées au hasard les unes après les autres et ajoutées à une liste de chaînes sélectionnées jusqu'à présent, le nombre de chaînes qui doivent être sélectionnées avant que la chance de sélectionner une chaîne qui a déjà été sélectionnée soit inférieur à 1 sur 100000 ( $10^{-5}$ )?

Remarque: 62 provient de: chiffres numériques (0-9), lettres majuscules (AZ) et lettres minuscules (az).

probability combinatorics bévues
la source

Votre deuxième puce peut être lue (au moins) de deux manières possibles. Je me demande ce qui vous intéresse. ( 1 ) La probabilité que la

ème chaîne corresponde à l'une des chaînes précédentes ou ( 2 ) La probabilité qu'au moment où la

ème chaîne est sélectionnée, il existe des doublons dans la collection de cordes tirées jusqu'à présent. Les réponses à ces deux questions seront très différentes. :)

n

$n$

n

$n$

cardinal

Peut-être que la considération d'un alphabet à deux caractères fera la différence. Que les lettres soient

. Nous pouvons demander: ( 1 ) Pour quel

avons-nous au moins 99% de chances que la

ème chaîne soit un doublon d'une chaîne précédente? Le

ici est 8 puisque la seule façon dont nous échouons est si notre séquence est soit

, qui a une probabilité totale de

. Ou, nous demandons ( 2 ) pour quoi

H

$H$

T

$T$

n

$n$

n

$n$

n

$n$

T T T \dots T H

$TTT \cdots TH$

H H H \dots H T

$HHH\cdots HT$

2^{- (n - 1)}

$2^{-(n-1)}$

-nous avons au moins une chance99% de voir une double? Dans ce cas,

car au moment où nous avons vu trois chaînes,

a été répété au moins une fois.

n

$n$

n = 3

$n = 3$

H

$H$

T

$T$

Cardinal

La réponse de Matt gère ( 1 ), ce qui répond essentiellement à la question de savoir si "ma" chaîne correspond à celle de quelqu'un d'autre. Mais, si vous êtes inquiet au sujet des deux autres cordes de gens aussi potentiellement correspondant, alors vous êtes intéressé par ( 2 ). Cela revient à savoir si vous avez une chaîne d'intérêt particulière à laquelle vous comparez toutes les autres ou si vous comparez toutes les chaînes les unes aux autres. Je ne suis pas sûr de clarifier cela, cependant. (Votre problème se résume à l'une des deux variantes du fameux "problème d'anniversaire".)

Cardinal

Le cardinal a, comme d'habitude, raison. J'ai supposé que vous aviez une chaîne "cible", pour laquelle vous génériez une liste de suppositions. Si au lieu de cela, vous générez des chaînes au hasard et que vous voulez connaître le nombre qu'il est sûr de générer avant que deux chaînes ne correspondent, alors la réponse est très différente. Je modifierai ma réponse pour répondre à cette affaire, si cela vous convient.

Matt Krause

Je n'ai pas précisé clairement mon exemple précédent. Désolé pour ça. Je pensais à un alphabet à deux lettres

et dessinais des chaînes de longueur un . Par conséquent, lorsque j'ai écrit

, qui se trouvait à

, ...,

{H, T}

$\{H,T\}$

H H H \dots H T

$HHH\cdots HT$

s_{1} = H

$s_1 = H$

s_{2} = H

$s_2 = H$

s_{n - 1} = H

$s_{n-1} = H$

s_{n} = T

$s_n = T$

cardinal

Nombre total de possibilités

1) Fermez! Vous avez 62 choix pour le premier personnage, 62 pour le 2e, etc., vous vous retrouvez donc avec , ce qui est un nombre absurdement énorme. $62 \cdot 62 \cdot 62 \cdot \cdots 62 = 62^{20}$

Collision avec une chaîne "cible"

2) Comme nous l'avons établi ci-dessus, il existe chaînes potentielles. Vous voulez savoir combien vous devez deviner pour avoir plus de 1 chance sur 100 000 de deviner la chaîne "cible". Essentiellement, vous demandez ce que $62^{20}$ Pour être clair, il faudrait arrondir x (ou en ajouter un, s'ils sont exactement égaux), mais comme vous le verrez dans une seconde, cela n'a pas vraiment d'importance.

\frac{X}{62^{20}} \geq \frac{1}{{dix}^{5}}

$\frac{x}{62^{20}} \ge \frac{1}{10^5}$

Grâce à l'algèbre de base, nous pouvons réorganiser cela comme

\begin{aligned} {dix}^{5} X & \geq 62^{20} \\ {dix}^{5} X & \geq (6.2 \cdot dix)^{20} \\ {dix}^{5} X & \geq {6.2}^{20} \cdot {dix}^{20} \\ X & \geq {6.2}^{20} \cdot {dix}^{15} \end{aligned}

$\begin{aligned} 10^5x &\ge 62^{20}\\ 10^5{x} &\ge (6.2 \cdot 10)^{20}\\ 10^5x &\ge 6.2^{20} \cdot 10^{20}\\ x &\ge 6.2^{20} \cdot 10^{15} \end{aligned}$

Pour faire le calcul, est environ , alors appelons le tout ou, plus succinctement, beaucoup. $6.2^{20}$ $7 \cdot 10^{15}$ $7 \cdot 10^{30}$

C'est, bien sûr, pourquoi les mots de passe longs fonctionnent très bien :-) Pour les vrais mots de passe, bien sûr, vous devez vous soucier des chaînes de longueur inférieure ou égale à vingt, ce qui augmente encore plus le nombre de possibilités.

Doublons dans la liste

Maintenant, considérons l'autre scénario. Les chaînes sont générées de façon aléatoire et nous voulons déterminer combien peuvent être générées avant qu'il y ait une chance de 1/100 000 de faire correspondre deux chaînes. La version classique de ce problème est appelée le problème d'anniversaire (ou «paradoxe») et demande quelle est la probabilité que deux personnes sur n aient le même anniversaire. L'article de wikipedia [1] semble décent et contient des tableaux qui pourraient vous être utiles. Néanmoins, je vais essayer de vous donner la saveur de la réponse ici aussi.

Quelques points à garder à l'esprit:

-La probabilité d'un match et de ne pas avoir de match doit être égale à 1, donc et vice versa. $P(\textrm{match}) = 1 - P(\textrm{no match})$

-Pour deux événements indépendants et , la probabilité de . $A$ $B$ $P(A \& B) = P(A) \cdot P(B)$

Pour obtenir la réponse, nous allons commencer par calculer la probabilité de ne pas voir de correspondance pour un nombre fixe de chaînes . Une fois que nous savons faire cela, nous pouvons définir cette équation égale au seuil (1/100 000) et résoudre pour . Pour plus de commodité, appelons le nombre de chaînes possibles ( ). $k$ $k$ $N$ $62^{20}$

$k$ $N$ $P_{k=1}(\textrm{no match}) = \frac{N}{N} = 1$ $N$ $P_{k=2}(\textrm{no match}) = \frac{N-1}{N}$ $N-2$ $P_{k=3}(\textrm{no match}) = \frac{N-2}{N}$ $k$

P_{k} (aucune concordance) = \frac{N - k + 1}{N}

$P_{k}(\textrm{no match})= \frac{N-k+1}{N}$

$k$

P (Pas de correspondance) = \frac{N}{N} \cdot \frac{N - 1}{N} \cdot \frac{N - 2}{N} \dots \frac{N - k + 1}{N}

$P(\textrm{No Matches}) = \frac{N}{N} \cdot \frac{N-1}{N} \cdot \frac{N-2}{N} \cdots \frac{N-k+1}{N}$

\begin{aligned} P (Pas de correspondance) & = \frac{N \cdot (N - 1) \cdot (N - 2) \dots (N - k + 1)}{N^{k}} \\ P (Pas de correspondance) & = \frac{N!}{N^{k} \cdot (N - k)!} \\ P (Pas de correspondance) & = \frac{k! \cdot (\binom{N}{k})}{N^{k}} \end{aligned}

$\begin{aligned} P(\textrm{No Matches}) &= \frac{N \cdot (N-1) \cdot (N-2) \cdots (N-k+1)}{N^k} \\ P(\textrm{No Matches}) &= \frac{N!}{N^k \cdot (N-k)!} \\ P(\textrm{No Matches}) &= \frac{k! \cdot \binom{N}{k}}{N^k} \\ \end{aligned}$

k! = (k) \cdot (k - 1) \cdot (k - 2) \dots 1

$k! = (k) \cdot (k-1) \cdot (k-2) \cdots 1$

N - k + 1 \dots N

$N-k+1 \cdots N$

k

$k$

\frac{1}{100, 000}

$\frac{1}{100,000}$

k

$k$

100!

$100!$

k = 0,5 + \sqrt{0,25 - 2 N \ln (p)}

$k = 0.5 + \sqrt{0.25 - 2N\ln(p)}$

N = 48, 000

$N=48,000$

3.7 \cdot 10^{15}

$3.7 \cdot 10^{15}$

Références

[1] http://en.wikipedia.org/wiki/Birthday_problem

[2] Mathis, Frank H. (juin 1991). "Un problème d'anniversaire généralisé". SIAM Review (Society for Industrial and Applied Mathematics) 33 (2): 265-270. Lien JSTOR

Matt Krause
la source

+1 Génial, étant donné que mes faibles compétences en mathématiques ont conduit à poser la question, je vais donc laisser la question sans réponse pendant une journée, mais cela me semble bien et est beaucoup plus clair que je ne le pensais - merci!

bévues

Heureux de vous aider! Faites-moi savoir si quelque chose n'est pas clair. Pour les coups de pied, j'ai couru les chiffres. Vous aurez besoin de 7044234255469980229683302646164 suppositions; comme je l'ai dit - beaucoup!

Matt Krause

+1 @Matt Krause: +1 à votre commentaire sous la réponse; votre réponse et votre engagement à donner la meilleure réponse possible sont exemplaires, dignes de mention, et merci pour tout votre travail acharné!

bévue

Question de combinaison / probabilité simple basée sur la longueur de la chaîne et les caractères possibles

Réponses:

Nombre total de possibilités

Collision avec une chaîne "cible"

Doublons dans la liste

Références