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

Question

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?

Answer 1

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.)