1
$\begingroup$

More generally, if an array of random integers (size N), and another array of random integers (size M), "overlap" by R numbers (have them in common): What is the chance that the smallest of one is the smallest of the other? You can assume these integers are in a finite interval, all positive.

Edit: The numbers are uniformly distributed, bounded arbitrarily (say by 1000000), and chosen without replacement. And in the first case, with 50 random integers, you know that the second set contains the smallest element selected from the first. In the general case, you know the smallest in the first set is present in the "R" overlap between the two sets.

$\endgroup$
  • 2
    $\begingroup$ The question is slightly ambiguous because you don't specify a distribution fot the integers and you don't say what happens when two of them are the same. From what I suspect the intention of your question to be, I'd suggest to specify that $N$ real numbers are drawn independently and uniformly from $[0,1]$. $\endgroup$ – joriki May 8 '13 at 17:06
  • $\begingroup$ Let us assume you draw a set $A$ of $N$ numbers and a set $B$ of $M$ numbers uniformly out of $\{1,2,3,\ldots P\}$, each without replacement, the chance that $1$ is in both of them (and therefore a matching smallest) is $\frac {NM}{P^2}$ The chance that $1$ is in neither and $2$ is in both is $(1-\frac NP)(1-\frac MP)\frac {NM}{(P-1)^2}$ You can continue in this vein, but the expressions get messier and messier. I don't know an easy way to sum them up. This ignores the constraint that $R$ of the numbers match between $A$ and $B$. $\endgroup$ – Ross Millikan May 8 '13 at 17:23
  • $\begingroup$ @Ross: For this sort of problem it's often useful to ignore the concrete numbers and focus only on their ranking (see my answer). $\endgroup$ – joriki May 9 '13 at 9:18
2
$\begingroup$

You have $99$ numbers and two sets of $50$ of them that share exactly one number. Up to permutations of the non-shared numbers within the two sets, there are $99\binom{98}{49}$ different possible rankings of the numbers, and they're all equally likely.

Here are two different ways in which to determine the probability of the shared number being the smallest of both sets under the condition that it's the smallest of a particular one of the sets:

$1)$ Start out with the ranking of the set in which the number is known to be the smallest, and successively insert the $49$ remaining numbers of the other set. In each insertion, every possible place of insertion is equally likely. The shared number is the smallest if none of the numbers is inserted below it. The probablity for this is

$$ \frac{50}{51}\cdot\frac{51}{52}\cdots\frac{97}{98}\cdot\frac{98}{99}=\frac{50}{99}\approx\frac12\;. $$

$2)$ Count the rankings that fulfill the two sets of requirements and divide the two counts.

The count of rankings in which the shared number is the smallest of both sets is easy: The shared number has to be the smallest of all the numbers, and the rest can be ranked arbitrarily, which makes $\binom{98}{49}$ possibilities.

To find the count of rankings in which the shared number is the smallest of a particular one of the sets, we can sum over all possible ranks of the shared number: If the shared number is the $k$-th smallest, there are $\binom{99-k}{49}$ possible rankings, so the total is

$$ \sum_{k=1}^{50}\binom{99-k}{49}=\binom{99}{49}\;, $$

and the desired probability is the quotient

$$ \frac{\displaystyle\binom{98}{49}}{\displaystyle\binom{99}{49}}=\frac{50}{99}\;. $$

In the general case, you can just ignore the additional shared numbers. So assume you have $N$ numbers and $M$ numbers sharing one number, which is the smallest of the $N$ numbers, and you want to know the probability of it also being the smallest of the $M$ numbers. Then method $1)$ above yields

$$ \frac{N}{N+1}\cdots\frac{N+M-2}{N+M-1}=\frac{N}{N+M-1}\;. $$

Note that the cases $N=M$ (above), $N=1$ and $M=1$ come out right.

$\endgroup$
  • $\begingroup$ Thank you very much! I realize now, however, that this is simply given by the definition of the probability of A given B: The probability that the number is the smallest of both: 1/99 The probability that it was the smallest of the first: 1/50. The ratio: 50/99 $\endgroup$ – Jim May 9 '13 at 16:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.