There are 2^m possible sequences of tosses, so the question is the same as if each student chooses one of 2^m objects at random (assuming all the coins are unbiased).

The usual way to handle such problems is to calculate the probability that all are different and subtract the answer from 1.

Choose one of the group of r students. The probability that all of the other group are different from this one is 1/2^m(k-r). They all have to be different from any other member of the group of r. As they are all independent, the probability of no overlap is 1/2^mk. As this isn't dependent on r, I wonder if I have over simplified. To check try an exhaustive listing of possibilities when m = 2 and k = 5 for r = 1 and 2.

Question 2 seems to require the use of this result, but  chi-squared goodness of fit test might be more powerful especially if m is large and there is almost certainly no overlap unless each group has one or more extremely biased coins.

I think I was too hasty. But it is certainly a useful simplification to forget about individual coin tosses and consider samples of r and k-r observations from a set of n objects.

Dear Prof. Terry Moore,

Thanks for your answer.

Besides,  do we really want to have some conditions/relations between (k, m, r ) ?

Thanking you,

B G Manjunath

I don't think any conditions are necessary but if m is much smaller than r or k-r the probability of overlap is much greater.

My answer was certainly wrong. I will change the notation. Let n = 2m, the number of possible sequences of throws (or more generally let each student choose one of n objects). Let s = k-r. Call the group of r, group 1 and the group of s, group 2.

If n >> r then it is almost certain that the group 1 students have different objects (sequences). Then for no overlap the group 2 students must avoid the particular r objects chosen by group 1. (I don't care which set of r objects so we don't need to consider the probability for group 1 (except that it is close to 1 that the objects are all different). This probability is (1 - r/n)s as none of group 2 may have any of the r objects chosen by group 1. This should be a good approximation for large n but it cannot be exact because the same argument gives (1 - s/n)r when n >> s. However, to first order terms, these are both equal to 1 - rs/n which is valid if n >> rs. So for this approximation the probability that there is an overlap is rs/n.

For small n we need to account for ties among group 1. The probability of no overlap when group 1 have chosen exactly t of the n objects is (1 - t/n)^s. We need to multiply by the probability that group 1 have chosen exactly t objects and sum from t=1 to min(r, n). I'm not confident about the next step. It seems to give

• sum_t=1^min(r, n) ( nCt (t/n)r (1 - t/n)s )

but by symmetry we also should get

• sum_u=1^min(s, n) ( nCu (u/n)s (1 - u/n)r )

and it does not seem likely that these are equal except when n

My error is as follows: the probability of choosing exactly t objects is the probability that all are in that set of t, but are in no smaller set. I'll leave you to work out the consequences, but I'll have another go if you get stuck.

I look forward to seeing your calculation.

Dear Prof. Terry Moore,

Thanks for your detailed answer.

Will start computing from my end and get back to you shortly.

Thanking You,

BGM

Take as Terry Moore n=2m. I'll calculate the probability of the complementary event, that there are no repetitions among the last k-r series.I am assuming that n>k.

Suppose that there are i different series among the first selected r, 1

By the way, since the r persons are randomly selected, I wouldn't bother about them when checking if the coin is fair. you have m*k coin tosses, so you should use them all and do a standard binomial test on all coin tosses, or the chisquare test as Terry Moore suggests.

Argh, sorry made en error as well in the last part. Combinatorics are pesky. I did something like this properly some time ago, Will be back when I can check it out in the office tomorrow.

Hello again,

The probability that there are i different series among the first r is

Bin(n,i)*sumj=0i(-1)i+j*(j/n)r

which follows from Theorem 3 in the attached working paper.

This gives the probability of no repetition as

sum_{i=0}^r (1-i/n)^{k-r}*Bin(n,i)*sum_{j=0}î Bin(i,j)* (-1)^{i+j} (j/n)^r

=n^{-r}*sum_{i=0}^r (n-i)^{k-r}*Bin(n,i)*sum_{j=0}î Bin(i,j)* (-1)^{i+j} j^r,

which you need to subtract from 1 to get your probability. Sorry about the mess, but it is a long time since I dealt with this :-( .

Regards,

Anders Stockmarr

Perhaps we can apply the approximation methods used for the classical birthday problem to this situation.  Suppose, for example, that the class is of size 20 and every one tosses the coin 20 times.  Then we have about 1 million possible sequences. Using the approximation p = (n^2)/2m, in this case p is approximately zero. For p to be appreciable we would need a small number of tosses, say less than 10.

Q2, about a fair coin is a different matter altogether. We have km independent tosses in all, and so the number of heads assuming a fair coin should be approximately 0.5km.  The standard error for a fair coin would be the square root of 0.25km, call this SE, and so we might suspect that the coin were unfair if the total number of heads were more than about 2 SEs away from 0.5km.

Milan: I thought about the birthday problem too. It does have some similarity.

Anders: I'll be away fro a few days and don't have time to look at your solution in detail, but it looks right. Meanwhile I thought of the following to fill the gaps in my solution.

See: http://www.math.utk.edu/~wagner/papers/comb.pdf section 5.1.

The solution is the sum from t = 1 to min(r, n) of

• nCt ( t+r-1Cr-t  /  t+r-1Cr-1 ) (t/n)r (1 - t/n)s
• = ( n!(r-1)! / ( (n-t)!(r-t)!(2t-1)! ) ) (t/n)r (1 - t/n)s

which is still a little unsatisfactory as it is not obvious from the formula that we can interchange groups 1 and 2. Also, if we omit the factor (1 - t/n)s, the sum should be 1. So there are some identities waiting to be discovered.

Hello  Terry,  Anders and Milan,

I was down with cold so I couldn't look into those computations.  Will start computing them.

Meanwhile, as we know k > 1,in particular for k = 2, m = 1 and r = 1.

what happens to Q1 ?

So, our computation must match this !

@ Milan: Limiting scenario will be interesting once we have solution for finite (k,m,r).  One such question will be, what will be the limiting probability when  m tends to infinity ?

Is it necessary to use combinatorials or approximation? I may be well off track but with minor changes I think Terry's initial approach works (and is computationally simpler)

The test for fair coins should be done first. This is complicated because the question implies many coins; we have low power to detect a few unfair among many fair coins; perhaps it is better to make all subjects toss the same coin.

Assuming fair coins...

Let Pr(two randomly chosen individuals from k identical sequences) =  2-m = 1/n; where n = 2m

Pr(a member in set k-r has an identical sequence to a member of set r) = 1 - 1/n 

Pr(a member of the k-r set differs from all in set r) = (1-1/n)r

Pr(all in k-r differ from all in r) = (1-1/n)(r(k-r))

Pr(at least one sequence in r occurs in k-r) = 1-(1-1/(2m))(r(k-r))

Is that not what we are looking for?

Below is a graph of behaviour up to (m, k, r) = (9, 10, 9); starting with (1, 2, 1), (1, 3, 1), (1, 3, 2), (1, 4, 1)... (it could be prettier with Pr, m, r and k as separate dimensions; perhaps using red-blue gradient for Pr). As expected Pr = 0.5 at (1, 2, 1) . Pr decreases with m, increases with k and is maximised at r = k/2. It is much more sensitive to increasing the number of tosses (m) than the number of candidates. For a sequence of 50 tosses you will need to sample tens of millions of sequences in each set before there is any reasonable chance of duplication. For much longer sequences you won't find a match among trillions.

This problem might have useful applications to DNA sequence / genome analysis (matching 2-state SNP haplotypes)

Michael: you may be right. My initial worry was 'what if the r units are not all different?' Therefore I considered the cases, t different values for each possible t.

But your post inspires the following argument that has the required symmetry. Number the n = 2m possible sequences (or more generally, the n objects). If the r and s units don't have object number 1, then neither have it or one of them does and the other doesn't. P(object 1 in set of r) = 1 - 1/nr. P(object 1 in set of s) = 1 - 1/ns.

P(not both having object 1) = 1 - (1 - 1/nr)(1 - 1/ns).

P(not both having a common object)

= P(not both having object 1 or object 2, or ...) = n(1 - (1 - 1/nr)(1 - 1/ns)

= n(1/nr + 1/ns - 1/nr+s) = 1/nr-1 + 1/ns-1 - 1/nr+s-1.

In the original notation, of course, r+s = k.

Is this correct?

Sorry, I can answer my own question: my answer is not correct, but I think it's on the right track. I made several errors, e.g., I meant 'and' not 'or'. Anyway the events are not mutually exclusive so I shouldn't have added.

• P(both samples have object 1) = (1 - (1 - 1/n)r)(1 - (1 - 1/n)s)
• P(at least one sample doesn't have object 1) = 1 - P(both)

This applies to any single object. The events 'both have object h' for each h, are not mutually exclusive so we can't use the addition rule. We can use the inclusion-exclusion principle. The events 'not both have object h' for each different h, are not independent so we can't use the multiplication rule but we can use conditional probabilities.

I'll use the former method. We need events such as 'both have chosen all of the objects in the set {1, 2, ..., t}'. The probability of this event is

• (1 - (1 - t/n)r)(1 - (1 - t/n)s).

All such subsets for the same value of t are mutually exclusive events.

The probability of overlap is therefore the sum for t = 1 to min(r, s, n) of

• nCt (-1)t (1 - (1 - t/n)r)(1 - (1 - t/n)s)

i.e. (n times the probability that both have object 1) - (n(n-1)/2 times the probability that they both chose objects 1 and 2) + - ... up to the number that they could possibly share given the sample sizes and the number of available objects.

This is similar to my earlier method, but I have preserved the symmetry between the two groups.

I sincerely hope this simplifies (perhaps to Michael's answer) but, if not we get a sequence of approximations.

If someone wants to calculate Michael's and my answers for a few special cases we can at least see if we agree.

We might be able to simplify this a little

• nCt (-1)t (1 - t/n)r + (1 - t/n)s - (1 - t/n)r+s)

and maybe the sums of the terms simplify.

Sorry again. Obviously (-1)t should be (-1)t+1.

(The problem with replying directly to a mailing list is that I can't put the reply away for a while and come back refreshed. Perhaps I should write in Open Office and copy into a message after debugging.)

This method might generalise to any number of groups. Three possible generalisations: (1) they all have at least one sequence in common, (2) every pair has at least one sequence in common, (3) at least one pair have at least one common sequence. I think the first is easiest.

I have put Michael's and my formulae into a spreadsheet and I'm ashamed to say that mine can give negative probabilities. I need to think again.

Hi Terry, 

I think there is a problem with your inclusion of t in ((1 - (1 - t/n)r)(1 - (1 - t/n)s)

I think it should be  a power. That is, the probability that they share sequence 1 AND sequence 2 AND...sequence t, all of which have the same probability. With sequentially numbered sequences in K:

• Pr(subset T{1, 2, ...t} occurs in both R and S) =  (1 - (1 - 1/n)r)(1 - (1 - 1/n)s)t

 Given a fair coin it is the same for sharing any set of t sequences (which is important because the shared set may not necessarily be a consecutive series - more likely it will be a single sequence, especially with increasing m)

But this is an extension of the problem, which only requires that any sequence in R also occurs in S, regardless of how many times it occurs in each of these (e.g. all heads would fit the criterion for any m, r and k).

Hi Michael,

You are right. There are all sorts of traps here. Multiplying the non-overlap probabilities requires independence, adding the overlap probabilities requires mutually exclusive. Having made sure the events are mutually exclusive I wanted to add so much that I added the wrong probabilities. I think your solution also assumes independence which does not hold.

I'm going to run a simulation to check your solution and whatever I think of next.

Hi Michael,

I ran a simulation in Python (my very first Python program). At first it agreed with your solution, but that was for n not much greater than r and k-r. When I tried r = 3, s = 5 (k = 8) and n = 128 (m = 7), your formula gave results a bit low (0.04596) compared with my simulation (0.11132 for 100000 trials). I think lack of independence is the problem. Although individual observations are independent, matches are not.

Here's the program:

import random

random.seed()

def trials(n, r, s):

    if r > s:

       r, s = s, r

    a = set()

    for i in range(r):

       a = a | {random.randrange(n)}

    for i in range(s):

       if random.randrange(n) in a:

          return 1

    return 0

def pMatch(n, r, s, M):

    matches = 0

    for i in range(M):

       matches = matches + trials(n, r, s)

    return matches/M

pMatch(128, 3, 5, 1000000)

[Indentation is significant in Python: annoying because this editor took the leading spaces out when I pasted my code]

My mistake, Michael. Your formula does agree with my simulation (I reported the wrong case (128, 3, 2). I've now added your solution and the approximation r*s/n to the simulation. Change the last return statement to

• return 1 - (1-1/n)**(r*s), r*s/n, matches/M

Now I'm fairly sure you're right despite my reservations about independence.

As my simulation agrees closely with Michael's formula, we can say this is solved. I didn't understand the argument because the probability of matching one of the set of k-r sequences with one of the set of r sequences depends on the size of the former set. So I really needed to convince myself of the logic.

I think the answer lies in looking at pairs of sequences (or objects). Any two independent pairs have probability 1 - 1/n of not matching. There are rs pairs. If we are allowed to multiply then we get Michael's answer.

If we arrange the pairs in a matrix, all those in the same row have the same first sequence, and all those in the same column have the same second sequence. This is because of the way they are constructed (chance might add more such pairs). That was my concern.

However, any two pairs with the same first sequence have independent second sequences and vice-versa. So whether the two sequences are the same or not is independent for each of the rs pairs.

Dear Terry Moore, Michael and all,

I thank each and everyone  for all your efforts  and valuable time for solving the

problem.  I will start screening the answers and try to simulate the same in R as well.

I am planning to share this question and answers in arXiv.org, of course with proper documentation.

@ Terry Moore and Michael :  Please let me know your feedback.

Thanking you,

B G Manjunath

Glad to have helped, but Michael gets the most credit.

I was still worried obout independence. See:

https://en.wikipedia.org/wiki/Independence_%28probability_theory%29#Pairwise_and_mutual_independence

However, I now see the justification for Michael's multiplication. Consider pairs of observations, the first from the first sample and the second from the second sample. The events 'first member = second member' for a given first member and each second member. These are independent because the second members are independent. We can multiply the probabilities to give P[no overlap with first member] = (1 - 1/n)s. This is just the case r = 1 that we all solved.

Now the first members are all independent so the compound events above are independent. This justifies multiplying these probabilities. This is the case that Michael solved. I was too blind to see why this was valid.

Too make up for being so stupid, I'll generalise. The generalisation could be useful for comparing DNA profiles when some profiles are more common than others.

Independence and random sampling are the only conditions we need.

We have already seen that the result applies to any set of objects, not just sequences of coin tosses. Let the pairs of observations come from any discrete distributions (they don't even have to come from the same distribution). If the two sets of objects are different, we can extend the domains and assign probability 0 to any extra objects. So without loss of generality we assume a common set of object with probabilities P1(i) and P2(i). One random pair of obserations match at object i with probability P1(i) P2(i). Therefore the overall matching probability p is the sum of these over the common set of objects.

The rest of the argument is exactly the same as before: if r objects are randomly chosen from the first population and s are independently randomly chosen from the second population, the probabilty that at least one from the first sample is the same as at least one from the second is 1 - (1-p)rs.

Thanks Terry & BG,

It is an interesting problem with potential applications. Yes, even with an unfair coin outcomes in the second set are not contingent on prior results (although they do affect our assessment of bias). Python rules!