Approximation de la probabilité de machine à écrire de singe
Disons que nous sommes intéressés par le problème d'un singe tapant au hasard une chaîne de longueur spécifique msur un clavier avec des ktouches, lors d' nessais, au moins une fois:
$$ 1 - \left(1 - \frac{1}{k^{m}}\right)^n $$
Je voudrais avoir une certaine intuition sur la façon dont cette expression varie pour met n(avec k autour de 26).
- Y a-t-il une approximation que nous pouvons utiliser dans ce cas?
- Je voudrais comprendre comment cette probabilité varie à mesure que nous ajoutons un caractère de plus - de combien devons-nous augmenter $n$ pour garder la même probabilité $?$.
- Relative à $1.$: Comment calculer la probabilité du cas où $k = 26, m = 50, n = 1,000,000\ ?$. Je ne pouvais pas le faire en Python.
Merci
Réponses
Une expérience avec de vrais singes a suggéré que les touches enfoncées ne sont pas indépendantes - dans ce cas, elles répétaient beaucoup les lettres
De retour à votre question, il peut être judicieux de soustraire $k-1$ de $n$ car vous ne pouvez pas obtenir la chaîne de caractères souhaitée $k$ personnages avec dans le premier $k-1$ tentatives.
Ignorant ce point, une approximation avec une grande $n$ est $$1 - \left(1 - \frac{1}{k^m}\right)^n \approx 1- e^{-n/k^m} $$
Si vous voulez que le côté droit reste constant $k$ augmente de $1$ alors tu veux $\frac{n_1}{(k+1)^m} \approx \frac{n_0}{k^m}$ alors tu veux $\frac{n_1}{n_0} \approx \left(1+\frac1k\right)^m$.
Qu'il s'agisse $e^{m/k}$ est une bonne approximation de ce rapport dépend des valeurs particulières de $m$ et $k$
Expression:
$$1 - (1 - \frac{1}{k^m})^n$$
Des questions:
Q1. Y a-t-il une approximation que nous pouvons utiliser dans ce cas?
Q3. Lié à 1 - comment calculer la probabilité pour le cas où k = 26, m = 50, n = 1 000 000? Je ne pouvais pas le faire en Python.
Je donnerai une seule réponse aux deux questions.
Ma réponse ici suppose que $k = 26.$ Prise en compte d'autres valeurs de $k$ est à la question 2.
Je ne connais pas les mathématiques mentionnées dans les autres réponses.
Je profite de cette occasion pour explorer en essayant d'utiliser les logarithmes, base 10. Je vais décrire comment l'approche fonctionnerait et où l'approche pourrait échouer .
Personnellement, je préfère la base 10 plutôt que la base $e$ parce que les logarithmes impliquent des nombres plus petits et parce qu'il devient plus facile de se rapporter au système de comptage décimal.
Tu pourrais raisonner que $\log_{10} (4)$est un peu plus de 0,6,
et $\displaystyle\frac{1}{26}$est juste en dessous $\displaystyle\frac{4}{100}$.
Pour que vous puissiez estimer $\log_{10} \left(\frac{1}{26}\right)$ comme sur $(0.6 - 2.0)$.
Vous pouvez également demander à l'ordinateur de fournir sa propre approximation de $\log_{10} \left(\frac{1}{26}\right)$ au nombre de décimales souhaité.
Une fois cela fait, il est facile de calculer $\log_{10} \left(\frac{1}{26^m}\right) = m \times \log_{10} \left(\frac{1}{26}\right)$
Une fois cela fait, vous utilisez simplement l'ordinateur pour calculer l'anti-journal.
Autrement dit, si le$\log_{10} (x) = a,$ ensuite $x = 10^a.$
Ensuite, après avoir calculé la valeur réelle de $r = \left(\frac{1}{26^m}\right)$
vous calculez ensuite $s = \log_{10} (1-r).$
Ensuite, vous avez que le $\log_{10} (1 - \frac{1}{k^m})^n = n \times s.$
Ensuite, vous convertissez ce qui précède en un anti-journal et le soustrayez de 1.
Pierre d'achoppement
Je n'ai jamais réellement expérimenté ou étudié l'utilisation des logarithmes, sur un ordinateur personnel, dans ce type de situation, où l'exposant $n$ était n'importe où près de 1 000 000.
Cela peut très bien être totalement irréalisable pour un exposant aussi grand.
Un essai consiste à voir si votre ordinateur gère ces nombres lorsque la notation scientifique est impliquée:
$u \times 10^v$, où $1 \leq u < 10.$
Un autre essai consiste à rechercher une bibliothèque de logiciels spécialisés personnalisés à votre langage (par exemple python, c, java, ...) qui est conçu pour gérer de si grands exposants.
Si ces approches ne fonctionnent pas, je pense que l'approche logarithmique doit être abandonnée.
Q2. Je voudrais comprendre comment cette probabilité varie à mesure que nous ajoutons un caractère de plus - de combien devons-nous augmenter n pour garder la même probabilité?
Si vous utilisez des logarithmes, vous pouvez simplement examiner
$\log_{10} \left(\frac{1}{26}\right)$ vs $\log_{10} \left(\frac{1}{27}\right).$
Plus formellement, $\frac{1}{26} - \frac{1}{27} = \frac{1}{26 \times 27}.$
En général, $\frac{1}{k} - \frac{1}{(k+1)} = \frac{1}{k \times (k+1)}.$
Un autre point de vue est qu'en passant de $\frac{1}{k}$ à $\frac{1}{(k+1)}$
vous appliquez simplement un facteur d'échelle de$\frac{k}{(k+1)}.$
Par conséquent, comme $\frac{1}{k}$ à $\frac{1}{(k+1)}$,
$\frac{1}{k^m}$ à $\frac{1}{k^m} \times \left(\frac{k}{(k+1)}\right)^m.$
Edit
Je viens de réaliser que je n'ai pas répondu à cette question.
de combien devons-nous augmenter n pour garder la même probabilité?
Le calcul est très laid . Ironiquement, l'expression la plus simple implique peut-être des logarithmes.
Vous voulez résoudre pour $x$, où
$$\left[1 - \left(\frac{1}{k^m}\right)\right]^n ~=~ \left[1 - \left(\frac{1}{(k+1)^m}\right)\right]^x. $$
Cela signifie que
$$\left(\frac{k^m - 1}{k^m}\right)^n ~=~ \left(\frac{(k+1)^m - 1}{(k+1)^m}\right)^x.$$
En prenant les logarithmes, cela signifie que
$$x \times \log_{(10)} \left(\frac{(k+1)^m - 1}{(k+1)^m}\right) ~=~ n \times \log_{(10)} \left(\frac{k^m - 1}{k^m}\right).$$
Q4. Je voudrais avoir une certaine intuition sur la façon dont cette expression varie pour$m$.
Cette question n'a pas été répertoriée, mais a été abordée dans la requête.
Mon explication à ce sujet sera nécessairement à la fois limitée et alambiquée.
Je limiterai mon explication à comment $\left[1 - \frac{1}{(26)^m}\right]$ varie avec $m$.
Considérons d'abord $d = \left[\frac{1}{(26)^m}\right]$.
Comme $m \to (m+1)$, cette valeur va de $d \to \left[\frac{d}{26}\right].$
Cela signifie que $(1 - d)$ va à $\left[1 - \frac{d}{26}\right].$
Par conséquent, l'expression bouge $26$ fois plus proche de $1$.