2
$\begingroup$

I read it on some website (which I do not remember now) that in a sequence of length $n$, to find the maximum value (with high probability) one only needs to generate a constant multiple of $\log(n)$ random numbers from the sequence. I could not find any reference for this.

My question: Is this true? If so, what is the exact statement in terms of the probability bound? If not $\log n$ number of samples, is there any randomized algorithm that requires far less than $n$ samples and outputs a number provably larger than the maximum with a specified probability.

I was able to prove the following (which is simple): suppose the sequence is $x_1, \ldots, x_N$. Let $x_{(\beta N)}$ denote the $\beta N$-th largest value of the sequence. Let $X_1, \ldots, X_n$ denote iid uniform random variables uniform on the sequence. Then for any $\beta\in(0, 1)$ and $n\ge 1$,

$\mathbb{P}(X_{(n)} > x_{(\beta N)}) = 1 - \beta^n.$

For this probability to be say $0.99$, we need $n \ge \log(100)/\log(1/\beta)$. If $\beta = 1 - k/N$ for some $k$ then $\beta N = N - k$ and so, $x_{(\beta N)}$ represents the $(N - k)$-th largest value and for this case $n \ge N\log(100)/k$. This implies that the number of random samples required is of the order $N$.

Improve this question
$\endgroup$
2
  • $\begingroup$ I'm not clear about the question. Are you looking for a generalization of the result you proved to the case where $\{X_i\}$ are not identically distributed (but presumably still independent)? $\endgroup$ Commented Feb 9, 2019 at 19:45
  • 2
    $\begingroup$ If you can only look at individual elements, you can't find the max element with high prob using less than $\Theta(n)$ looks. Because: the max element might be anywhere. Three other things you might be recalling: (1) the maximum of a unimodal sequence can be found in $O(\log n)$ looks, (2) a local maximum (number not smaller than the number on either side) can be found in $O(\log n)$ looks, (3) Carlo's answer, which uses all the elements but performs $O(\log^2 n)$ tests which are to evaluate a multivariable polynomial with arguments from the sequence and compare it to 0. $\endgroup$ Commented Feb 10, 2019 at 1:05

1 Answer 1

Reset to default
6
$\begingroup$

A Randomized Algorithm for Finding Maximum with $O(\log^2 n)$ Polynomial Tests, H.F. Ting and A.C. Yao (1994)

Improve this answer
$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.