# A $log(k)$ algorithm for the matroid secretary problem

I'm reading the following article that presents a $log(k)$ algorithm for your secretary problem.

I'm in the analysis section at the left part of page 5 there is the following claim:

$B^*$ is a set with elements $x_1,...,x_k$ with respective values $v_1,...,v_k$ where $v_1\geq...\geq v_k$. Denote $n_i(B^*)$ as the number of elements in $B^*$ with value at least $v_i$. Then the sum of the $q$ largest elements is $[\sum_{i=1}^{q-1}(v_{i+1}-v_{i})n_{i}(B^{*})]+v_{q}n_{q}(B^{*})$

I fail to see how the sum presented is the sum of the largest $q$ elements. From what I understand $n_{i}(B^{*})=i$ since the elements with value at least $v_{i}$ are $v_{1},...,v_{i}$.

If I open the sum than all the inner element ($v_{2},...,v_{q-1}$) has a coefficient of $1$, but the coefficient of $v_{1}$ is $-1$ and the coefficient of $v_{q}$ is $2q$.

Can someone help me understand this equality?

• Is there a way to formulate this question without us needing to read the four pages leading up to your question? Dec 22, 2017 at 12:46
• @YuvalFilmus - I thought that many would be familiar with the setting and the article, I added the information needed to make the question self contained. thanks for the comment. Dec 25, 2017 at 20:41

It seems that there is a typo – $v_{i+1} - v_i$ should be $v_i - v_{i+1}$.
Suppose first that all elements are distinct. Then (using the convention $v_0 = 0$) $$\sum_{i=1}^{q-1} (v_i-v_{i+1}) n_i(B^*) + v_q n_q(B^*) = \\ \sum_{i=1}^{q-1} i (v_i-v_{i+1}) + q v_q = \\ \sum_{i=1}^q i v_i - \sum_{i=2}^q (i-1) v_i = \sum_{i=1}^q v_i.$$
Consider now the general case, in which we have $$v_1 = \cdots = v_{j_1} > v_{j_1+1} = \cdots = v_{j_2} > \cdots,$$ where $j_r = q$. Then for $j_0 = 0$, $j_{r+1} = j_r+1$, and $v_{q+1} = 0$, we have $$\sum_{i=1}^{q-1} (v_i - v_{i+1}) n_i(B^*) + v_q n_q(B^*) = \\ \sum_{\ell=1}^{r+1} \sum_{t=0}^{j_\ell-1} (v_{j_{\ell-1}+t} - v_{j_{\ell-1}+t+1}) n_{j_{\ell-1}+t}(B^*) = \\ \sum_{\ell=1}^{r+1} (v_{j_{\ell-1}} - v_{j_{\ell-1}+1}) (j_1 + \cdots + j_{\ell-1}) = \\ \sum_{\ell=1}^r v_{j_\ell} j_\ell = \sum_{i=1}^q v_i.$$ (This calculation might not be 100% correct, but you get the idea.)
• Thanks! So in general, even if I have a different set, say $W$ with values $w_i$ then with the same notation, the above equality holds? I get this from the general case where we don't know in advance how many elements are greater or equal to some $v_i$ Dec 25, 2017 at 21:18