Abstract | ||
---|---|---|
We prove a conjecture of Droste and Kuske about the probability that 1 is minimal in a certain random linear ordering of the set of natural numbers. We also prove generalizations, in two directions, of this conjecture : when we use a biased coin in the random process and when we begin the random process with a specified ordering of a finite initial segment of the natural numbers. Our proofs use a connection between the conjecture and a question about the game of gambler's ruin. we exhibit several different approaches (combinatorial, probabilistic, generating function) to the problem, of course ultimately producing equivalent results. |
Year | Venue | Keywords |
---|---|---|
2005 | ELECTRONIC JOURNAL OF COMBINATORICS | linear order,random process,generating function |
DocType | Volume | Issue |
Journal | 12 | 1.0 |
ISSN | Citations | PageRank |
1077-8926 | 1 | 0.37 |
References | Authors | |
1 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Andreas Blass | 1 | 31 | 3.62 |
Gábor Braun | 2 | 4 | 1.09 |