We extend recently developed eigenvalue bounds on mixing rates for reversible Markov chains to nonreversible chains. then apply our results show that the $d$-particle simple exclusion process corresponding clockwise walk discrete circle $\mathbf{Z}_p$ is rapidly when $d$ grows with $p$. The dense case $d = p/2$ arises in a Poisson blockers problem statistical mechanics.

A strong stationary time for a Markov chain $(X_n)$ is stopping $T$ which $X_T$ and independent of $T$. Such times yield sharp bounds on certain measures nonstationarity $X$ at fixed finite $n$. We construct an absorbing dual with absorption $X$. relate our to notion duality used in the study interacting particle systems. For birth death chains, again permits stochastic interpretation eigenvalues transition matrix The approach unifies extends analysis previous constructions provides several...

For a large class of examples arising in statistical physics known as attractive spin systems (e.g., the Ising model), one seeks to sample from probability distribution $\pi$ on an enormously state space, but elementary sampling is ruled out by infeasibility calculating appropriate normalizing constant. The same difficulty arises computer science problems where randomly finite distributive lattice whose precise size cannot be ascertained any reasonable amount time. Markov chain Monte Carlo...

When the random intersection graph G(n, m, p) proposed by Karoński, Scheinerman, and Singer-Cohen [Combin Probab Comput 8 (1999), 131–159] is compared with independent-edge p), evolutions are different under some values of m equivalent others. In particular, when m=nα α>6, total variation distance between variables has limit 0. ©2000 John Wiley & Sons, Inc. Random Struct. Alg., 16, 156–176, 2000

In this paper we exhibit, under suitable conditions, a neat relationship between the Moore--Penrose generalized inverse of sum two matrices and inverses individual terms. We include an application to parallel matrices.

A deck of n cards is shuffled by repeatedly taking off the top m and inserting them in random positions. We give a closed form expression for distribution after any number steps. This used to asymptotics approach stationarity: fixed large, it takes shuffles get close random. The formulae lead new subalgebras group algebra symmetric group.

We investigate the duration of an elimination process for identifying a winner by coin tossing or, equivalently, height random incomplete trie. Applications include election leader in computer network. Using direct probabilistic arguments we obtain exact expressions discrete distribution and moments height. Elementary approximation techniques then yield asymptotics distribution. show that no limiting exists, as asymptotic exhibit periodic fluctuations. In many similar problems associated...

By developing and applying a broad framework for rejection sampling using auxiliary randomness, we provide an extension of the perfect algorithm Fill (1998a) to general chains on quite state spaces, describe how use bounding processes can ease computational burden. Along way, unearth simple connection between coupling from past (CFTP) originated by Propp Wilson (1996) our Fill's algorithm. © 2000 John Wiley & Sons, Inc. Random Struct. Alg., 17: 290–316,

A file of records, each with an associated request probability, is dynamically maintained as a serial list. Successive requests are mutually independent. The list reordered according to the move-to-front (MTF) rule: requested record moved front We derive stationary distribution search cost (=depth item) by embedding in Poisson processes and certain finite-time stochastic ordering results for MTF chain so embedded. connection cache fault probabilities discussed. also establish Schur-concavity...

We study the distribution Q on set Bn of binary search trees over a linearly ordered n records under standard random permutation model. This also arises as stationary for move-to-root (MTR) Markov chain taking values in when successive requests are independent and identically distributed with each record equally likely. identify minimum maximum functional achieving those argue that is crude measure "shape" tree. Q(T) two choices T; uniform Q. In latter case, we obtain limiting normal −ln...

We use coupling into and from the past to sample perfectly in a simple provably fast fashion Vervaat family of perpetuities. The includes Dickman distribution, which arises both number theory analysis Quickselect algorithm (the motivation for our work).

We derive upper and lower bounds on total variation distance to stationarity for the distribution of search cost under move-to-front (MTF) rule self-organizing lists with i.i.d. record requests. These enable us obtain sharp rates convergence several standard examples weights, including Zipf's law geometric as length list becomes large. The bound also shows that a number moves order is uniformly sufficient near-stationarity over all choices weights. Concerning stationary itself, we use...

Total path length, or search cost, for a rooted tree is defined as the sum of all root-to-node distances. Let T n be total length random recursive order . Mahmoud [10] showed that W := ( − E [ ])/ converges almost surely and in L 2 to nondegenerate limiting variable Here we give recurrence relations moments show p each 0 < ∞. We confirm conjecture distribution not normal. also characterized among distributions having zero mean finite variance by distributional identity formula here where...

We explore and relate two notions of monotonicity, stochastic realizable, for a system probability measures on common finite partially ordered set (poset) $\mathscr{S}$ when the are indexed by another poset $\mathscr{A}$. give counterexamples to show that not always equivalent, but various large classes we also present conditions $\mathscr{A}$ necessary sufficient equivalence. When $\mathscr{A} = \mathscr{S}$ , condition cover graph have no cycles is This case arises in comparing...

Abstract The limiting distribution of the normalized number comparisons used by Quicksort to sort an array n numbers is known be unique fixed point with zero mean a certain distributional transformation S . We study convergence sequence distributions obtained iterating , beginning (nearly) arbitrary starting distribution. demonstrate geometrically fast for various metrics and discuss some implications numerical calculations Finally, we give companion lower bounds which show that not faster...