1
$\begingroup$

In a computer program I am writing, I have several independent variables, each of which is uniformly distributed between two real values. I seek the probability of each variable being the maximum of the group.

That is, let $X_1, X_2, X_3,\ldots, X_n$ be my random variables. I seek a probability function $P$ such that $P(X_m)$ is the probability that $X_m = \max\{X_1, X_2, X_3,\ldots, X_n\}$. How would I find such a function given the ranges of each random variable? I don't need the actual maximum value - rather, I only need the probabilities that each variable produces that maximum value.

Since this is for a computer program, I would like to have a solution which can be easily algebraically calculated for an arbitrary number of variables, each with arbitrary ranges. However, if this is not feasible, I would naturally accept a calculus based program.

$\endgroup$
  • $\begingroup$ For n=2 you can have this approach, perhaps extensible. Scale the range with higher upper bound to $1$, let the other range be $a$ with overlap $x$. The probability of the first rv is greater than the second can be written as $1-x + \frac{x^2}{2a}$ $\endgroup$ – karakfa Mar 25 '13 at 21:04
2
$\begingroup$

As I understand it, the interval of each $X_i$ is a parameter of your algorithm.

Let $X_1,X_2...,X_n$ be the random variables that survived step 1. Let $F_1,F_2...,F_n$ be their cdf(cumulative distribution function) and let $f_1,f_2...,f_n$ be their pdf(probability density function). Let $[r_i,\:s_i]$ be the interval of $X_i$. Let $r_k$ be the biggest of all $r_i$.

I suggest a reduction phase. Remove all random variables $X_i$ that have $s_i<r_k$. Those cannot be the maximum.

After this step of reducing the problem to a subset of the random variables, we can start looking at the probability aspect of this.

Now the probability that the following holds $X_m = \max\{X_1, X_2, X_3,\ldots, X_n\}$ amounts to:

$$\int_{r_k}^{s_m}\: f_m(x)\prod_{i=1,i\neq m}^n F_i(x) \; dx$$

$$=\frac{1}{s_m-r_m}\int_{r_k}^{s_m}\: \prod_{i=1,i\neq m}^n F_i(x) \; dx$$

For uniform distributed random variables we know their cdf, namely:

$$F_i(x)=\left\{ \begin{array}{ll} 0 & x<r_i \\ \frac{x-r_i}{s_i-r_i} & r_i \leq x < s_i \\ 1 & x \geq s_i \end{array} \right.$$

Or equivalently: $$F_i(x)=\left\{ \begin{array}{ll} 0 & x<r_i \\ \frac{1}{s_i-r_i}(\min(x,s_i)-r_i) & r_i \leq x \end{array} \right.$$

Using the fact that we choose $r_k$ to be the biggest of all lower bounds of the intervals, we only have case 2 for our cdf. This is the equation you get :

$$\prod_{i=1}^n{\frac{1}{s_i-r_i}}\int_{r_k}^{s_m}\: \prod_{i=1,i\neq m}^n (\min(x,s_i)-r_i) \; dx$$

Now some the knowledge of the interval can be used. Let the upper bounds of the intervals $s_i$ be increasing or equal if $i$ increases, this can always be done by changing the index of each random variable. Now cutting the integration area in parts we get:

$$\int_{r_k}^{s_m}\: \prod_{i=1,i\neq m}^n (\min(x,s_i)-r_i) \; dx=$$ $$\int_{r_k}^{s_1}\: \prod_{i=1,i\neq m}^n (x-r_i) \; dx + \sum_{j=1}^{m-1}\int_{s_j}^{s_{j+1}}\: \prod_{i=j+1,i\neq m}^n (x-r_i) \; dx=$$

Now you have all integrals of polynomials of degree at most n, this can be computed.

I reckon this won't have a lovely runtime in the number of variables left after the reduction, because a random variable makes the degree of all polynomials one higher in the worst case.

I hope this helps.

$\endgroup$

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.