3
$\begingroup$

This is a discrete problem concerning integers.

If there are $n$ independent random variables $X_1,...,X_n$ that each take on a value from $\{1,...,x\}$ uniformly at random ($x$ distinct values), what is the probability that the minimum (call it $l$) is unique? The following are approaches I've taken:

Lower Bound:
Treat the problem as a birthday paradox problem. This is a lower bound because the birthday paradox tells us the probability that no pair share the same birthday. We only care if anyone shares a birthday with the earliest birthday (whatever the earliest might be)...

Upper Bound:
Sort the values in ascending order and select the first entry ($l$). Note: there may be ties. All $n-1$ remaining values shouldn't match $l$ if it's a unique lowest. This is trivial if we ignore the fact that selecting the lowest value $l$ gave us information about the remaining values (namely, they are "squished" into the range $\{l,...,x\}$)

$$ p=n(\frac{x-1}{x})^{(n-1)} $$

...But we can't actually ignore that fact so this is an upper bound.

Exact?
The upper bound calculation nudged me into the direction of the exact solution but I can't simplify it past:

$$ \frac{n}{x}\sum_{j=1}^{x}(\frac{x-j}{x-j+1})^{(n-1)} $$

Too be clear, here is what each variable means:
x = number of discrete values that each RV might take on
j = the assumed value of the minimum for that iteration
n = the number of variables

I got to this form by starting with the law of total probability for a unique minimum given that minimum is $j$. The probability that the minimum is $j$ is a constant with respect to $j$ and can be pulled out. The probability that there is a unique minimum given that the minimum is $j$ is what's left inside the summation. I very well may have made a mistake somewhere.

Example:
x = 10. Values drawn from $\{1,...,10\}$
n = 4. Values: $[3, 5, 3, 10]$ (no distinct minimum)

$\endgroup$
  • 1
    $\begingroup$ Just to double check I'm understanding your notation, when you write $[1,x]$, then $x$ is (presumably) a positive integer and this refers to the set of values $\{1,2,\ldots,x\}$? $\endgroup$ – cardinal Apr 18 '12 at 10:37
  • $\begingroup$ Notation $[1,x]$ usually means set of real numbers $y$ satisfying $1\le y\le x$. In that case if the probability density function is continuous, the probability of unique minimum is 1, i.e. the minimum will always be unique. This is just to illustrate the importance of comment by @cardinal. $\endgroup$ – mpiktas Apr 18 '12 at 11:16
  • $\begingroup$ @mpiktas Just to nitpick a little, for jointly continuous random variables, the probability that the minimum is unique is $1$, but this does not mean that the minimum will always be unique. $\endgroup$ – Dilip Sarwate Apr 18 '12 at 11:27
  • $\begingroup$ I also seems like the uniform distribution is being assumed, but a more general solution for all distributions on ${1,...,x}$ is possible. $\endgroup$ – Daniel Johnson Apr 18 '12 at 11:38
  • $\begingroup$ colithium, I think your "upper bound" is missing something. Maybe you meant to multiple by $n$ in order to account for which of the $n$ items was the lowest? (Check you bound, e.g., for the case $n = 3$.) $\endgroup$ – cardinal Apr 18 '12 at 12:59
4
$\begingroup$

Let's call our random variables $X_1$, ... $X_n$. I assume that you meant that they are integer valued, also look at the comments to your original question. Let's look at the case that there is a unique minimum which is $j$ and is assumed by $X_i$ (and only $X_i$). The probability for this case is

$$p(X_i = j) \prod_{k \neq i} p(X_k > j) = (\frac{1}{x})(\frac{x-j}{x})^{n-1}.$$

Multiply by $n$ since every random variable could be the one which assumes the unique minimum $j$. Then sum over $j$ arriving at:

$$\sum_{j=1}^x {n\left(\frac{1}{x}\right)\left(\frac{x-j}{x}\right)^{n-1}} = \frac{n}{x^n} \sum_{j=1}^x {(x-j)^{n-1}} = \frac{n}{x^n} \sum_{j=0}^{x-1} {j^{n-1}}.$$

This would be my solution, I hope it is correct. I might easily have made a mistake. A solution to finding the final sum is given here:

http://mathworld.wolfram.com/PowerSum.html

It involves the Zeta-function.

$\endgroup$
  • $\begingroup$ (+1) Note that the right hand side of your last expression can be written $\frac{n}{x^n} \sum_{j=1}^{x-1} j^{n-1}$ from which it is clear that the probability in question has lower bound $(1-1/x)^n$. $\endgroup$ – cardinal Apr 18 '12 at 13:01
  • $\begingroup$ @Erik It looks like our formulas are similar. Our loops are off by 1 but I think our formulas both turn out to be the same thing. The difference is: I calculate the probability that each n-1 remaining entries don't match $l$ differently (I do it out of x-j instead of x). I also don't have the multiply by n part. Your formula matches my simulation output but I don't fully understand it. Given you know the minimum is j, wouldn't the range of possible values be reduced to $x-j$? $\endgroup$ – colithium Apr 18 '12 at 21:08
  • 1
    $\begingroup$ Erik's answer is correct, as inspecting some small cases will demonstrate. Colithium, your denominators are too small: they should all equal $x$, not $x-j+1$. E.g., for $x=3,n=2$ Erik gets $2/3$ for the answer. You compute $(2/3)((2/3)^1 + (1/2)^1)$=$7/9$ but only $6$ of the $9$ equiprobable outcomes $11, 12, 13, 21, 22, 23, 31, 32, 33$ have a unique minimum. $\endgroup$ – whuber Apr 18 '12 at 22:00
2
$\begingroup$

I agree with Erik's answer in the case of a uniform distribution. Here I will assume a general distribution $P(X_i = j) \doteq p_j$ for all $j = 1,...,x$ (obviously $1 = \sum_{j=1}^xp_j$).

$$P(\text{there is a unique minimum}) = \sum_{k=1}^nP(X_k\text{ is the unique minimum})$$ $$ = nP(X_1\text{ is the unique minimum})$$ $$ = n\sum_{j=1}^xP(X_1 = j,X_1\text{ is the unique minimum})$$ $$ = n\sum_{j=1}^xP(X_1\text{ is the unique minimum}|X_1 = j)P(X_1 = j)$$ $$ = n\sum_{j=1}^xP(X_2 > j,...,X_n>j)p_j$$ $$ = n\sum_{j=1}^x[\sum_{i=j+1}^xp_i]^{n-1}p_j$$

From here, you can plug in $p_j = \frac{1}{x}$ for all $j$ and recover Erik's answer.

For another common example, let us assume that $X_j$ comes from a binomial distribution generated by $x$ Bernoulli trials each with probability $q$ of success. Here we allow for $X_k = 0$ which just means that our outermost sum above will start from zero rather than one and $P(X_jk = 0) = p_0$. In other words $X_k \sim Bern(x,q)$ with $p_j = \binom{x}{j}q^j(1-q)^{x-j}$.

$\endgroup$
  • $\begingroup$ (+1) But, I think there are some typos in your last paragraph. Also, you can skip right over the line invoking conditional probability with no loss whatsoever. :) $\endgroup$ – cardinal Apr 18 '12 at 13:02

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.