Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have a collections of "systems" that I want to test their performance, $1,\ldots,k$.

I have a small set of samples, for which I can test whether each condition does better or not than the other, so I can get a binary result $I(i,j)$ for each $1 \le i,j \le k$ that tests whether $i$ or $j$ do better on this small sample.

This $I(i,j)$ is calculated by the following way: each $i$ is associated with a "system", like I said. We have a collection of samples $X_1,...,X_n$, and we measure $C(i) = 1/n \sum_{l=1}^n l(X_l,i)$ where $l(X_l,i)$ is a measure of how well system $i$ does on sample $l$. Then we just measure whether $C(i) > C(j)$ or vice versa (to get $I(i,j)$).

Can I pick from these collections of binary indicators the system which is mostly likely to do best on the expected value of the whole distribution? Are there any ways to have theoretical guarantees for that, and do they depend on $k$?

By "do best on the expected value" I am referring to $D(i) = \mathbb{E}[l(X),i]$ - this should be highest for the system I pick.

share|cite|improve this question

Under the described conditions, I(i,j) will describe the order over systems induced by your empirical (average) measurement. This is good - the strategy is obvious, choose the top system. Analysis is more delicate. You need to know something about the dispersion of excepted values for the systems vs the concentration of a single measurement of a single system, and then use Hoeffding or Bernstein inequality to bound the probability that the some system is actually better than the chosen system, despite the empirical evidence. Of course if all systems are almost equal and measurements are very noisy, only very high values of n will do. The effect of k on reliability depends on the distribution from which systems are chosen, which you didn't mention. Highly dispersed systems lead to higher reliability with higher k. Bounded distribution for systems lead to decreasing reliability with higher k (many very systems are very similar to the top rated, one will be better).

share|cite|improve this answer

Your Answer


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.