# On the Moments of the Number of Hires in the Assistant Hiring Algorithm
## 2 The Results  
Let \(H\) be the number of hires. Then, we can write  
\[H=H_{1}+H_{2}+\ldots+H_{n}, \tag{2}\]  
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},\ldots,r_{j}\), and if we sort them in increasing order \(z_{1}\leq z_{2}\leq...\leq z_{j}\), and we identify \(z_{k}\) with \(k\), we can simply work with the subarray of rankings \(1,2,\ldots,j\). In particular,  
\[P(H_{j}=1)=\frac{(j-1)!}{j!}=\frac{1}{j},\]  
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 \(EH_{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. The variables \(H_{i}\) and \(H_{j}\), \(i<j\), are independent. Proof. : We will prove that \(P(H  
\[=\frac{(j-i-1)!i!}{ij(i-1)!(j-1)!}\sum_{\alpha=i}^{j-1}\frac{(\alpha-1)!}{(\alpha- i)!}=\frac{1}{ij(\binom{j-1}{i})}\sum_{\alpha=i}^{j-1}\binom{\alpha-1}{i-1}.\]  
However,  
\[\sum_{\alpha=i}^{j-1}\binom{\alpha-1}{i-1}=\binom{j-1}{i},\]  
by the well-known hockey stick identity (also known as [PERSON]'s theorem; see [5]) and, therefore, \(P(H_{i}=1,H_{j}=1)=\frac{1}{i!}\). It is trivial to see that this is enough to prove the independence of the variables, that is, \(P(H_{i}=a,H_{j}=b)=P(H_{i}=a)P(H_{j}=b)\), where \(a\) and \(b\) can be arbitrarily chosen as either \(0\) or \(1\). As the variables \(H_{i}\) are _pairwise_ independent, a simple computation of \(Var(H)\) 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  
\[Var(H)=\sum_{i=1}^{n}Var(H_{i})+2\sum_{i<j}Cov(H_{i},H_{j})=\sum_{i=1}^{n}Var( H_{i})=\mathcal{H}_{n}(1)-\mathcal{H}_{n}(2).\]  
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. **Proposition 2**. : _The variables \(H_{i_{1}},H_{i_{2}},\ldots,H_{i_{s}},\)\(i_{1}<i_{2}<\ldots<i_{s}\), are independent._  
Proof. : Let us prove that \(H_{i},H_{j},H_{k}\) are independent for \(i<j<k\). Again, since these variables only take two values, \(0\) and \(1\), it is enough to show that  
\[P(H_{i}=H_{j}=H_{k}=1)=P(H_{i}=1)P(H_{j}=1)P(H_{k}=1)=\frac{1}{ijk}.\]  
Arguing as before, we can restrict our attention to the rankings \(1,2,\ldots,k\). Candidate \(k\) must obtain the ranking \(k\); thus, the possibles values of the ranking \(\alpha\) for candidate \(j\) are \(\{j,j+1,\ldots,k-1\}\). Once the rank \(\alpha\) is fixed, it is clear that the possible values \(\beta\) for the ranking of candidate \(i\) are \(\{i,i+1,\ldots,\alpha-1\}\). Once we fix \(\beta\), there are \(\beta-1\) possible rankings to be placed between candidates \(1\) and \(i-1\) in \(\frac{(\beta-1)!}{(\beta-i)! }\) ways. Next, between candidates \(i+1\) and \(j-1\), we can place \(\alpha-i-1\) available rankings in \(\frac{(\alpha-i-1)!}{(\alpha-j)! }\) ways. Finally, between candidates \(j+1\) and \(k-1\) we can place the remaining \(k-j-1\) unassigned rankings in \((k-j-1)!\) ways.