Random doubly stochastic tridiagonal matrices. Issue 4 (3rd August 2012)

• Record Type: Journal Article
• Authors: Diaconis, Persi; Wood, Philip Matchett
• Is Part Of: Random structures & algorithms. Volume 42:Issue 4(2013)
• Page Start: 403
• Page End: 437
• Publication Date: 2012-08-03
• Subjects: Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20452
• Languages: English
• ISSNs: 1042-9832

Abstract

<abstract abstract-type="main" xml:lang="en"> <title>Abstract</title> <p>Let <tex-math notation="LaTeX"><![CDATA[\documentclass{article}\usepackage{mathrsfs}\usepackage{amsmath, amssymb}\pagestyle{empty}\begin{document}\begin{align*}{\mathcal T}\end{align*} \end{document}]]></tex-math><inline-graphic xlink:href="ark:/27927/pgg20q1b039" mimetype="image" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><italic>n</italic> be the compact convex set of tridiagonal doubly stochastic matrices. These arise naturally in probability problems as birth and death chains with a uniform stationary distribution. We study 'typical' matrices <italic>T</italic>∈ <tex-math notation="LaTeX"><![CDATA[\documentclass{article}\usepackage{mathrsfs}\usepackage{amsmath, amssymb}\pagestyle{empty}\begin{document}\begin{align*}{\mathcal T}\end{align*} \end{document}]]></tex-math><inline-graphic xlink:href="ark:/27927/pgg20q1b02r" mimetype="image" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><italic>n</italic> chosen uniformly at random in the set <tex-math notation="LaTeX"><![CDATA[\documentclass{article}\usepackage{mathrsfs}\usepackage{amsmath, amssymb}\pagestyle{empty}\begin{document}\begin{align*}{\mathcal T}\end{align*} \end{document}]]></tex-math><inline-graphic xlink:href="ark:/27927/pgg20q1b0hx" mimetype="image" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><italic>n</italic>. A simple algorithm is presented to allow direct sampling from the uniform distribution on <tex-math notation="LaTeX"><![CDATA[\documentclass{article}\usepackage{mathrsfs}\usepackage{amsmath, amssymb}\pagestyle{empty}\begin{document}\begin{align*}{\mathcal T}\end{align*} \end{document}]]></tex-math><inline-graphic xlink:href="ark:/27927/pgg20q1b0gc" mimetype="image" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><italic>n</italic>. Using this algorithm, the elements above the diagonal in <italic>T</italic> are shown to form a Markov chain. For large <italic>n</italic>, the limiting Markov chain is reversible and explicitly diagonalizable with transformed Jacobi polynomials as eigenfunctions. These results are used to study the limiting behavior of such typical birth and death chains, including their eigenvalues and mixing times. The results on a uniform random tridiagonal doubly stochastic matrices are related to the distribution of alternating permutations chosen uniformly at random.© 2012 Wiley Periodicals, Inc. Random Struct. Alg., 42, 403–437, 2013</p> </abstract>