Motivation. Suppose we have a number of images that we want to arrange in a linear order from the prettiest to the ugliest. At our disposal we have a trained aesthete, whom we can show two pictures and ask him which is the prettiest. We assume that the aesthete's preferences are unchanging and internally consistent. (That's a pretty big assumption, but this is mathematics: Our assumptions don't have to be likely, only consistent).
Our task is to discover the true aesthetic order between the images without paying the aesthete for too much work. Ideally we would use a good close-to-minimal comparison sorting algorithm, such as binary insertion sort which comes within $n$ of the information-theoretic bound of $\log_2 n!$ comparisons.
Unfortunately most of the algorithms at hand tend to ask the aesthete runs of questions where he's asked to compare the same image to several other images in succession, and he finds that so boring that he threatens to increase his rates. While we're trying to find a better algorithm, the junior member of the design team suggests just to ask random questions until we know enough (but avoiding questions that we can deduce the answer to already). Is this a good idea?
Actual question. Given $n$, let $R_0$ be the identity relation on $\{1,2,3,\ldots,n\}$. As long as $R_k$ is not a total order, choose $(a,b)$ uniformly in $\{(a,b) \mid 1\le a<b\le n\}\setminus R_k$, and let $R_{k+1}$ be the transitive closure of $R_k\cup\{(a,b)\}$.
What is the expected number of steps until $R_k$ is a total order?
The ideal answer would give an explicit (and feasible) way to compute it, but just the asymptotic behavior would be interesting to know.
This answer is partial -- it's what I get from Obinna's ideas up until the point where I cannot follow his reasoning anymore. (Parts of it are wrong; I'm leaving them here as examples of something that doesn't work).
We can reformulate the problem as:
This reformulation corresponds to excluding edges that are in the transitive closure lazily when our random choice hits them, instead of before each choice. At each time the next question actually asked always still ends up being chosen uniformly among the questions it makes sense to ask at any given step, so the reformulation doesn't change the possible question sequences or their probability.
By additivity of expectations, the expected number of questions asks is simply the sum over all possible edges of the probability that this edge becomes a question during a run of the algorithm.
For the edge $(i,j)$, whether it becomes a question depends on which edges $(a,b)$ with $i\le a < b \le j$ have been considered before $(i,j)$. Edges with ends before $i$ or after $j$ don't matter, and one sees that the probability depends only on the distance between $i$ and $j$.
Let $f(k)$ be the probability that,
in random graph on the vertices $\{1,2,3,\ldots k\}$ where each possible edge appears with probability $1/2$, there's no strictly increasing path from $1$ to $k$ containing at least $2$ edges.The probability that edge $(i,j)$ becomes a question is then $f(j-i+1)$,
because every other edge is equally likely to be considered before $(i,j)$ or after it(whoops, no. The probability of each edge being in the graph is $1/2$, but the edges are not independent). And the answer we're looking for is $$\sum_{1\le i<j\le n} f(j-i+1) = \sum_{k=2}^n (n-k+1)f(k) $$Obinna's answer appears to conclude (using an analogy I can't follow) that $f(k)=2/k$.
However, that can't be right, because there are $2^{k(k-1)/2}$ equally probable random graphs being considered in the above definition of $f(k)$, so $f(k)$ is surely some multiple of $2^{-k(k-1)/2}$. And that can't possibly be $2/k$ when $k$ is not a power of $2$.I can't find an expression for $f(k)$, though.
(I have a dynamic programming algorithm to compute $f(2)$ up to $f(k)$ in $O(k^2)$ time, but it's not immediately enlightening).