Random rotations: Characters and random walks on \(SO(N)\) (Q1323299): Difference between revisions

From MaRDI portal
Importer (talk | contribs)
Created a new Item
 
Import241208061232 (talk | contribs)
Normalize DOI.
 
(3 intermediate revisions by 3 users not shown)
Property / DOI
 
Property / DOI: 10.1214/aop/1176988864 / rank
Normal rank
 
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank
Property / full work available at URL
 
Property / full work available at URL: https://doi.org/10.1214/aop/1176988864 / rank
 
Normal rank
Property / OpenAlex ID
 
Property / OpenAlex ID: W2011211004 / rank
 
Normal rank
Property / DOI
 
Property / DOI: 10.1214/AOP/1176988864 / rank
 
Normal rank
links / mardi / namelinks / mardi / name
 

Latest revision as of 18:09, 10 December 2024

scientific article
In more languages
Configure
Language Label Description Also known as
English
Random rotations: Characters and random walks on \(SO(N)\)
scientific article

    Statements

    Random rotations: Characters and random walks on \(SO(N)\) (English)
    17 November 1994
    For a positive integer \(N\), let \(S=SO(N)\) denote the infinite, compact group consisting of all real, orthogonal, \(N\times N\) matrices with determinant 1, and let \(\lambda\) be normalized Haar measure on \(S\). The author considers a Markov chain \(\{X_ k\}^ \infty_{k=0}\), with state space \(S\), a transition of which may roughly be described as the random choice of a plane in \({\mathbb{R}}^ N\) followed by a rotation of the unit sphere of \({\mathbb{R}}^ N\) through a fixed angle \(\theta\) in that plane. Let \(Q_ k\) be the distribution of \(X_ k\), which we regard as a Borel measure on \(S\). (It turns out that \(Q_ k\) is the \(k\)-fold convolution of \(Q_ 1\) with itself.) Then the variation distance \(D_ k=\| Q_ k-\lambda\|=\sup_ A| Q_ k(A)-\lambda(A)|\) converges to zero, but may remain close to maximal (i.e. close to 1) for an unexpectedly large number of early \(k\)-values. With Fourier analysis on \(S\) as the principal tool, the paper gives the most information about the case \(\theta=\pi\). In this case, \(D_ k\) commences an exponential decrease to 0 when \(k\) passes the cutoff value \(K_ 0={1\over 4} N \text{ ln } N\). More specifically, there are positive constants \(A\), \(B\), \(C\) such that, whenever \(k=K_ 0-xN\) for some \(x>0\), then \(D_ k\geq 1-Ae^{-8x}-(B\text{ ln } N)/N\); and whenever \(k=K_ 0+xN\), then \(D_ k\leq Ce^{-x/8}\). From an examination of the author's calculations, it appears that, for \(N\) (odd) sufficiently large, we can take \(A=200\), \(B=2175\), \(C=253\). Assuming, for purposes of illustration, that \(N\approx 10^ 6\) is ``sufficiently large'', these inequalities would tell us that the exponential decrease commences after 3.5 million trials or so, that \(D_ k\) reaches .05 after about 72 million trials, but that \(D_ k\geq .95\) for the first 2.3 million trials or so. This large-distance-before-exponential-decrease property is called the Diaconis cutoff phenomenon. It occurs in a surprising number of Markov chains, the first examples coming from card shuffling processes, and the author has provided the first (nontrivial) example with an infinite state space.
    random walk
    Haar measure
    rate of convergence
    cutoff phenomenon
    Weyl character formula
    Diaconis cutoff phenomenon
    card shuffling

    Identifiers