0

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 ?

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

2 Answers2

1

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)}$.

user133281
  • 16,073
0

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 $$

Carser
  • 3,400