1
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ Is there a way to formulate this question without us needing to read the four pages leading up to your question? $\endgroup$ Dec 22 '17 at 12:46
  • $\begingroup$ @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. $\endgroup$
    – Belgi
    Dec 25 '17 at 20:41
1
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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$ $\endgroup$
    – Belgi
    Dec 25 '17 at 21:18
  • $\begingroup$ by the way, is this fact so common that the author didn't bother to explain it ? I didn't manage figure it out on myself $\endgroup$
    – Belgi
    Dec 25 '17 at 21:19
  • $\begingroup$ It's similar to summation by parts. It's not too hard to derive yourself – first consider the case in which all elements are distinct, and then generalize. $\endgroup$ Dec 25 '17 at 21:47

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.