# Probability that n sequences agree in a certain percentage of them

I am trying to work out what the probability that $$n$$ coin toss sequences of length $$k$$ match in $$m$$ spots. The simplest example would be two sequences of a given length. If I toss a coin 100 times, twice, how many of positions in the sequence will match? My intuition tells me that if I have a fair coin (so $$p = 0.5$$) then I should expect two random sequences to on average, agree in 50% of their locations. I also think that I am correct in saying that the probability of two sequences of length $$k$$ being in complete agreement is $$p^q (1-p)^{(k-q)}$$ where $$q$$ is the number of heads in the sequence.

However, I am unable to formalize my particular question (which is a fraction of the sequence, independent of subsequence length), nor am I able to extend this to the probability that 3 sequences of a particular length agreeing in 50% of their locations. Any help would be appreciated.

Edit: To be more specific, I am having difficulty with the combinatorics involved when the probability $$p \neq 0.5$$. Suppose the first sequence contains 2 heads. It can be $$HHTT$$ or $$HTHT$$ or $$THTH$$ etc.. it doesn't matter. Now I want to calculate the probability that another sequence matches $$0, 1, 2, 3, \mathrm{or}\ 4$$ of those outcomes. I have chosen $$HHTT$$ as the first sequence and enumerated the possible matching sequence for each case.

In the case of 0 matching outcomes, the only possibility is

$$\begin{array}{cccc} & T & T & H & H \\ \end{array}$$

In the case of 1 matching outcome, the possibilities are:

$$\begin{array}{cccc} & H & T & H & H \\ & T & H & H & H \\ & T & T & T & H \\ & T & T & H & T \\ \end{array}$$

In the case of 2 matching outcomes, the possibilities are:

$$\begin{array}{cccc} & H & H & H & H \\ & H & T & T & H \\ & H & T & H & T \\ & T & H & T & H \\ & T & H & H & T \\ & T & T & T & T \\ \end{array}$$

In the case of 3 matching outcomes, the possibilities are:

$$\begin{array}{cccc} & H & H & T & H \\ & H & T & T & T \\ & H & H & H & T \\ & T & H & T & T \\ \end{array}$$

Finally, for all 4 matching outcomes, the only possibility is:

$$\begin{array}{cccc} & H & H & T & T \\ \end{array}$$

Now the number of combinations for matching $$m$$ outcomes for a sequence of length $$k$$ is given by $${k\choose m}$$. The only problem is, because the probability is not $$0.5$$, I need to enumerate how many of those contain $$x$$ number of $$H$$, so I can sum up $$p^q (1-p)^{(k-q)}$$, each multiplied by the appropriate prefactor. However, I am unable to identify the appropriate pattern. This is the main difficulty I am having.

Any help towards figuring out a formula for the probability of two (or more!) sequences of length $$k$$ matching in $$m$$ spots, where the probability of each outcome is not 0.5 would be greatly appreciated.

Thanks!

• Did my answer address the clarifying edit? – Anirudh Jul 4 at 15:30
• Yes it did, thank you! – pragmatist1 Jul 5 at 15:07

We are going to imagine that the set of all our rolls form a grid.

So if I rolled HTTH, TTTH, HHHH. The grid created would be:

HTTH
TTTH
HHHH


Now when we are looking for match we can just look at each column of our grid individually. If every element in the column is the same we have a match.

Now we can rephrase our problem in terms of our grid

We want to calculate the probability of getting:

• $$m$$ matching columns
• In a grid with $$k$$ columns and $$n$$ rows
• With $$p$$ being the probability any element is a heads

We can know view our problem as a simple case of binomial probability with each of our columns being a trial.

There are $$\binom{k}{m}$$ ways we can select the $$m$$ columns we want as our matching columns.

The probability of getting a matching column is $$p^n+(1-p)^n$$ since we can have all heads or all tails in our column.

And of course the probability of not having a match in a column is $$1-(p^n+(1-p)^n)$$

This leaves us with

$$\binom{k}{m}(p^n+(1-p)^n)^m(1-p^n-(1-p)^n)^{k-m}$$

As our final probability.

I also wrote a program in java to verify this and the formula seems to be correct you can look at the code yourself here.

When you are matching two sequences of a fair coin it doesn't matter what the first one is. It might as well all be heads. Each toss matches with chance $$0.5$$ The chance of perfect agreement is just $$\frac 1{2^n}$$ where $$n$$ is the total number of tosses. Similarly, the chance of matching in $$m$$ out of $$n$$ positions is $${n \choose m}\frac 1{2^n}$$. You are correct that this is maximized at $$50\%$$ matches. For reasonably large $$n$$ the distribution of matches is approximately normal with mean $$0.5n$$ and standard deviation $$\sqrt {\frac n4}$$

When you talks of three sequences agreeing, assuming you mean they all have a common value at a given position, the chance is $$25\%$$. The first one can be anything and the others each have $$50\%$$ chance to match it. You would therefore expect triple matches in $$\frac 14$$ of the locations.

• Thank you, that makes sense. Could you elaborate on the triple matches (and more general number of matches). Why would it be 25% and not 33%? How would this translate to an actual distribution? So for 2 sequences we have binomial. How about n sequences? – pragmatist1 Apr 25 at 18:22
• Also, can you elaborate on how this would translate to an unfair coin? – pragmatist1 Apr 25 at 18:31
• Because if the first is heads, you have $\frac 12$ chance the second is heads and again $\frac 12$ chance the third is heads. The chance they are both heads is the product of these. For an unfair coin you need to condition on the first flip. If the chance of heads is $p$ the chance of a triple match is $p^3+(1-p)^3$ – Ross Millikan Apr 25 at 18:32
• I would appreciate it if you could explicitly elaborate on the analytical expression for those cases. I'm having a difficult time getting something that matches numerical experiments. If I have an unfair coin, then I expect I need to know how many heads/tails there are in the reference sequence, not necessarily their exact positions (even though I have that info). Once I have that, how do I go about calculating the probability of m matches for 2, then 3 sequences? Thanks again! – pragmatist1 Apr 25 at 22:08
• Yes, however this is not my main issue. I have edited my original question with an extensive elaboration on where I am running into trouble, which I do not believe is answered by your comments (unless I am somehow missing it, in which case I would definitely appreciate clarification). Thanks! – pragmatist1 Apr 26 at 0:03