Kac's random walk and coupon collector's process on posets

In the first part of this work, we study a long standing open problem on the mixing time of Kac's random walk on SO(n, R) by random rotations. We obtain an upper bound mix = O (n2.5 log n) for the weak convergence which is close to the trivial lower bound [Omega] (n2). This improves the upper bound O (n4 log n) by Diaconis and SaloffCoste 1131. The proof is a variation on the coupling technique we develop to bound the mixing time for compact Markov chains, which is of independent interest. In the second part, we consider a generalization of the coupon collector's problem in which coupons are allowed to be collected according to a partial order. Along with the discrete process, we also study the Poisson version which admits a tractable parametrization. This allows us to prove convexity of the expected completion time E T with respect to sample probabilities, which has been an open question for the standard coupon collector's problem. Since the exact computation of E - is formidable, we use convexity to establish the upper and the lower bound (these bounds differ by a log factor). We refine these bounds for special classes of posets. For instance, we show the cut-off phenomenon for shallow posets that are closely connected to the classical Dixie Cup problem. We also prove the linear growth of the expectation for posets whose number of chains grows at most exponentially with respect to the maximal length of a chain. Examples of these posets are d-dimensional grids, for which the Poisson process is usually referred as the last passage percolation problem. In addition, the coupon collector's process on a poset can be used to generate a random linear extension.

Department dc:contributor.department

Massachusetts Institute of Technology. Dept. of Mathematics.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2008

Author dc:creator

• Sidenko, Sergiy

Advisor dc:contributor.advisor

• Igor Pak.

• Mathematics.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/43781

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/43781