Let $k, n \in \mathbb{N}$, with $k \leq n$. Let $A = (a_1, a_2, ..., a_n)$ be an unordered finite sequence of real numbers. Let $(B_1, B_2, ..., B_k)$ be an unordered sequence of random variables such that each $B_i$ is sampled uniformly from $A$, without replacement. Let the random variable $X = max(B_1, B_2, ..., B_k)$.

What is the distribution $p(X)$? What is the expected value $\mathbb{E}[X]$. (The former would go a long way to compute the latter.)

This is very similar to Distribution of max of samples with replacement, except here the collection in question possibly has duplicate values and the sampling is without replacement.

In the context of recommendation systems, $a_i$ is the relevancy or score of some document or item $d_i$. A system may be allowed to recommend $k$ of the $n$ documents (an internet search engine may recommend 10 pages out of billions). $\mathbb{E}[X]$ is the expected relevancy or score of the naive recommendation system which chooses $k$ documents uniformly at random and without replacement.

This seems related to the Urn Problem, the Multivariate Hypergeometric Distribution, and this paper; but here, the balls have a number instead of a color and we are interested in value of the balls instead of counts.

(Any corrections to the concepts, terminology, or even notation/syntax are welcome.)


Here is a Python solution to compute the expected value, created by NabiNaga. By sorting the values in $A$, we can compute the cumulative distribution of $X$. The probability of $X$ is then the cumulative probability of a particular value from sorted $A$ minus the cumulative probability of the value that comes before it. The probability that $X$ assumes one of the $k-1$ smallest values is $0$, unless there are duplicates. The brute_force method verifies that this handles duplicate values in $A$.

from functools import reduce
from itertools import combinations
import operator as op

def ncr(n, r):
    # from https://stackoverflow.com/questions/4941753/is-there-a-math-ncr-function-in-python
    r = min(r, n - r)
    numer = reduce(op.mul, range(n, n - r, -1), 1)
    denom = reduce(op.mul, range(1, r + 1), 1)
    return numer / denom

def brute_force(A, k):
    total = 0
    count = 0
    for combination in combinations(A, k):
        total += max(combination)
        count += 1
    return total / count

def solve(A, k):
    assert k <= len(A)
    A = sorted(A)

    total = 0
    last_num_combs = 0
    for i in range(k, len(A) + 1):
        num_combs = ncr(i, k)
        X = A[i - 1]
        total += X * (num_combs - last_num_combs)
        last_num_combs = num_combs

    return total / last_num_combs

if __name__ == "__main__":
    A = [1, 3, 7, 10, 15, 20, 20, 100, 100, 112, 150]
    k = 5

    assert brute_force(A, k) == solve(A, k)
    print(solve(A, k))

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.