Probability of combinations that share at least 3 items I have a question about probabilities that I can't get my head around. Suppose I would like to generate a combination of 7 elements, where each element is randomly drawn from a set of n alternatives. For example, the first element has possible alternatives A1, A2, ... A10, the second element has possible alternatives B1, B2, ... B10, etc. The number of possible alternatives for each element is the same, and the order of the elements is also always the same. For instance, three random examples could look like this:


*

*A5 B2 C6 D2 E7 F1 G2 H6

*A1 B3 C8 D9 E9 F2 G2 H7

*A2 B1 C5 D3 E2 F2 G2 H7


I would like to know two things: 


*

*What is the probability that 2 randomly drawn combinations have the same alternatives for at least three elements? For example, examples (2) and (3) above share 3 alternatives (F2 G2 H7), but (1) and (2) do not (they share only G2).

*If I draw 1,000,000 such examples, what proportion of these examples will share at least 3 elements with another example in the set, on average?


Thanks a lot for your help!

This is binomial. The probability the $i^{th}$ character matches is $p=\dfrac{1}{n}$. Thus the probability of exactly $x$ matches in a character length of $k$ is
$$P(X=x) = {k\choose x}\left(\dfrac{1}{n}\right)^x\left(1-\dfrac{1}{n}\right)^{k-x}$$
At least three matches would be
$$P(X\ge 3) = P(X=3)+\cdots+P(X=k) = \sum_{x=3}^k {k\choose x}\left(\dfrac{1}{n}\right)^x\left(1-\dfrac{1}{n}\right)^{k-x}$$
Your second question is more involved. See the birthday problem and notice it is essentially the same. With "two people having the same birthday" is your "shares at least three characters".
