Constructing uniformly random permutation by coin flippings

Question

Let $R \subseteq \{1 \dots n\}^2$ be a variable of strict partial order on $n$ elements. Initially, $R_0 := \emptyset$. The goal is to gradually and randomly enlarge R, so that R end up being a uniformly random strict total order (or equivalently, a uniformly random permutation).

This question came up during the design of a sorting algorithm, and I'm not experienced on either order theory, or graphs, or probabilities. I'm wondering whether there's already an established result on this, and if not, whether the following procedure works.

1. At the $i$-th round, deterministically select some $x,y \in \{1 \dots n\}$ such that $\left(x,y\right) \not\in R_i^*$ and $\left(y,x\right) \not\in R_i^*$ (so that adding $\left(x,y\right)$ to $R_i$ is neither useless nor contradictory), where "some" formally means the Hilbert choice function (so that the exact choice is unknown but supposedly irrelevant)
2. Let $R_{i+1} := R_i \cup t$ where $t$ is randomly chosen between $(x,y)$ and $(y,x)$ with $50\%$ probability.
3. If $R_{i+1}^*$ is complete strict order, then let $R := R_{i+1}$ and stop, otherwise go to step 1.

Answer 1

The given procedure does not work because choosing between $(x,y)$ and $(y,x)$ with $50\%$ probability each does not necessarily result in a uniform distribution at the end.

For example, take $n=3$; suppose that in the first step, the pair $(1,2)$ was added to $R_1$. In the second step, the pair $\{x,y\} = \{2,3\}$ is chosen.

Among the three permutations where $1$ comes before $2$, two of them - $(1,3,2)$ and $(3,1,2)$ - have $3$ come before $2$ as well. Only one - $(1,2,3)$ - has $2$ come before $3$. So when choosing between $(3,2)$ and $(2,3)$, we should choose $(3,2)$ with $\frac23$ probability, and $(2,3)$ with $\frac13$ probability.

Trying to correct the algorithm with carefully determining the right probability to use seems tricky, and also hard to do with fair coin flips. (It is also impossible to do with a fixed finite number of coin flips, though we can simulate probabilities like $\frac13$ using a variable number of coin flips that is finite with probability $1$.)

---

For an alternative procedure, we can choose a permutation $\sigma$ of $\{1,2,\dots,n\}$ by choosing $n$ uniformly random real numbers $X_1, X_2, \dots, X_n \in [0,1]$, and taking $\sigma$ to be the permutation that orders the real numbers. That is, we want to have $X_{\sigma(1)} < X_{\sigma(2)} < \dots < X_{\sigma(n)}$.

If we actually had the real numbers $X_1, X_2, \dots, X_n$ to look at, we could do this with any sorting algorithm. Unfortunately, you can't pick a random real number by flipping a coin. So instead we do the following:

1. Leave $X_1, X_2, \dots, X_n$ undetermined to begin with. Start your favorite sorting algorithm on $X_1, X_2, \dots, X_n$.
2. When the sorting algorithm needs to compare $X_i$ to $X_j$, flip the coin to generate random binary digits for $X_i$ and $X_j$ until the comparison becomes clear. (For example, if we know that $X_i$ begins $0.1101\dots$ and $X_j$ begins $0.1100\dots$, then we conclude $X_i > X_j$.)
3. Remember the bits generated for each $X_i$ and use them in later comparisons. (Sometimes the base $2$ expansions will need to get expanded later.)