Optimal $k$-Secretary with Logarithmic Memory

Throughout the paper, $s=(s_1,s_2,\mathrm{\dots },s_n)$ denotes a random-order sequence, and we shorthand $s_{i_1:i_2}$ for the subsequence $(s_{i_1},s_{i_1+1},\mathrm{\dots },s_{i_2})$. When it is clear from the context, we sometimes abuse the notation and let $s_{i_1:i_2}$ denote the set formed by the elements in the subsequence. For instance, $s_{i_1:i_2}\cap (-\mathrm{\infty },a)$ is used as a shorthand for .

We will frequently use the rank of an element $x$ within a contiguous subsequence, when only the elements that are strictly smaller than a threshold $x^{\prime }$ are counted.

We formally define the $k$-secretary problem as follows.

The assumption that all the elements are distinct is for the simplicity of the exposition. It comes without loss of generality by a standard tie-breaking argument.²²2For example, we may augment each element with a random identifier with $\mathrm{\Theta }(\log n)$ bits. This ensures distinctness with high probability, and only requires one additional word for storing each element.

We say that a $k$-secretary algorithm is competitive, if it is guaranteed to secure a certain fraction of the maximum possible outcome, namely, the sum of the $k$ largest elements.

Next, we formally define quantile estimation in a random-order stream.

Again, the assumption that the $n$ elements are distinct is for simplifying the notations. The results for distinct elements can be extended to the general case via tie-breaking and a more careful definition of the error.

We informally introduce the model of computation and the memory usage of an algorithm. All our algorithms can be implemented in the word RAM model, assuming that each word can store either an integer of magnitude $poly(n)$ or an element in the stream (in either $k$-secretary or quantile estimation). In particular, when all stream elements are bounded by $poly(n)$, a word size of $\mathrm{\Theta }(\log n)$ is sufficient. Moreover, all our algorithms are comparison-based: they only access the stream elements via pairwise comparisons, and do not perform any arithmetic operations on the elements. Therefore, a word size of $\mathrm{\Theta }(\log n)$ would suffice if: (1) every stream element is presented as a unique identifier (which takes $O(\log n)$ bits); (2) the algorithm has access to an oracle that compares two elements specified by their identifiers.

Towards proving Theorem 5, we show that a quantile estimation algorithm leads to a competitive $k$-secretary algorithm with almost the same memory usage. Formally, the reduction applies to all comparison-based quantile estimators. Roughly speaking, an algorithm is comparison-based if it only accesses the elements in the stream via pairwise comparisons. As a result, the output of a comparison-based algorithm is invariant (up to the renaming of elements) under any order-preserving (i.e., monotone) transformations. See Definition 9 for a more formal definition.

The proposition follows from a reduction that is essentially implicit in [27] – Kleinberg’s algorithm can be viewed as a special case in which the quantile estimator is exactly correct (and thus, we can take $\alpha =1/2$). Our proof of Proposition 6 shows that this reduction is actually robust to the inaccuracy in the quantile estimator, so the error bound in quantile estimation can be smoothly translated to the sub-optimality in $k$-secretary.

As we explain in Section 2.4, directly following the reduction of [27] would increase the memory usage by a factor of $\log k$. We avoid this multiplicative increase by carefully modifying the reduction, so that the $k$-secretary algorithm would run $\log k$ copies of the quantile estimator sequentially, rather than in parallel.

In light of Proposition 6, the only missing piece towards proving Theorem 5 is a memory-efficient quantile estimator with $O(\sqrt{k})$ error.

We note that both the memory usage and the error bound are independent of $n$. This is because we address the expected error directly, rather than conditioning on a good event involving the entire length-$n$ stream, thus avoiding a potential $polylog(n)$ dependence.

The key idea behind the algorithm for Theorem 7 is to reduce the problem of finding the $k$-th largest element to finding the $k^{\prime }$-th largest in a subsequence, for some $k^{\prime }\ll k$. By shrinking the value of $k$ fast enough, we ensure that the error incurred in the subproblems can be controlled. In Sections 2.1 and 2.2, we sketch the algorithm and its analysis in more detail.

Our second algorithm finds the $k$-th largest element exactly with high probability, albeit with a looser memory bound of $O(\sqrt{k})$.

In particular, setting $m=O(\sqrt{k\log (1/\delta )}+\log (1/\delta ))$ is sufficient for succeeding with probability $\ge 1-\delta$.

Theorem 8 follows from the technique of [35]: the algorithm maintains $m$ consecutive elements among the stream that has been observed so far, in the hope that the $k$-th largest element is among these $m$ elements at the end. [35] showed that this strategy finds the median of a length-$n$ random-order stream (i.e., the $k=n/2$ case) using $O(\sqrt{n})$ memory, and proved a matching $\mathrm{\Omega }(\sqrt{n})$ lower bound. Our result extends the result of [35] to general $k$. In Section 2.3, we introduce the technique of [35] in more detail, and sketch our strategy for handling biased quantiles (i.e., the $k\ll n$ case).

The classical secretary problem is often attributed to [15], though the exact origin of the problem is obscure [18, 17]; different versions of the problem were studied in the contemporary work of [30, 13, 21].

The natural extension of selecting up to $k$ elements (i.e., the $k$-secretary problem) was studied by [21, 3, 27, 5] under various objectives (e.g., the probability of selecting the $k$ largest elements exactly, or the largest element being among the chosen ones). We followed the formulation of [27] in terms of the competitive ratio. [27] showed that the optimal competitive ratio is $1-\mathrm{\Theta }(1/\sqrt{k})$ as $k\to \mathrm{\infty }$. [5] subsequently gave $1/e$-competitive algorithms for all $k\ge 1$, improving the result of [27] in the small-$k$ regime. A more recent work of [4] also focused on the non-asymptotic regime, and gave a deterministic algorithm with a competitive ratio $>1/e$ for all $k\ge 2$.

A further extension of the $k$-secretary problem considers selecting multiple elements subject to a more general combinatorial constraint. [5] studied the knapsack secretary problem. [7, 6] introduced the matroid secretary problem, in which the player is asked to select elements that form an independent set of a given matroid. This problem has been extensively studied [12, 42, 25, 14, 29, 16, 24, 43, 1], and it remains a long-standing open problem whether an $O(1)$-competitive algorithm exists in general. Other variants of the secretary problem consider alternative models for how the player accesses the elements and makes decisions, including models of interview costs [8], shortlists [2], reservation costs [11], and a “pen testing” variant [39, 19].

For the quantile estimation problem in random-order streams, [35] gave an exact selection algorithm for the $k=\lfloor n/2\rfloor$ case (i.e., finding the median) with $O(\sqrt{n})$ memory, and proved a matching $\mathrm{\Omega }(\sqrt{n})$ memory lower bound. Our Theorem 8 generalizes their result to general values of $k$, and their lower bound implies that the $O(\sqrt{k})$ memory usage cannot be improved in general (specifically, in the $n=2k$ case).

For approximate selection, [22] proposed an algorithm that uses $O(1)$ words of memory and finds the $k$-th largest element up to an error of $O(\sqrt{k}{\log }^{2}n\cdot \log (1/\delta ))$ with probability $1-\delta$. In comparison, Theorem 7 bounds the expected error and avoids the extra $polylog(n)$ factor, both of which are crucial for the optimality of the resulting $k$-secretary algorithm. A subsequent work of [34] solved median estimation with an $n^{1/3+o(1)}$ error using $O(1)$ words of memory. In comparison, Theorem 7 applies to all values of $k$ and makes the error dependent only on $k$ and not $n$, at the cost of a larger exponent of $1/2$ and a logarithmic memory usage. We note that, even if we could improve the error to $O(k^{1/3})$, the reduction from $k$-secretary still introduces an $\mathrm{\Omega }(\sqrt{k})$ error, which would dominate the quantile estimation error.

While we focus on the random-order setup of quantile estimation, many prior work also addressed the more challenging setup in which elements arrive in an arbitrary order [35, 31, 26, 33, 23]. The multi-pass setting, in which the algorithm may scan the stream multiple times, was also considered [35, 22].

More broadly, our work is part of the endeavor to understand the role of memory in learning, prediction, and decision-making. Prior work along this line studied the memory bounds for parity learning in a streaming setting [46, 45, 28, 40, 20], for the experts problem in online learning [44, 38, 37], as well as the fundamental problem of linear regression [41, 32, 10, 9].

How should we solve quantile estimation for a specific value of $k$, if we already have an algorithm (denoted by ${𝒜}_{k/2}$) that solves the $k^{\prime }=k/2$ case with an $O(\sqrt{k^{\prime }})=O(\sqrt{k})$ error? The answer is simple: we run ${𝒜}_{k/2}$ on the first $n/2$ elements of the sequence and return its answer. Assuming that the output of ${𝒜}_{k/2}$, denoted by $x^{\ast }$, is exactly the $(k/2)$-th largest element among $s_{1:(n/2)}$, a simple concentration argument would show that the rank of $x^{\ast }$ among $s_{1:n}$ is roughly $k\pm O(\sqrt{k})$. Now, let $l≔{\mathrm{Rank}}_{1:(n/2)}(x^{\ast })$ denote the actual rank of $x^{\ast }$ among the first half of the sequence. Our assumption on ${𝒜}_{k/2}$ implies that $l\approx k/2\pm O(\sqrt{k})$, which further gives

At first glance, the above seems to suggest an extremely simple solution to quantile estimation: we repeatedly apply the reduction above, and reduce the value of “$k$” to $k/2,k/4,\mathrm{\dots },1$. For the base case that “$k$” equals $1$, we can find the largest element exactly using $O(1)$ memory. However, this approach is equivalent to outputting the largest one among the first $\approx n/k$ elements, and its error can be easily shown to be $\mathrm{\Omega }(k)$. What goes wrong here? The issue is that we ignored the blow-up in the error during the reduction. Define random variables $X_1,X_2,X_4,\mathrm{\dots },X_{k/2},X_k$ such that $X_{k^{\prime }}$ denotes the error in the rank when we solve the instance with $k=k^{\prime }$. Our discussion from the last paragraph shows that, for some universal constant $C>0$, $(X_k)$ satisfies the dynamics

Expanding the above gives

since the error incurred at $k^{\prime }=O(1)$ would be doubled roughly ${\log }_{2}k$ times through the iteration $X_k\approx 2X_{k/2}\pm C\sqrt{k}$, resulting in the dominant term of $\mathrm{\Omega }(k)$ in the error.

We would get an $O(\sqrt{k})$ error bound if we could shrink the value of $k$ faster. Imagine that, instead of reducing to an instance with $k^{\prime }=k/2$, we can reduce to an instance with $k^{\prime }=k/100$, while the error still propagates in the same way. Then, the recursion in Equation 1 would be replaced with $X_k\approx 2X_{k/100}+C\sqrt{k}$, which leads to

Therefore, the key is to reduce the scale of the problem (measured by parameter $k$) at a slightly faster pace. Our algorithm does this in a fairly simple way. First, we divide the length-$n$ sequence $s$ into two halves $s_{1:B}$ and $s_{(B+1):n}$ for some $B\approx n/2$. Then, we subsample a random $p$-fraction of the first half, where $p=\mathrm{\Theta }(m/k)$, by drawing $B_1\sim \mathrm{𝖡𝗂𝗇𝗈𝗆𝗂𝖺𝗅}(B,p)$ and taking the first $B_1$ elements. We find the top $m$ elements among $s_{1:B_1}$, denoted by $M[1],M[2],\mathrm{\dots },M[m]$, using $O(m)$ memory (in the straightforward way). After reading the remaining $B-B_1$ elements in $s_{1:B}$, we can compute the rank ${\mathrm{Rank}}_{1:B}(M[i])$ for every $i\in [m]$. Then, we find an index $i^{\ast }$ such that

Let $a^{\prime }≔M[i^{\ast }]$ and $k^{\prime }≔k/2-{\mathrm{Rank}}_{1:B}(a^{\prime })$. We know that the $(k/2)$-th largest element among $s_{1:B}$ is simply the $k^{\prime }$-th largest element among $s_{1:B}\cap (-\mathrm{\infty },a^{\prime })$. Therefore, we recursively find the $k^{\prime }$-th largest element among $s_{(B+1):n}\cap (-\mathrm{\infty },a^{\prime })$, in the hope that it will be a good approximation for the $k$-th largest element overall.

To make this work, we need the parameter $k^{\prime }$ for the recursive call to be smaller than $k$ be a sufficiently large factor. This is indeed the case, since the gaps in the ranks of $M[1],M[2],\mathrm{\dots },M[m]$ among $s_{1:B}$ roughly follow the geometric distribution $\mathrm{𝖦𝖾𝗈}(p)$, so each of them has an expectation of $\le 1/p=O(k/m)$. By setting $m=\mathrm{\Omega }(\log k)$, we can ensure that every gap is smaller than $C_0\cdot k$ (for any small constant $C_0$), with probability $1-1/poly(k)$.

The reduction sketched above actually reduces quantile estimation to a slightly different problem: instead of finding the $k$-th largest element among $s_{1:n}$, we find the $k$-th largest among $s_{1:n}\cap (-\mathrm{\infty },a^{\prime })$. This does not pose a problem as the reduction works for this generalized version as well.

Formally, the recursive algorithm takes parameters $n$, $k$, and $a$ as inputs, and aims to find the $k$-th largest element among $s_{1:n}\cap (-\mathrm{\infty },a)$, where $s_{1:n}$ is the upcoming random-order sequence of length $n$. The quantile estimation instance is invalid if $k>n^{\prime }≔|s_{1:n}\cap (-\mathrm{\infty },a)|$. While the outermost call to the algorithm (where $a=+\mathrm{\infty }$) is always valid, the algorithm might eventually lead to a recursive call in which the parameter $k$ becomes invalid. In this case, our algorithm always returns $-\mathrm{\infty }$ as the answer. Then, in the previous level of recursion – which makes this invalid call – the algorithm translates this $-\mathrm{\infty }$ to the smallest element in the stream.

The second edge case is that we fail to find a good choice of $a^{\prime }$ that significantly reduces the value of $k$. This can, in turn, happen for three different reasons: (1) , in which the first half of the sequence does not have a $(k/2)$-th largest element; (2) the $(k/2)$-th largest element exists, but none of the elements with ranks in $[k/2-C_0\cdot k,k/2]$ get subsampled into $s_{1:B_1}$, so none of them is present in the array $M$; (3) Some element with rank in $[k/2-C_0\cdot k,k/2]$ gets subsampled into $s_{1:B_1}$, but more than $m$ elements with ranks in $[1,k/2]$ get subsampled, so that the one with a rank closest to $k/2$ is not kept in $M$.

For the latter two cases, we show that for some appropriate choice of $m=\mathrm{\Omega }(\log k)$, their total probability is at most $1/poly(k)$. Thus, if we detect that either of them happens, we can choose to return the largest element, which leads to a rank error of $k-1$ and becomes negligible after multiplying with the $1/poly(k)$ probability. The first case is trickier since it can happen with a constant probability.³³3Consider the case that $k\approx n^{\prime }≔|s_{1:n}\cap (-\mathrm{\infty },a)|$, in which case $|s_{1:B}\cap (-\mathrm{\infty },a)|$ roughly follows $\mathrm{𝖡𝗂𝗇𝗈𝗆𝗂𝖺𝗅}(n^{\prime },1/2)$, and can be below $k/2$ with probability $\approx 1/2$. In that case, we return the smallest element (with a rank error of $n^{\prime }-k$), and it turns out that its contribution to the overall error is still under control.

In addition to the need of handling the edge cases outlined above, the analysis of our algorithm is necessarily complicated due to the complex dependence between different parts of the algorithm.

For simplicity, we assume that the algorithm proceeds in a “typical” way, i.e., none of the edge cases happen. Furthermore, we analyze the outermost level of recursion, where the threshold parameter is $a=+\mathrm{\infty }$ (i.e., no element gets ignored). Then, roughly speaking, our algorithm has the following three steps:

Step 1.

Compute a threshold $a^{\prime }\in s_{1:B}$ and let $k^{\prime }≔k/2-{\mathrm{Rank}}_{1:B}(a^{\prime })$.

Step 2.

Run the algorithm recursively on $s_{(B+1):n}$ with parameters $n-B$, $k^{\prime }$ and $a^{\prime }$.

Step 3.

Return the output $x^{\ast }$ of the recursive call as the answer.

Then, the straightforward approach to analyzing the above would be an inductive one: Let $l≔{\mathrm{Rank}}_{(B+1):n}(x^{\ast };a^{\prime })$ denote the actual rank of $x^{\ast }$ among $s_{(B+1):n}\cap (-\mathrm{\infty },a^{\prime })$. By the inductive hypothesis, $|l-k^{\prime }|=O(\sqrt{k^{\prime }})$ in expectation (denoted by $l\approx k^{\prime }\pm O(\sqrt{k^{\prime }})$ informally). If $B$ is sampled from $\mathrm{𝖡𝗂𝗇𝗈𝗆𝗂𝖺𝗅}(n,1/2)$, $\{s_1,s_2,\mathrm{\dots },s_B\}$ would be uniformly distributed among all subsets of $s_{1:n}$. Then, a concentration argument suggests

In total, we would obtain ${\mathrm{Rank}}_{1:n}(x^{\ast })={\mathrm{Rank}}_{1:B}(x^{\ast })+{\mathrm{Rank}}_{(B+1):n}(x^{\ast })\approx k\pm O(\sqrt{k})$.

Unfortunately, the analysis above is technically incorrect. We were analyzing the conditional concentration of ${\mathrm{Rank}}_{1:B}(x^{\ast })$ and ${\mathrm{Rank}}_{(B+1):n}(x^{\ast })$ given the values of $a^{\prime }$, $k^{\prime }$ and $l$. Since $(a^{\prime },k^{\prime },l)$ is determined by the value of $B$ as well as ordering of $s$, after the conditioning, $s_{1:B}$ is no longer uniformly distributed, which invalidates the concentration argument.

Towards a rigorous analysis, we need to carefully untangle the randomness in the three steps above. Crucially, we note that our algorithm is comparison-based, i.e., the behavior of the algorithm is unchanged if we replace $s$ with a different sequence $s^{\prime }$ with the same ordering as $s$. This motivates the following order in which we “realize” the randomness:

• $\mathrm{■}$

  First, we sample $B\sim \mathrm{𝖡𝗂𝗇𝗈𝗆𝗂𝖺𝗅}(n,1/2)$.

• $\mathrm{■}$

  Then, towards analyzing Step 1, we realize the relative ordering of the elements $s_1,s_2,\mathrm{\dots },s_B$ (out of the $B!$ possibilities). This ordering is sufficient for determining $i≔{\mathrm{Rank}}_{1:B}(a^{\prime })$, the rank of $a^{\prime }$ among $s_{1:B}$ as well as the value of $k^{\prime }$.

• $\mathrm{■}$

  We also realize the value of $i_1≔{\mathrm{Rank}}_{1:n}(a^{\prime })$. Conditioning on $(B,i)$, this rank $i_1$ is identically distributed as the $i$-th smallest element in a size-$B$ subset of $[n]$ chosen uniformly at random.

• $\mathrm{■}$

  After that, we realize the relative ordering of the last $(n-B)$ elements $s_{(B+1):n}$ (out of the $(n-B)!$ possibilities). This, in turn, determines the rank of $x^{\ast }$ (the output of the recursive call) among $s_{(B+1):n}\cap (-\mathrm{\infty },a^{\prime })$, denoted by $l≔{\mathrm{Rank}}_{(B+1):n}(x^{\ast };a^{\prime })$.

• $\mathrm{■}$

  At this point, even after conditioning on the values of $(B,i,i_1,l)$, the subset $\{s_1,s_2,\mathrm{\dots },s_B\}$ is still uniformly distributed among all size-$B$ subsets $S\subseteq \{s_1,s_2,\mathrm{\dots },s_n\}$, subject to the constraint that the $i_1$-th largest element among $s_{1:n}$ (namely, $a^{\prime }$) is the $i$-th largest element among $s_{1:B}$.

The uniformity that we retain in the last step above allows us to rigorously prove bounds that are qualitatively similar to Equation 2.

At any time $t$, after reading the first $t$ elements $s_1,s_2,\mathrm{\dots },s_t$ in the random-order stream, the algorithm maintains $m$ consecutive elements out of them. Here, “consecutive” is with respect to the sorted order of the elements, rather than the order in which they arrive. Formally, suppose that the first $t$ elements of $s$, when sorted in decreasing order, are given by $x_1>x_2>\mathrm{\cdots }>x_t$. The algorithm stores the elements $x_l,x_{l+1},\mathrm{\dots },x_r$ as well as the values of $l$ and $r$, where $r-l+1=m$.

Then, what happens when the next element $x^{\prime }≔s_{t+1}$ arrives? By the random-order assumption, $x^{\prime }$ is equally likely to fall into the $t+1$ intervals below:

In particular, we have the three cases below:

Case 1.

$x^{\prime }>x_l$. This happens with probability $l/(t+1)$. In this case, we cannot add $x^{\prime }$ to the array without breaking the invariant that the elements are consecutive. Therefore, we have to keep the $m$ stored elements unchanged, and the parameters $(l,r)$ become $(l^{\prime },r^{\prime })=(l+1,r+1)$ in the next step.

Case 2.

. Similarly, with probability $(t-r+1)/(t+1)$, the condition holds. Again, we cannot update the $m$ elements, and the parameters in the next step remain unchanged, i.e., $(l^{\prime },r^{\prime })=(l,r)$.

Case 3.

$x^{\prime }\in (x_r,x_l)$. The most interesting case is that $x^{\prime }$ falls into one of the $r-l=m-1$ “gaps” among $x_l>x_{l+1}>\mathrm{\cdots }>x_r$, which happens with probability $(m-1)/(t+1)$. In this case, we would obtain $m+1$ consecutive elements among $s_{1:(t+1)}$. Then, we need to kick out one of the two elements at the ends. This gives us some freedom in deciding whether $(l^{\prime },r^{\prime })=(l,r)$ (by kicking out the smallest element) or $(l^{\prime },r^{\prime })=(l+1,r+1)$ (by kicking out the largest element).

At the end of the game, we successfully find the $k$-th largest element if $l\le k\le r$.

Following this strategy, the quantile estimation problem becomes a control problem: We start at time $t=m$ with $(l,r)=(1,m)$. At each of the following steps $t=m+1,m+2,\mathrm{\dots },n$, the value of $(l,r)$ transitions according to the three cases above – either it transitions deterministically (in Cases 1 and 2), or the algorithm may specify whether $l$ and $r$ get incremented by $1$ in Case 3. The goal is to design our strategy in Case 3 (which may vary for different time step $t$ and the values of $(l,r)$ at that step), so that the probability of $k\in [l,r]$ is maximized at time $n$.

The above was exactly the idea in the work of [35], who studied the special case of $k=n/2$. For that special case, their strategy for Case 3 is to choose $(l^{\prime },r^{\prime })$ such that $\left|\frac{l^{\prime }+r^{\prime }}{2}-\frac{t+2}{2}\right|$ is minimized. Intuitively, this makes sure that the median of the stream that has been observed so far is as close to the center of the length-$m$ array as possible. They analyzed the resulting random walk, and showed that a memory of $m=\mathrm{\Theta }(\sqrt{n})$ is sufficient. For the general $k$ case, analyzing the random walk associated with the analogue of the algorithm of [35] becomes more difficult.⁴⁴4As [35] remarked in their work, this random walk is “difficult to analyze exactly since the transition probabilities vary with [the value of $(l,r)$] and with time”.

Our algorithm behind Theorem 8 can be viewed as a staged strategy for the control problem of [35], which admits a slightly simpler analysis.

The algorithm is divided into $\approx {\log }_{2}k$ stages. Roughly speaking, the goal of each stage $i\in \{0,1,\mathrm{\dots },{\log }_{2}k\}$ is to make sure that, after reading the first $(n/k)\cdot 2^i$ elements, we have $l\le 2^i\le r$. What happens when we go from stage $i$ to stage $i+1$? Suppose that, at the end of stage $i$, the $2^i$-th largest element so far (denoted by $x^{\ast }$) is exactly in the middle of the array, i.e., $2^i=\frac{l+r}{2}$. As we read the additional elements in stage $(i+1)$, we maintain the $m$ consecutive elements, such that $x^{\ast }$ is kept in the middle of the array.

By a concentration argument, after stage $i+1$, the rank of $x^{\ast }$ is bounded between $2^{i+1}\pm O(\sqrt{2^i})=2^{i+1}\pm O(\sqrt{k})$. Then, as long as $m\gg \sqrt{k}$, the actual element with rank $2^{i+1}$, denoted by $\tilde{x}$, must be among the $m$ consecutive elements maintained by the algorithm. Then, our algorithm shortens the length-$m$ array that contains consecutive elements, so that $\tilde{x}$ becomes the center of the array. Here, we deviate from the plan outlined earlier, as the value of $r-l+1$ can drop below $m$ from time to time. Fortunately, by another concentration argument, as we go from stage $i+1$ to stage $i+2$, we are going to “absorb” additional elements in to the array, so that the length of the array returns to $m$ before we shorten the array again.

The proof sketch above can be formalized into a high-probability guarantee, which states that, as long as $m=\mathrm{\Omega }(\sqrt{k})$, the algorithm proceeds in the hoped-for manner except with a tiny probability.

We remark that our algorithm can alternatively be viewed as a remedy of the “naïve reduction” from Section 2.1. In Equation 1, by reducing to the $k^{\prime }=k/2$ case, the error doubles and increases by an $O(\sqrt{k})$ amount, resulting in a trivial error bound of $O(k)$. In the algorithm outlined above, however, by utilizing the strategy of [35], we can offset the error by $O(m)$ at each iteration. In particular, as long as $m\gg \sqrt{k}$, the errors accumulated in all stages can be canceled out. This leads to our exact selection guarantee.

We note that our algorithm is comparison-based in the sense that it can be implemented such that the algorithm only accesses the elements in the sequence in the following three ways: (1) compare a pair of elements; (2) return an element as output; (3) pass an element as a parameter of a recursive call. One desirable property of such comparison-based algorithms is that, roughly speaking, the output of the algorithm only depends on the relative ordering of the elements, rather than their exact identities. We formalize this property and use it as the definition of comparison-based algorithms in the following.

Let $n^{\prime }≔|\{s_1,s_2,\mathrm{\dots },s_n\}\cap (-\mathrm{\infty },a)|$ denote the number of elements that are strictly smaller than the threshold $a$. When , the quantile estimation problem is ill-defined, in which case $\text{Find-}k\text{-th}$ always returns $-\mathrm{\infty }$. Note that the case has the highest priority among all edge cases in the sense that, before the algorithm tries to output anything (possibly as a result of handling other corner cases), it makes sure to read through the end of the stream $s$ to check whether (and outputs $-\mathrm{\infty }$ if so).

On Line 3, we choose to use the straightforward algorithm for quantile estimation when $k\le m$. This serves as the boundary condition of the recursion, and also ensures that the parameter $\frac{2m}{3k}$ on Line 5 is indeed in $[0,1]$, and thus valid.

On Line 10, if it turns out that , we return the smallest element in the entire stream. To see why we do this, recall that there are $n^{\prime }$ elements in $s_{1:n}\cap (-\mathrm{\infty },a)$. If we are not in the edge case that , we should expect that there are $\approx n^{\prime }/2\ge k/2$ elements in $s_{1:B}\cap (-\mathrm{\infty },a)$, since $s_{1:B}$, as a set, is uniformly distributed among all subsets of $\{s_1,s_2,\mathrm{\dots },s_n\}$. Therefore, whenever the edge case happens, we are sure that $n^{\prime }$ only exceeds $k$ by a small amount, in which case outputting the $n^{\prime }$-th largest element in $s\cap (-\mathrm{\infty },a)$ (namely, the smallest element in $s$) is accurate enough.

When the above does not happen, we aim to find an element $a^{\prime }$ in the first half of the stream, $s_{1:B}$, so that $a^{\prime }$ is close to the $\lfloor k/2\rfloor$-th largest among $s_{1:B}\cap (-\mathrm{\infty },a)$. On Line 15, if we fail to find such an $a^{\prime }$, we return the largest element among $s_{1:n}\cap (-\mathrm{\infty },a)$, which has a rank of $1$. While doing so leads to an error of $k-1$ in the rank, this edge case only happens with probability $1/poly(k)$, so the contribution to the expected error is negligible.

If none of the edge cases above happen, $\text{Find-}k\text{-th}$ calls itself recursively and gets an output $x$. The final edge case is that this $x$ might take value $-\mathrm{\infty }$, as a result of encountering the first edge case in the recursive call. If this happens, we translate $-\mathrm{\infty }$ to the smallest element $\underset{¯}{x}$ in the stream.

We will prove the error bound of $\text{Find-}k\text{-th}$ by induction. As mentioned in Section 2.2, a rigorous analysis is complicated because, for the inductive step, we need to show that the accuracy of the recursive call

(conditioning on all the parameters) implies the accuracy of the original procedure. For this purpose, we might hope that $s_{(B+1):n}$ (as a set) is uniformly distributed among all size-$(n-B)$ subsets of $s_{1:n}$, so that we can translate the rank of $x^{\ast }$ among $s_{(B+1):n}$ to its rank among the entire stream $s_{1:n}$. Unfortunately, this uniformity might not hold, since the conditioning on $a^{\prime }$ and ${\mathrm{Rank}}_{1:B}(a^{\prime };a)$ would bias the conditional distribution of $s_{(B+1):n}$.

To make the analysis valid, we need to “realize” the randomness of $s_{1:n}$ in a specific order. In the following, we sketch the analysis assuming that none of the edge cases above happen:

• $\mathrm{■}$

  First, over the randomness in $B\sim \mathrm{𝖡𝗂𝗇𝗈𝗆𝗂𝖺𝗅}(n,1/2)$, $s_{1:B}$ is uniformly distributed among all subsets of $s_{1:n}$. In particular, $s_{1:B}\cap (-\mathrm{\infty },a)$ is a uniformly random subset of $s_{1:n}\cap (-\mathrm{\infty },a)$. It follows that: (1) $B^{\prime }≔|s_{1:B}\cap (-\mathrm{\infty },a)|$ follows the distribution $\mathrm{𝖡𝗂𝗇𝗈𝗆𝗂𝖺𝗅}(n^{\prime },1/2)$, where $n^{\prime }≔|s_{1:n}\cap (-\mathrm{\infty },a)|$; (2) Conditioning on the realization of $B^{\prime }$, $s_{1:B}\cap (-\mathrm{\infty },a)$ is uniformly distributed among all size-$B^{\prime }$ subsets of the size-$n^{\prime }$ set $s_{1:n}\cap (-\mathrm{\infty },a)$.

• $\mathrm{■}$

  We condition on the realization of $B^{\prime }$. The algorithm finds an element $a^{\prime }\in s_{1:B}$ on Line 12. Let $i≔{\mathrm{Rank}}_{1:B}(a^{\prime };a)$ denote its rank among the first half (when only elements below $a$ are considered). Note that the distribution of $i$ is solely determined by the value of $B^{\prime }$, since the algorithm is comparison-based (Definition 9).

• $\mathrm{■}$

  Conditioning on the realization of $(B^{\prime },i)$, $a^{\prime }$ is identically distributed as the $i$-th largest element in a uniformly random size-$B^{\prime }$ subset of $s_{1:n}\cap (-\mathrm{\infty },a)$. Let $i_1≔{\mathrm{Rank}}_{1:n}(a^{\prime };a)$ denote the rank of $a^{\prime }$. Later, we can analyze the concentration of $i_1\mid B^{\prime },i$.

• $\mathrm{■}$

  Conditioning on the realization of $(B^{\prime },i,i_1)$, the algorithm makes a recursive call (on Line 16) to find the $k^{\prime }$-th largest among $s_{(B+1):n}\cap (-\mathrm{\infty },a^{\prime })$, where $k^{\prime }≔\lfloor k/2\rfloor -i$. Let $x^{\ast }$ denote the element returned by the recursive call, and $l≔{\mathrm{Rank}}_{B+1:n}(x^{\ast };a^{\prime })$ be its actual rank. During the inductive proof, we will use the induction hypothesis that $l\mid B^{\prime },i,i_1$ concentrates around $k^{\prime }$.

• $\mathrm{■}$

  Conditioning on $(B^{\prime },i,i_1,l)$, $x^{\ast }$ is the $l$-th largest element among $s_{(B+1):n}\cap (-\mathrm{\infty },a^{\prime })$. Furthermore, we can verify that $s_{(B+1):n}\cap (-\mathrm{\infty },a^{\prime })$ is uniformly distributed among all size-$(n-i_1-(B-i))$ subsets of $s_{1:n}\cap (-\mathrm{\infty },a^{\prime })$. Applying another concentration bound shows that ${\mathrm{Rank}}_{1:n}(x^{\ast };a^{\prime })$ concentrates, which in turn implies the concentration of ${\mathrm{Rank}}_{1:n}(x^{\ast };a)={\mathrm{Rank}}_{1:n}(x^{\ast };a^{\prime })+i_1$.

• $\mathrm{■}$

  Finally, our goal is to show that the rank of $x^{\ast }$, ${\mathrm{Rank}}_{1:n}(x^{\ast };a)$, concentrates around $k$. For this purpose, we will start with the conditional concentration bound above, and take an expectation over the joint distribution of $(B^{\prime },i,i_1,l)$.