Return to Answer

This answer gives exact formulas for the expected number of steps, with and without replacement. To be clear, we interpret OP's problem as detailed in OP's Python gist: each step of the process makes one random comparison, and the process stops as soon as the comparisons made are sufficient to determine the total order.

Lemma 1. (i) Without replacement the expected number of comparisons is $${n \choose 2} H_{n-1},$$ where $H_k = \sum_{i=1}^k \frac 1 i \approx 0.5+\ln k$ is the $k$th harmonic number.

(ii) With replacement, the expected number of comparisons is $$n^2/2 - n + 3/2 - 1/n.$$

Proof. Assume WLOG that the set of numbers in $x$ is $[n]$. Let random variable $T$ be the total number of steps.

As observed in @user3257842's answer, a necessary and sufficient condition for the full order to be known is that, for all $i\in [n-1]$, the positions holding elements $i$ and $i+1$ have been compared. Call such positions "neighbors".

Proof of Part (i). For $m \in [n-1]$, let random variable $T_m$ be the number of steps such that, at the start of the step, the number of neighbors that have not yet been compared is $m$. Then the total number of steps is $T=T_{n-1} + T_{n-2} + \cdots + T_1$. By linearity of expectation, $E[T] = \sum_{m=1}^{n-1} E[T_m]$. To finish, we calculate $E[T_m]$ for any $m\in [n-1]$.

Consider any $m\in [n-1]$. Consider any iteration that starts with $m$ neighbors not yet compared. Given this, $m$ of the $n\choose 2$ possible comparisons would compare one not-yet compared pair of neighbors, while the remaining comparisons would not (so would leave the number of uncompared neighbors unchanged). So the number of not-yet-compared neighbors either stays the same, or, with probability $m/{n\choose 2}$, reduces by 1. It follows that $E[T_m]$, the expected number of steps that start with $m$ uncompared neighbors, is ${n\choose 2}/m$.

So $E[T] = \sum_{m=1}^{n-1} {n\choose 2}/m = {n\choose 2} H_{n-1}$, proving Part (i).

Proof of Part (ii). View the process as follows: a random permutation of the $n\choose 2$ pairs is chosen, and then the algorithm checks each pair (in the chosen order) just until it has compared all neighboring pairs.

That is, we want the expected position of the last neighboring pair in the random ordering of pairs. There are $n-1$ neighboring pairs and ${n\choose 2} - (n-1) = {n-1\choose 2}$ non-neighboring pairs. By a standard calculation, the expected position of the last neighboring pair is ${n \choose 2} - {n-1\choose 2}/n = n^2/2 - n + 3/2 - 1/n$. $~~~\Box$

Here is some intuition about the last "standard calculation". Suppose you choose a $k$-subset $S$ uniformly at random from $[m+k]$. What's the expectation of $\max S$? The $k$ chosen elements divide the $m$ unchosen elements into $k+1$ intervals of total size $m$. By a symmetry argument the expected number of elements in each of these intervals is the same, so each interval has size $m/(k+1)$ in expectation. In particular, the expected size of the last interval is $m/(k+1)$, so the expectation of the largest element is $m+k - m/(k+1)$.

In our case $m+k = {n \choose 2}$ and $k=n-1$.

This answer gives exact formulas for the expected number of steps, with and without replacement. To be clear, we interpret OP's problem as detailed in OP's Python gist: each step of the process makes one random comparison, and the process stops as soon as the comparisons made are sufficient to determine the total order.

Lemma 1. (i) With replacement the expected number of comparisons is $${n \choose 2} H_{n-1},$$ where $H_k = \sum_{i=1}^k \frac 1 i \approx 0.5+\ln k$ is the $k$th harmonic number.

(ii) Without replacement, the expected number of comparisons is $$n^2/2 - n + 3/2 - 1/n.$$

Proof. Assume WLOG that the set of numbers in $x$ is $[n]$. Let random variable $T$ be the total number of steps.

As observed in @user3257842's answer, a necessary and sufficient condition for the full order to be known is that, for all $i\in [n-1]$, the positions holding elements $i$ and $i+1$ have been compared. Call such positions "neighbors".

Proof of Part (i). For $m \in [n-1]$, let random variable $T_m$ be the number of steps such that, at the start of the step, the number of neighbors that have not yet been compared is $m$. Then the total number of steps is $T=T_{n-1} + T_{n-2} + \cdots + T_1$. By linearity of expectation, $E[T] = \sum_{m=1}^{n-1} E[T_m]$. To finish, we calculate $E[T_m]$ for any $m\in [n-1]$.

Consider any $m\in [n-1]$. Consider any iteration that starts with $m$ neighbors not yet compared. Given this, $m$ of the $n\choose 2$ possible comparisons would compare one not-yet compared pair of neighbors, while the remaining comparisons would not (so would leave the number of uncompared neighbors unchanged). So the number of not-yet-compared neighbors either stays the same, or, with probability $m/{n\choose 2}$, reduces by 1. It follows that $E[T_m]$, the expected number of steps that start with $m$ uncompared neighbors, is ${n\choose 2}/m$.

So $E[T] = \sum_{m=1}^{n-1} {n\choose 2}/m = {n\choose 2} H_{n-1}$, proving Part (i).

Proof of Part (ii). View the process as follows: a random permutation of the $n\choose 2$ pairs is chosen, and then the algorithm checks each pair (in the chosen order) just until it has compared all neighboring pairs.

That is, we want the expected position of the last neighboring pair in the random ordering of pairs. There are $n-1$ neighboring pairs and ${n\choose 2} - (n-1) = {n-1\choose 2}$ non-neighboring pairs. By a standard calculation, the expected position of the last neighboring pair is ${n \choose 2} - {n-1\choose 2}/n = n^2/2 - n + 3/2 - 1/n$. $~~~\Box$

Here is some intuition about the last "standard calculation". Suppose you choose a $k$-subset $S$ uniformly at random from $[m+k]$. What's the expectation of $\max S$? The $k$ chosen elements divide the $m$ unchosen elements into $k+1$ intervals of total size $m$. By a symmetry argument the expected number of elements in each of these intervals is the same, so each interval has size $m/(k+1)$ in expectation. In particular, the expected size of the last interval is $m/(k+1)$, so the expectation of the largest element is $m+k - m/(k+1)$.

In our case $m+k = {n \choose 2}$ and $k=n-1$.

To be clear, we interpret the problem as follows. Given an array $x$ of $n$ distinct numbers, the algorithm iterates as follows: at each step it chooses a pair $x[i]$ and $x[j]$ with $1\le i < j \le n$ uniformly at random, then learns either that $x[i] < x[j]$ or that $x[i] > x[j]$. The question is, how many steps, in expectation, are required before the learned comparisons suffice to determine the order of the elements. (This is the interpretation taken in OP's Python gist.)

Lemma 1. (i) Without replacement the expected number of comparisons is ${n \choose 2} H_{n-1}$, where $H_k = \sum_{i=1}^k \frac 1 i \approx 0.5+\ln k$ is the $k$th harmonic number.

(ii) With replacement, the expected number of comparisons is $n^2/2 - n + 3/2 - 1/n$.

Proof. Assume WLOG that the set of numbers in $x$ is $[n]$. Let random variable $T$ be the total number of steps.

As observed in @user3257842's answer, a necessary and sufficient condition for the full order to be known is that, for all $i\in [n-1]$, the positions holding elements $i$ and $i+1$ have been compared. Call such positions "neighbors".

Proof of Part (i). For $m \in [n-1]$, let random variable $T_m$ be the number of steps such that, at the start of the step, the number of neighbors that have not yet been compared is $m$. Then the total number of steps is $T=T_{n-1} + T_{n-2} + \cdots + T_1$. By linearity of expectation, $E[T] = \sum_{m=1}^{n-1} E[T_m]$. To finish, we calculate $E[T_m]$ for any $m\in [n-1]$.

Consider any $m\in [n-1]$. Consider any iteration that starts with $m$ neighbors not yet compared. Given this, $m$ of the $n\choose 2$ possible comparisons would compare one not-yet compared pair of neighbors, while the remaining comparisons would not (so would leave the number of uncompared neighbors unchanged). So the number of not-yet-compared neighbors either stays the same, or, with probability $m/{n\choose 2}$, reduces by 1. It follows that $E[T_m]$, the expected number of steps that start with $m$ uncompared neighbors, is ${n\choose 2}/m$.

So $E[T] = \sum_{m=1}^{n-1} {n\choose 2}/m = {n\choose 2} H_{n-1}$, proving Part (i).

Proof of Part (ii). View the process as follows: a random permutation of the $n\choose 2$ pairs is chosen, and then the algorithm checks each pair (in the chosen order) just until it has compared all neighboring pairs.

That is, we want the expected position of the last neighboring pair in the random ordering of pairs. There are $n-1$ neighboring pairs and ${n\choose 2} - (n-1) = {n-1\choose 2}$ non-neighboring pairs. By a standard calculation, the expected position of the last neighboring pair is ${n \choose 2} - {n-1\choose 2}/n = n^2/2 - n + 3/2 - 1/n$. $~~~\Box$

Here is some intuition about the last "standard calculation". Suppose you choose a $k$-subset $S$ uniformly at random from $[m+k]$. What's the expectation of $\max S$? The $k$ chosen elements divide the $m$ unchosen elements into $k+1$ intervals of total size $m$. By a symmetry argument the expected number of elements in each of these intervals is the same, so each interval has size $m/(k+1)$ in expectation. In particular, the expected size of the last interval is $m/(k+1)$, so the expectation of the largest element is $m+k - m/(k+1)$.

In our case $m+k = {n \choose 2}$ and $k=n-1$.

This answer gives exact formulas for the expected number of steps, with and without replacement. To be clear, we interpret OP's problem as detailed in OP's Python gist: each step of the process makes one random comparison, and the process stops as soon as the comparisons made are sufficient to determine the total order.

Lemma 1. (i) Without replacement the expected number of comparisons is $${n \choose 2} H_{n-1},$$ where $H_k = \sum_{i=1}^k \frac 1 i \approx 0.5+\ln k$ is the $k$th harmonic number.

(ii) With replacement, the expected number of comparisons is $$n^2/2 - n + 3/2 - 1/n.$$

Proof. Assume WLOG that the set of numbers in $x$ is $[n]$. Let random variable $T$ be the total number of steps.

As observed in @user3257842's answer, a necessary and sufficient condition for the full order to be known is that, for all $i\in [n-1]$, the positions holding elements $i$ and $i+1$ have been compared. Call such positions "neighbors".

Proof of Part (i). For $m \in [n-1]$, let random variable $T_m$ be the number of steps such that, at the start of the step, the number of neighbors that have not yet been compared is $m$. Then the total number of steps is $T=T_{n-1} + T_{n-2} + \cdots + T_1$. By linearity of expectation, $E[T] = \sum_{m=1}^{n-1} E[T_m]$. To finish, we calculate $E[T_m]$ for any $m\in [n-1]$.

Consider any $m\in [n-1]$. Consider any iteration that starts with $m$ neighbors not yet compared. Given this, $m$ of the $n\choose 2$ possible comparisons would compare one not-yet compared pair of neighbors, while the remaining comparisons would not (so would leave the number of uncompared neighbors unchanged). So the number of not-yet-compared neighbors either stays the same, or, with probability $m/{n\choose 2}$, reduces by 1. It follows that $E[T_m]$, the expected number of steps that start with $m$ uncompared neighbors, is ${n\choose 2}/m$.

So $E[T] = \sum_{m=1}^{n-1} {n\choose 2}/m = {n\choose 2} H_{n-1}$, proving Part (i).

Proof of Part (ii). View the process as follows: a random permutation of the $n\choose 2$ pairs is chosen, and then the algorithm checks each pair (in the chosen order) just until it has compared all neighboring pairs.

That is, we want the expected position of the last neighboring pair in the random ordering of pairs. There are $n-1$ neighboring pairs and ${n\choose 2} - (n-1) = {n-1\choose 2}$ non-neighboring pairs. By a standard calculation, the expected position of the last neighboring pair is ${n \choose 2} - {n-1\choose 2}/n = n^2/2 - n + 3/2 - 1/n$. $~~~\Box$

Here is some intuition about the last "standard calculation". Suppose you choose a $k$-subset $S$ uniformly at random from $[m+k]$. What's the expectation of $\max S$? The $k$ chosen elements divide the $m$ unchosen elements into $k+1$ intervals of total size $m$. By a symmetry argument the expected number of elements in each of these intervals is the same, so each interval has size $m/(k+1)$ in expectation. In particular, the expected size of the last interval is $m/(k+1)$, so the expectation of the largest element is $m+k - m/(k+1)$.

In our case $m+k = {n \choose 2}$ and $k=n-1$.

To be clear, we interpret the problem as follows. Given an array $x$ of $n$ distinct numbers, the algorithm iterates as follows: at each step it chooses a pair $x[i]$ and $x[j]$ with $1\le i < j \le n$ uniformly at random, then learns either that $x[i] < x[j]$ or that $x[i] > x[j]$. The question is, how many steps, in expectation, are required before the learned comparisons suffice to determine the order of the elements.

Lemma 1. (i) Without replacement the expected number of comparisons is ${n \choose 2} H_{n-1}$, where $H_k = \sum_{i=1}^k \frac 1 i \approx 0.5+\ln k$ is the $k$th harmonic number.

(ii) With replacement, the expected number of comparisons is $n^2/2 - n + 3/2 - 1/n$.

Proof. Assume WLOG that the set of numbers in $x$ is $[n]$. Let random variable $T$ be the total number of steps.

As observed in @user3257842's answer, a necessary and sufficient condition for the full order to be known is that, for all $i\in [n-1]$, the positions holding elements $i$ and $i+1$ have been compared. Call such positions "neighbors".

Proof of Part (i). For $m \in [n-1]$, let random variable $T_m$ be the number of steps such that, at the start of the step, the number of neighbors that have not yet been compared is $m$. Then the total number of steps is $T=T_{n-1} + T_{n-2} + \cdots + T_1$. By linearity of expectation, $E[T] = \sum_{m=1}^{n-1} E[T_m]$. To finish, we calculate $E[T_m]$ for any $m\in [n-1]$.

Consider any $m\in [n-1]$. Consider any iteration that starts with $m$ neighbors not yet compared. Given this, $m$ of the $n\choose 2$ possible comparisons would compare one not-yet compared pair of neighbors, while the remaining comparisons would not (so would leave the number of uncompared neighbors unchanged). So the number of not-yet-compared neighbors either stays the same, or, with probability $m/{n\choose 2}$, reduces by 1. It follows that $E[T_m]$, the expected number of steps that start with $m$ uncompared neighbors, is ${n\choose 2}/m$.

So $E[T] = \sum_{m=1}^{n-1} {n\choose 2}/m = {n\choose 2} H_{n-1}$, proving Part (i).

Proof of Part (ii). View the process as follows: a random permutation of the $n\choose 2$ pairs is chosen, and then the algorithm checks each pair (in the chosen order) just until it has compared all neighboring pairs.

That is, we want the expected position of the last neighboring pair in the random ordering of pairs. There are $n-1$ neighboring pairs and ${n\choose 2} - (n-1) = {n-1\choose 2}$ non-neighboring pairs. By a standard calculation, the expected position of the last neighboring pair is ${n \choose 2} - {n-1\choose 2}/n = n^2/2 - n + 3/2 - 1/n$. $~~~\Box$

Here is some intuition about the last "standard calculation". Suppose you choose a $k$-subset $S$ uniformly at random from $[m+k]$. What's the expectation of $\max S$? The $k$ chosen elements divide the $m$ unchosen elements into $k+1$ intervals of total size $m$. By a symmetry argument the expected number of elements in each of these intervals is the same, so each interval has size $m/(k+1)$ in expectation. In particular, the expected size of the last interval is $m/(k+1)$, so the expectation of the largest element is $m+k - m/(k+1)$.

In our case $m+k = {n \choose 2}$ and $k=n-1$.

To be clear, we interpret the problem as follows. Given an array $x$ of $n$ distinct numbers, the algorithm iterates as follows: at each step it chooses a pair $x[i]$ and $x[j]$ with $1\le i < j \le n$ uniformly at random, then learns either that $x[i] < x[j]$ or that $x[i] > x[j]$. The question is, how many steps, in expectation, are required before the learned comparisons suffice to determine the order of the elements. (This is the interpretation taken in OP's Python gist.)

Lemma 1. (i) Without replacement the expected number of comparisons is ${n \choose 2} H_{n-1}$, where $H_k = \sum_{i=1}^k \frac 1 i \approx 0.5+\ln k$ is the $k$th harmonic number.

(ii) With replacement, the expected number of comparisons is $n^2/2 - n + 3/2 - 1/n$.

Proof. Assume WLOG that the set of numbers in $x$ is $[n]$. Let random variable $T$ be the total number of steps.

As observed in @user3257842's answer, a necessary and sufficient condition for the full order to be known is that, for all $i\in [n-1]$, the positions holding elements $i$ and $i+1$ have been compared. Call such positions "neighbors".

Proof of Part (i). For $m \in [n-1]$, let random variable $T_m$ be the number of steps such that, at the start of the step, the number of neighbors that have not yet been compared is $m$. Then the total number of steps is $T=T_{n-1} + T_{n-2} + \cdots + T_1$. By linearity of expectation, $E[T] = \sum_{m=1}^{n-1} E[T_m]$. To finish, we calculate $E[T_m]$ for any $m\in [n-1]$.

Consider any $m\in [n-1]$. Consider any iteration that starts with $m$ neighbors not yet compared. Given this, $m$ of the $n\choose 2$ possible comparisons would compare one not-yet compared pair of neighbors, while the remaining comparisons would not (so would leave the number of uncompared neighbors unchanged). So the number of not-yet-compared neighbors either stays the same, or, with probability $m/{n\choose 2}$, reduces by 1. It follows that $E[T_m]$, the expected number of steps that start with $m$ uncompared neighbors, is ${n\choose 2}/m$.

So $E[T] = \sum_{m=1}^{n-1} {n\choose 2}/m = {n\choose 2} H_{n-1}$, proving Part (i).

Proof of Part (ii). View the process as follows: a random permutation of the $n\choose 2$ pairs is chosen, and then the algorithm checks each pair (in the chosen order) just until it has compared all neighboring pairs.

That is, we want the expected position of the last neighboring pair in the random ordering of pairs. There are $n-1$ neighboring pairs and ${n\choose 2} - (n-1) = {n-1\choose 2}$ non-neighboring pairs. By a standard calculation, the expected position of the last neighboring pair is ${n \choose 2} - {n-1\choose 2}/n = n^2/2 - n + 3/2 - 1/n$. $~~~\Box$

Here is some intuition about the last "standard calculation". Suppose you choose a $k$-subset $S$ uniformly at random from $[m+k]$. What's the expectation of $\max S$? The $k$ chosen elements divide the $m$ unchosen elements into $k+1$ intervals of total size $m$. By a symmetry argument the expected number of elements in each of these intervals is the same, so each interval has size $m/(k+1)$ in expectation. In particular, the expected size of the last interval is $m/(k+1)$, so the expectation of the largest element is $m+k - m/(k+1)$.

In our case $m+k = {n \choose 2}$ and $k=n-1$.