In a testing, ranking, or selection scenario, we have samples of size n where a measurement is correlated 0<r<1 with some second variable of interest; they are bivariate normally distributed. We'd like to select the maximum. If we pick the maximum on the first variable, we have a better chance of picking the maximum on the second variable as well, but of course, with less than 100% probability. What exactly is the probability of selecting the true maximum for a given n and r?

This can be easily simulated (R):

max1IsMax2 <- function(n,r) { mean(replicate(100000, {
                sample <- mvrnorm(n, mu=c(0,0), Sigma=matrix(c(1, r, r, 1), nrow=2))
                })) }

sapply(2:10, function(n) { max1IsMax2(n, r) })
# [1] 0.66925 0.53466 0.46197 0.41044 0.37627 0.34344 0.32760 0.30732 0.29484

But I have failed to figure out any way to calculate it exactly.

I spent a few hours trying to read through the order statistics literature, without little success (most of the discussions of bivariate or multivariate order statistics don't seem to be considering a scenario like this, or I completely failed to understand them) and also following one idea I had: given the expectation on the first variable (the expected maximum of n), the expected second variable is regressed to the mean by r, eg

exactMax <- function(n, mean=0, sd=1) { expect.max.ostat(n, para=vec2par(c(mean, sd), type="nor"), cdf=cdfnor, pdf=pdfnor) }
# [1] 1.53875273
exactMax(10) * r
# [1] 0.769376365

The winner on the test is +1.53SD, but regress to the mean down to +0.76SD on the true latent variable. For it to be the maximum on the second variable as well, that is another way of saying that all the other 9 datapoints in the sample must all be smaller than it. Each datapoint has a certain p of being greater than +0.76SD, so the probability of p failing 9 times is then simply $(1-p)^9$. So to estimate the repeat probability, you'd simply take the expected maximum of n, deflate by r, calculate the CDF for that, and raise it to n-1. p is easily estimated by simulation or exactly for the normal distribution:

1 - mean(rnorm(1000000) > (exactMax(10) * r))
# [1] 0.77932
pnorm(exactMax(10) * r)
# [1] 0.779165043

Except... $0.779^9=0.10$, which is way off from 0.29, and this is true of all the other values I've tried. I wondered if I was specifying the SDs wrong for the second variable, but looking at the simulation, it is indeed $N(0,1)$ as it should be, the maximum on variable 1 does indeed regress by r in variable 2, and I can't find any formula which gives max-probabilities consistent with the simulation estimates even fiddling around with the SDs.

So what am I doing wrong here and what is the right answer? And are there any generalizations discussing how much slippage there is for given n and r?

  • $\begingroup$ Is it correct if i rewrite your problem as follows? Given a sample of size $n$ from a $Normal(\mu,\Sigma)$ with known parameters. Let's call each sample $S_i$ and let's write $S_i = (X_i, Y_i)$. We want to find the probability that $P(X_i \ge X_j | Y_i \ge Y_j)$ for all $j$. $\endgroup$ – Nicola Mingotti Sep 15 '19 at 8:01
  • $\begingroup$ I think you could generalize it to ask about each order statistic, not just the max/min, yes. I am primarily interested in the maximum because most real-world problems take the form of either selecting a threshold (which I already have exact solutions for), or the single biggest (max); relatively few natural problems would be 'select the fifth', eg, and I'd rather not bite off more than I can chew. :) $\endgroup$ – gwern Sep 15 '19 at 13:59
  • $\begingroup$ Some progress: apparently for n = 2, it's $\frac{1}{2} + \frac{1}{\pi}\arcsin(r)$. And Sibuya 1960 proves that asymptotically in n when r < 1, the two distributions are independent (ie the probability of the max in one being the max in the other just approaches 1 / n - so the correlation is basically a constant factor gain). And Dos Anjos et al 2005 might help but I can't understand it. $\endgroup$ – gwern Dec 24 '19 at 15:45
  • $\begingroup$ Finally, The Asymptotic Theory of Extreme Order Statistics, Galambos 1987 might, from some references, cover exact formulas or approximations good for small n, at least, but I can't find any digital copies or books for sale to scan, so I've set up an alert on Abebooks in case any copies surface. $\endgroup$ – gwern Dec 24 '19 at 15:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.