×

The nearest neighbor random walk on subspaces of a vector space and rate of convergence. (English) Zbl 0818.60061

Summary: Let \(X\) be the collection of \(k\)-dimensional subspaces of an \(n\)- dimensional vector space \(V_ n\) over \(GF(q)\). A metric may be defined on \(X\) by letting \(d(W_ k, V_ k) = k - \dim (W_ k \cap V_ k)\) for \(W_ k\), \(V_ k \in X\). The nearest neighbor random walk on \(X\) starts at an initial fixed point \(Z_ k\) of \(X\) and, from wherever it finds itself, moves with the same probability to any of the points of \(X\) at distance one from it. We analyze the rate of convergence of the nearest neighbor random walk on \(X\) to its stationary distribution. The argument involves lifting the process on \(X\) to a random walk on \(GL_ n (GF(q))\) and using the Fourier transform and \(q\)-Hahn polynomials.

MSC:

60G50 Sums of independent random variables; random walks
Full Text: DOI

References:

[1] Aldous, D., and Diaconis, P. (1986). Shuffling Cards and Stopping Time.Amer. Math. Monthly 93 (5), 333–348. · Zbl 0603.60006 · doi:10.2307/2323590
[2] Aldous, D., and Diaconis, P. (1987). Strong Uniform Times and Finite Random Walks,Adv. in App. Math. 8, 69–97. · Zbl 0631.60065 · doi:10.1016/0196-8858(87)90006-6
[3] Andrews, G. (1976),The Theory of Partitions, Addison-Wesley. · Zbl 0371.10001
[4] Belsley, E. (1992). Rates of Convergence of Markov Chains on Homogeneous Spaces, preprint, Mathematics Department, Harvard University, Cambridge, Massachusetts.
[5] Broder, A. (1989). Generating Random Spanning Trees,30th Ann. Symp. on Foundations of computer Science, IEEE Computer Society Press, Washington, D.C.
[6] Bhattacharya, R., and Waymire, E. (1990).Stochastic Processes with Applications, John Wiley and Sons. · Zbl 0744.60032
[7] Calabi, E., and Wilf, H. (1977). On the Sequential and Random Selection of Subspaces over a Finite Field,J. Combi. Th. (A),22, 107–109. · Zbl 0354.05003 · doi:10.1016/0097-3165(77)90069-3
[8] Diaconis, P. (1988). Group Representations in Probability and Statistics,IMS Lecture Series, Vol. 11, Institute of Mathematical Statistics, Hayward, California. · Zbl 0695.60012
[9] Diaconis, P., and Shahshahani, M. (1987). Time to Reach Stationarity in the Bernoulli-Laplace Diffusion Model,Siam J. Math. Anal. 18, 208–218. · Zbl 0617.60009 · doi:10.1137/0518016
[10] Diaconis, P., and Saloff-Coste, L. (1992). Comparison Theorems for Random Walk on Finite Groups, Technical Report 388, Statistics Department, Stanford University, Stanford, California. · Zbl 0790.60011
[11] Dunkl, C. (1977). An Additional Theorem for Someq-Hahn Polynomials,Mh. Math. 85, 5–37. · doi:10.1007/BF01300958
[12] Goldman, J., and Rota, G. C. (1969). The Number of Subspaces of a Vector Space, in W. J. Tuttle, (ed.),Recent Progress in Combinatorics, Academic Press, pp. 75–83. · Zbl 0196.02801
[13] Greenhalgh, A. (1988). Random Walks on Groups with Subgroup Invariance Properties, Ph.D. Dissertation, Department of Mathematics, Stanford University, Stanford, California. · Zbl 0657.92008
[14] Segre, B. (1967). Introduction to Galois Geometries,Atti. Accad. Naz. Lincei Mem. Cl. Sc. Fis. Mat. Natur. 8, 135–236. · Zbl 0194.21503
[15] Stanton, D. (1984). Orthogonal Polynomials and Chevalley Groups, in R. Askey, T. H. Koornwinder and W. Schempp, (eds.),Special Functions: Group Theoretical Aspects and Applications, Reidel, Dordrecht, pp. 87–128. · Zbl 0578.20041
[16] Stong, R. (1992). Choosing a Random Spanning Subtree: A Case Study.J. Theoretical Prob. 4, 753–766. · Zbl 0737.60059 · doi:10.1007/BF01259553
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.