0
$\begingroup$

Let the alphabet from which characters are taken is of size 'k'

If a string S1 contains 'n' characters

String S2 contains 'm' characters (m << n)

What is the probability of a character in S1 is equal to a character in S2 ?

$\endgroup$
  • $\begingroup$ It is impossible to say unless you say what alphabet the characters of $S_1$ and $S_2$ are drawn from. If $S_1$ and $S_2$ are strings over xes, for example, then the probability is 1 unless one of the strings is empty. $\endgroup$ – MJD Mar 7 '14 at 18:46
  • $\begingroup$ What is the number of different characters possible? $\endgroup$ – user133281 Mar 7 '14 at 18:46
  • $\begingroup$ Can S1 or S2 have duplicates? How are S1 and S2 picked with replacement or not? $\endgroup$ – bobbym Mar 7 '14 at 19:49
1
$\begingroup$

If you mean the corresponding character should be equal: the alphabet contains of $k$ characters, there is for each position a probability of $1/k$ of a match. The probability that there is no match equals $(1-\frac{1}{k})^{\min(m,n)}$, hence the probability of at least one match is $1-(1-\frac{1}{k})^{\min(m,n)}$.

$\endgroup$
0
$\begingroup$

Given an alphabet of $k$ characters, the probability of there being $any$ match between $any$ character in $S1$ and $any$ character in $S2$ given $equal$ probability of each character, is $$ 1 - (\frac{1}{k} \frac{1}{k-1} ... \frac{1}{k-m})^n $$

$\endgroup$
  • 1
    $\begingroup$ I think you halfway assumed that $k=26$. $\endgroup$ – user133281 Mar 7 '14 at 18:59
  • $\begingroup$ Ha, yes, but only half way :) $\endgroup$ – Carser Mar 7 '14 at 19:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.