On the Moments of the Number of Hires in the Assistant Hiring Algorithm

Cormen et al.’s book [1] is a widely used textbook in colleges worldwide and is a standard reference for researchers. When discussing the probabilistic analysis of algorithms in chapter 5, the authors introduce the assistant hiring algorithm, where n candidates, with rankings from 1 (worst) to n (best), scrambled in random order, are interviewed to fill an assistant position. Every time a candidate is better (i.e., has a higher ranking) than the current one, (s)he is hired and the current one is fired. The first applicant is always hired. Under the hypothesis that all $n!$ permutations of the rankings are equally likely, using indicator random variables and the linearity of the expected value, the authors compute the expected number of hires as

The sum above, the n-th harmonic number, will be denoted by ${\mathcal{H}}_n\left(1\right)$. More generally, we will use the notation

The variance in the number of hires in the assistant hiring algorithm, a relevant parameter that provides a measure of the spread of the H values around its expectation, is not computed in [1]. In his seminal book [2], Donald Knuth also introduces a probabilistic analysis of algorithms by looking at the same assistant hiring problem, but refers to this with a less playful name: Algorithm M (finding the maximum: page 96 and the following). He obtains both the expectation and the variance, referring the reader to [3] for the asymptotic values of higher moments, although in this article they base their analysis of the higher moments on a further reference on power series with a finite number of singularities: [4]. In both [2] and [3], they find difference equations for the probability mass function of H and derive formulas for the factorial moment generating function $M_X^{\ast }\left(t\right)=E{t}^X$ of H through some computations involving Stirling numbers and Lagrange’s method for solving differential equations.

In this self-contained note, we revisit the assistant hiring algorithm, which essentially looks at the number of times the value of the current maximum is updated when finding the maximum element of a random permutation. Our approach is different, in that we do not focus on the probability mass function of H, and we believe it is simpler. We first prove that H can be expressed as the sum of independent indicator variables, using a well-known combinatorial identity, the hockey stick identity. Then, we obtain a reasonably compact moment generating function $M_H\left(t\right)=E{e}^{tX}$ that allows for us to find exact expressions for its first three moments, as well as asymptotic values for its higher moments, using simple differentiation and an inductive argument.

Let H be the number of hires. Then, we can write where $H_i=1$ in case the candidate i is hired, and $H_i=0$ otherwise. It is not clear that $H_i$ and $H_j$ are independent random variables: if $i<j$, a possible heuristic would say that the hiring of candidate j in the future should not affect the hiring of the earlier candidate i, but we can turn this heuristic around and say that the hiring of candidate i implies a large value for the ranking for this candidate, possibly affecting the occurrence of large rankings for future candidate j. Heuristics aside, we argue that the joint behavior of the candidates i and j, $i<j$ is only determined by the rankings $r_1,r_2,\dots ,r_j$, and if we sort them in increasing order $z_1\le z_2\le ...\le z_j$, and we identify $z_k$ with k, we can simply work with the subarray of rankings $1,2,\dots ,j$. In particular, the reason being that, in order for candidate j to be hired, their ranking should be j and all previous candidates may have any of the remaining $j-1$ rankings. From this, we conclude that $E{H}_j=P(H_j=1)=\frac{1}{j}$. This fact, and the linearity of the expectation, imply that taking expectations on both sides of (2) yields (1). With these preliminaries, we can prove the following.

As the variables $H_i$ are pairwise independent, a simple computation of $Var\left(H\right)$ follows. Indeed, using the formula for the variance of the sum, and since the independence of two variables implies that their covariance vanishes, we obtain

The previous derivation of the variance is simple enough to find its way into an introductory textbook on the subject. However, to find higher orders of H, we will need to resort to the moment generating function of the random variable, and first obtain the following.

The two-valued random variable $H_i$ has a simple moment generating function (m.g.f.): and since the $H_i$s are independent, the m.g.f of H is the product of the m.g.f.s of the $H_i$s, that is,

The relatively simple expression for the m.g.f of H is a direct consequence of the independence of the $H_i$. Without this fact, finding the m.g.f. of H would be a much harder task. Now, in principle, we could obtain the moments of H by taking the derivatives of $M_H$ and evaluating them at $t=0$. The formulas become more involved after a few differentiations, but we can obtain some asymptotics for $E{H}^k$. We first note that and

By evaluating (4) and (5) at $t=0$, we obtain and

Therefore, we recover (1) and the variance as

Another differentiation of (5) yields

Evaluating at $t=0$, we obtain

It is well-known (see [1]) that ${\mathcal{H}}_n\left(1\right)=lnn+O\left(1\right)$, or, in a more compact and somewhat less informative way, ${\mathcal{H}}_n\left(1\right)=\mathsf{\Theta }(lnn)$, where the constants involved in the upper and lower bounds are both equal to 1. As the numbers ${\mathcal{H}}_n\left(k\right)$, for $k\ge 2$, are partial sums of convergent series, we see that the dominating term there is ${\mathcal{H}}_n{\left(1\right)}^3$ and, thus, $E{H}^3=\mathsf{\Theta }\left({(lnn)}^3\right)$.

By inspecting Formula (6) and proceeding recursively, we see that the k-th derivative of $M_H\left(t\right)$ can be written as: where the $G_j\left(t\right)$ are functions involving powers of $e^t$ and sums of inverse powers of $e^t+i$, $0\le i\le n-1$. After evaluating at $t=0$, this becomes or

The values $G_j\left(0\right)$ involve either partial sums of convergent series, or ${\mathcal{H}}_n\left(1\right)$, and inside the summation there are only moments $E{H}^j$ for $j\le k-2$. Thus, a simple inductive argument tells us that the dominant term in (8) is $E{H}^{k-1}{\mathcal{H}}_n\left(1\right)$, or, in other words, for $k\ge 1$, where the constants involved in the upper and lower bounds are both equal to 1.

In this note, we studied the random variable that counts the number of hires in the assistant hiring algorithm, or, in other words, the number of updates to the current maximum when searching for the maximum element in a random permutation of an array of real numbers. We found exact expressions for its first three moments, and asymptotic values for its higher moments. The technique was to write the random variable under consideration as the sum of indicator variables that take the value 1 if a hire is carried out in the i-th interview (or, in other words, if an update of the current maximum is performed after the inspection of the i-th number), and 0 otherwise. An application of the hockey stick identity showed that these indicator variables are independent, implying that the moment generating function of the variable under consideration equals the product of the simple moment generating functions of the indicator variables. We obtained thus a reasonable expression for the moment generating function, which differentiated and evaluated at 0 yielded that the k-th moment of the variable under study, asymptotically, is the k-th power of the natural logarithm. We believe that our method, which does not rely on explicit knowledge of the probability mass function of the variable under study, is simpler than other treatments of the algorithm found in the literature. The basic idea of decomposing a random variable into the sum of indicator random variables is well-known, and is used extensively for the analysis of algorithms, at least for computation of the expected values, in textbooks such as [1]. Due to the linearity of the expectation, the expected value of the original variable is simply the sum of the expected values of the indicator variables, which, in turn, is the probability that the indicator variables take the value 1. However, we must warn that the computation of the variance, or that of higher moments, can be a difficult task unless the indicator variables are independent, as was the case in the assistant hiring algorithm.