Kombinatorisches Problem in einer "Autocomplete" -Anwendung

Question

Es wird ein Alphabet angegeben, bestehend aus $26$ Briefe:

$a, b, c,..., z$

$N$ zufällige Zeichenfolgen der Länge $L$werden mit diesem Alphabet erstellt. Man kann eine gleichmäßige Verteilung bei der Auswahl der Buchstaben annehmen, und Wiederholungen sind zulässig (sowohl Wiederholungen eines bestimmten Buchstabens innerhalb einer Zeichenfolge als auch Wiederholungen ganzer Zeichenfolgen).

Nun auf die gleiche Weise eine einzelne zufällige Zeichenfolge (nennen wir es $S$) wird von Länge erstellt $l$ (($l < L$).

Was ist die Wahrscheinlichkeit, dass genau $k$ Zeichenfolgen aus zuvor ausgewählten zufälligen Zeichenfolgen beginnen mit dem $S$?

Ich weiß, dass ich leicht eine Computersimulation durchführen kann, aber gibt es eine geschlossene Formel, die nur davon abhängt $N$, $L$, $l$ und $k$?

Dieses Problem tritt in einigen Anwendungen zur automatischen Vervollständigung von Zeichenfolgen auf.

Answer 1

Lassen $p$ sei die Wahrscheinlichkeit, mit der ein String beginnt $S$. Die Wahrscheinlichkeit, dass genau$k$ von $N$ Zeichenfolgen beginnen mit $S$ ist $$\binom Nkp^k(1-p)^{N-k}$$ weil dort sind $\binom Nk$ Möglichkeiten zu wählen, mit welchen Zeichenfolgen begonnen wird $S$.

Jetzt $p=26^{-l}$ da für jeden der ersten $l$ Buchstaben der Zeichenfolge, die Wahrscheinlichkeit, dass es dem entsprechenden Buchstaben von entspricht $S$ ist $\frac1{26}$. Die endgültige Antwort lautet also$$\binom Nk26^{-lk}\left(1-26^{-l}\right)^{N-k}$$

Answer 2

Die anderen Antworten haben bereits die genaue Antwort gegeben, die binomial verteilt ist. Da jedoch die Anzahl der Zeichenfolgen wahrscheinlich sehr groß ist und die Wahrscheinlichkeit einer Übereinstimmung mit jeder Zeichenfolge sicherlich sehr gering ist, kann die Poisson-Näherung auch hier sehr nützlich sein.

Aus dem $N$ Zeichenfolgen, die erwartete Anzahl von Übereinstimmungen ist $\frac{N}{26^l}$. Wenn wir uns durch eine Poisson-Zufallsvariable mit Mittelwert annähern$\frac{N}{26^l}$, die Wahrscheinlichkeit, genau zu bekommen $k$ Übereinstimmungen ist $$ e^{-N/26^l} \cdot \frac{(N/26^l)^k}{k!}. $$ Dies liegt sehr nahe an der Binomialwahrscheinlichkeit, ist jedoch einfacher zu berechnen.

Answer 3

Die Wahrscheinlichkeit, dass eine zufällig generierte Zeichenfolge mit der Zeichenfolge beginnt $S$ entspricht

$$p = \Big(\frac{1}{26}\Big)^l$$

weil jeder der $l$ Zeichen müssen übereinstimmen, und die Wahrscheinlichkeit einer Übereinstimmung ist $1/26$ für jedes Zeichen.

Also die Wahrscheinlichkeit, dass genau $k$ des $N$ zufällige Zeichenfolgen beginnen mit $S$ entspricht

$$\binom{N}{k}p^k (1-p)^{N-k} = \binom{N}{k}\Big(\frac{1}{26}\Big)^{lk}\Big(1 - \Big(\frac{1}{26}\Big)^l\Big)^{N-k}$$

Beachten Sie, dass dies völlig unabhängig vom Wert von ist $L$, so lange wie $L > l$. Das liegt daran, dass nur der erste$l$ Zeichen jeder zufälligen Zeichenfolge haben einen Einfluss darauf, ob jede Zeichenfolge mit beginnt oder nicht $S$.