Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I have several positive random variables $x_i,\ i=1,...,N$ taken from different unknown distributions (these distributions can be closely approximated by log-normal if needed). I can sample these variables as many times as needed; all variables are sampled simultaneously.

From each sample my software selects the minimal variable $x_j$ and outputs its index $j$.

The problem is: all values of output index $1 \leq j \leq N$ should have equal probabalities. So, random variables should be somehow adjusted to be "equal" for the minumum operation.

I decided to multiply each random variable by some constant $k_i$. First idea was that $k_i=1/E[x_i]$, so that all adjusted variables will have equal expected values. The output indices indeed became much more uniform, but I pretty sure that my solution is wrong.

The software should also dynamically adapt to gradually changing distributions of random variables (noise shape of sensors depend on temperature).

Do you have any advice?

share|improve this question

2 Answers 2

up vote 4 down vote accepted

Such simple adjustment is not possible. First, take the logarithm: consider new random variables $y_i=\log x_i$. Their ordering is the same, but correction is now additive rather than multiplicative: you change $y_i$ to $y_i+c_i$ where $c_i=\log k_i$.

Assume that the distribution of each $y_i$ is normal. The natural choice is $c_i=-E(y_i)$, so that the adjusted distributions are centered at 0. By symmetry of the distributions, having the same mean is equivalent to the property that, for each pair $i,j$, the probability that $y_i+c_i\ge y_j+c_j$ equals 1/2. So setting $c_i=-E(y_i)$ is the only way to go if you want the uniformity of the minimum index for every subset of the variables.

But this does not always work. For example, consider $N=3$ and assume that $y_1$ is concentrated near 0 (i.e. has very small dispersion) and $y_2$ and $y_3$ have identical distributions with very large dispersion. Then the events $y_2\ge y_1$ and $y_3\ge y_1$ are almost independent, so the probability that $\min\{y_i\}=y_1$ is approximately 1/4, not 1/3 as desired.

For topological reasons, for every collection of distributions there exist adjustment constants such that the minimum index is distributed uniformly. But, as shown above, they depend in a strange way on the entire collection (i.e. you would need to recompute them if you remove one of the variables). And they are probably hard to compute.

It is better to adjust $y_i$ both additively and multiplicatively so as to make all normal distributions identical. In terms of the original variables, you transform them by $x_i\mapsto k_ix_i^{p_i}$ where $k_i$ and $p_i$ are computed from $E$ and $\sigma $ of $\log x_i$.

share|improve this answer
    
That completely solves my problem. Thank you! –  Anton Sukhinov Feb 25 '12 at 6:15

I assume your random variables are independent.

If $F_i(x)$ is the cumulative distribution function and $f_i(x)$ the probability density function of $x_i$, then you want to solve the equations

$$ \int_0^\infty k_i f_i(k_i t) \prod_{j \ne i} (1 - F_j(k_j t))\ dt = 1/N, \ i = 1 \ldots N$$

Actually only $N-1$ of these equations are needed, as the sum of the probabilities is always $1$. You'll also want to use some normalization condition on the $k_i$'s, perhaps $k_1 = 1$. It's unlikely that the integrals can be done in closed form, so you're pretty much forced to use numerical methods both for evaluating the integrals and solving the equations.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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