Random orders and gambler's ruin (Q2571263)

\textit{M. Droste} and \textit{D. Kuske} [J. Comb. Theory, Ser. A 102, 241--254 (2003; Zbl 1026.03020)] defined a random linear order in the following recursive way. \(\{1\}\) has its unique ordering. The first \(n-1\) steps, through coin tossings, define a linear order \(\prec\) on \(\{1,2,\dots,n\}\). Step \(n\) tosses a coin to define the linear order between \(n\) and \(n+1\). After this decision, the order of \(n-1\) and \(n+1\) may or may not be determined by transitivity. If not, toss another coin to decide about it, and keep going. All coin tossings are independent and the coins are fair. Droste and Kuske conjectured that probability of finding 1 as the first element under \(\prec\) is \(\prod_{i=1}^{n-1} (2i-1)/(2i)\). The paper solves the problem through three generalizations: (a) the coins have a constant bias, (b) for some \(w\), the procedure starts from the linear order \(1\prec 2\prec \cdots \prec w\), and inserts further elements as above, and (c) the previous two generalizations combined together.