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$
12
  • 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, 2012 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, 2012 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$ Apr 18, 2012 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$ Apr 18, 2012 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, 2012 at 12:59

2 Answers 2

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$
3
  • $\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, 2012 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, 2012 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, 2012 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$
1
  • $\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, 2012 at 13:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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