1

Given a string of 10 random digits in the range 0-9 what is the probability of another random 10 digit string (in the same range) matching where a match can have an edit distance of 2.

By edit distance I mean that a string could be said to match if you could arrive at the correct answer by making two edits. For example for the string:

1111111111

The string 1111111142 would be considered a match as by editing the last two numbers it is possible to get the correct sequence.

Ben
  • 91,027
  • 3
  • 150
  • 376
HAL
  • 13
  • 2

1 Answers1

3

The chance of any given digit matching is 1/10 and not matching is 9/10.

For exactly 2 edits, you need 8 matches, 2 non-matches, and there are 10 choose 2 ways to arrange those. So $P={\frac{1}{10}}^8 \cdot {\frac{9}{10}}^2 \cdot \binom{10}{2} \approx3.6 \cdot 10^{-7}$

For 2 or fewer you would add the less likely 1 and 0 terms to get about $3.7 \cdot 10^{-7}$

Of course this assumes all random digits in each string are independent of one another.

MikeP
  • 2,117
  • 8
  • 9
  • I'm using the formula you gave me but I have realized that I am unclear on the $c= \frac{10}{2}$ term. Would you be able to give more detail on it. I am using the formula to calculate the probability when allowing 5 edits would it be $P=\frac{1}{10}^5\cdot\frac{9}{10}^5\cdot(\frac{10}{5})$ – HAL Oct 02 '16 at 10:13
  • Sorry HAL! Are you familiar with choose notation? In the chase of $10\choose2$ it's $\frac{10!}{2!\cdot (10-2)!}=45$. For $10\choose{5}$, $\frac{10!}{5! 5!}=252$. – MikeP Oct 04 '16 at 16:02
  • https://en.wikipedia.org/wiki/Combination – MikeP Oct 04 '16 at 16:04