# Expected Value of Naive Recommender System

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

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