# Calculate the probability of a collision between these two functions?

$f(x) =$ Choose a random number between $1$ and $100$ (inclusive)

$g(x) =$ Choose a random number between $1$ and $200$ (inclusive)

What is the probability that $f(x) = g(x)$?

Here is my working:

$$P(f_1(x) = f_2(x)) = \frac1{100}$$

$$P(g(x) = f(x)) = \frac{100}{200} \cdot \frac1{200} = \frac1{400}$$

Is my working correct?

• What has $f_1(x) = f_2(x)$ got to do with it? – copper.hat Feb 19 '15 at 18:29
• f1(x) = f2(x) was a way of saying: Well, what if g(x) were actually identical to f(x), in which case there is a 1/100 chance that the same number appears twice. Then if you double the size of possible values of f(x) you get all possible values from g(x), which led me to the second step. I wouldn't argue that this is absolutely correct reasoning, but it was my way to start reasoning about the problem. – Trindaz Feb 19 '15 at 18:42
• In my defense: my first parse at this actually resulted in 1/200 too, but it seemed counter-intuitive at first to accept that the size of the first set of possible values had no impact on the probability of a collision. I suppose after all it doesn't make much difference, and the probability is mostly dependent on the size of that second set, when the first set of values is entirely contained in the second set of possible values. – Trindaz Feb 19 '15 at 18:55

Assuming that by "number" you mean "integer," and by "random" you mean "uniformly at random," AND ASSUMING THAT THE CHOICES ARE INDEPENDENT, then the desired probability is $$\sum_{k=1}^{200} \Pr[X = k]\Pr[Y = k] = \sum_{k=1}^{100} \frac{1}{100} \cdot \frac{1}{200} + \sum_{k=101}^{200} 0 \cdot \frac{1}{200} = \frac{1}{200}.$$

I think this is a slightly more intuitive way of looking at the question:

Suppose $f (x)=k$. Once we have chosen $k$, there are $200$ possible values for $g (x)$, one of which is $k$, hence we get an answer of $\frac{1}{200}$.

• and alternately --- suppose $g(x)=k$. Half the time there's zero chance of it being $f(x)$. The other half it's $1/100$. Thus in total it's $1/200$. Not as clean as this argument, but helps give an idea of what to do if the two ranges don't overlap. – Joel Feb 19 '15 at 23:18
• It must be stressed that this explanation only works because the first number $k$ is chosen uniformly at random. If not, then the conditional probability described in this answer must be weighted by the probability of observing the first outcome. – heropup Feb 19 '15 at 23:24
• @heropup Well, that would be a problem if $g(x)$ were not chosen uniformly at random. For $f(x)$ non-uniform but $g(x)$ uniform, the same reasoning goes through just fine. – Strants Feb 20 '15 at 1:21
• The assumption of independence should be stated explicitly. – r.e.s. Feb 20 '15 at 6:10

Assuming the selections are independent and uniform, there are $100 \times 200$ possible equiprobable pairs of which $100$ can be a match, so the probability is ${100 \over 200 \cdot 100 }$.