# Probability of matching

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 ?

• 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. – MJD Mar 7 '14 at 18:46
• What is the number of different characters possible? – user133281 Mar 7 '14 at 18:46
• Can S1 or S2 have duplicates? How are S1 and S2 picked with replacement or not? – bobbym Mar 7 '14 at 19:49

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)}$.
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$$
• I think you halfway assumed that $k=26$. – user133281 Mar 7 '14 at 18:59