# Probability of n columns of an array being identical

I'm trying to calculate the probability that p (or more) columns, of an n x m matrix, each element of which can have q values, will be identical. The value of elements are assigned randomly, with equal probability.

So for instance, elements of the n x m (5 x 7) matrix below can have any of q (4) different values. p (2) columns have identical values. What is the probability that p or more columns had identical values?

+----+----+----+----+----+----+----+
| a  | c  | t  | g  | a  | a  | c  |
| a  | t  | t  | c  | c  | c  | a  |
| a  | a  | t  | a  | g  | a  | g  |
| a  | t  | t  | c  | a  | a  | c  |
| a  | t  | t  | g  | a  | c  | g  |
+----+----+----+----+----+----+----+


So far my logic is:

• The probability that any column won't have identical values is $1- \frac{1}{q^\left(n - 1\right)}$
• There are $\frac{m!}{\left(m-p\right)! p!}$ ways to have $m-p$ columns that don't match
• The n-pick-k formula is usually written $\frac{n!}{k! \left(n - k\right)!}$
• In my example, we replace $n$ with the number of columns $m$; and $k$ with $m-p$, because we want to know how many ways there are to not have matching values
• The probability that $m-p$ columns won't have matching values is therefore $\left(1-\frac{1}{q^\left(n-1 \right)} \right) ^\left(m-p\right)$

This can't be right, though: The example above, in which 2 columns have the same value, is not terribly likely. But the formula I wrote evaluates to

$$\left(1- \frac{1}{4^4} \right) ^\left(5 \right) = 0.98$$

which must be way too high.

$$\left(\frac{1}{q^\left(n-1 \right)} \right) ^\left(m-p\right)$$

gives me numbers that seem reasonable, but I can't justify why that would be the right equation.

• So that others can understand this question better, it would help to call such columns "constant." "Identical" is usually understood to be a comparison between two objects--columns in this case--rather than a characterization of a single object. And don't you want to refer to "p" in the title rather than "n"? – whuber Sep 26 '17 at 16:59

Alright, here's my go at it... The probability of any single column having all identical values is $\frac{q}{q^n}$, which I see you already have. (You can think of any specific combination of bases in a column as having prob of 1/q^n, and then you're interested in q of those outcomes).

You then spread these independent samples across m columns, each of which you can think of as a super-biased coinflip where the probability of "success" is this $\frac {q}{q^n}$ probability. This sets up a binomial distribution!

By definition of binomial distribution, the probability of getting $k$ successes given $n$ independent trials, each with $p$ probability of success, is $\binom nk p^k(1-p)^{n-k}$.

So the probability of getting 2 columns with all identical values in your 5x7 matrix? Start here: $$P_{column} =\frac{4}{4^5} = 0.015625 = p$$

Then: $$P_{twoidentical} = \binom 72 p^2(1-p)^{7-2} = 0.004738733$$

Mind that this is the probability of getting exactly two identical columns, and you'd have to sum up the probabilities of the higher values (k = 3,4,etc) if you're interested in the probability of having "two or more" identical columns (aka using the cumulative distribution function for binomial distributions, which is just this summation).

This whole process can easily be extended for nonrandom base selection (e.g. if you're dealing with taxa of varying relatedness).

Hope this helps / is correct (after all, that's a pretty low probability) / is what you were looking for!