Tuyển tập các báo cáo nghiên cứu khoa học trên tạp chí toán học quốc tế đề tài: Random Orders and Gambler’s Ruin. | Random Orders and Gambler s Ruin Andreas Blass Mathematics Department University of Michigan Ann Arbor MI 48109-1109 . ablass@ Gabor Braun 1 Alfred Renyi Institute of Mathematics Hungarian Academy of Sciences Budapest Realtanoda 13-15 1053 Hungary braung@ Submitted Aug 23 2004 Accepted Apr 20 2005 Published May 13 2005 2000 Mathematics Subject Classifications Primary 05A15 Secondary 05A19 60C05 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. 1 Introduction Droste and Kuske 4 have studied several random processes for producing a linear ordering A on the set N of positive integers. In contrast to random graphs 2 and similar structures random orders cannot be produced by deciding independently about each of the relations a A b for all pairs a b because the transitivity of the ordering imposes dependencies between these relations. Droste and Kuske consider processes that make decisions about the relations a A b one after another the decision about any particular pair a b being made at random provided it is not already determined by previous decisions about other pairs. To specify such a process one must specify the order in which the various pairs a b are to be considered several such specifications are considered in 4 . Partially supported by NSF grant DMS-0070723. Part of this paper was written during a visit of the first author to the Centre de Recerca .
