×

Uniform sampling modulo a group of symmetries using Markov chain simulation. (English) Zbl 0814.68077

Friedman, Joel (ed.), Expanding graphs. Proceedings of the DIMACS workshop on expander graphs, May 11-14, 1992, Princeton University, NJ (USA). Providence, RI: American Mathematical Society. DIMACS, Ser. Discrete Math. Theor. Comput. Sci. 10, 37-47 (1993).
Let \(\Sigma\) be a finite alphabet of cardinality \(k\), and let \(G\) be a permutation group on \(\{0, \dots, n - 1\}\). The group \(G\) induces a natural action on \(\Sigma^ n_ g\) as follows: the word \(x = x_ 0x_ 1 \dots x_{n-1}\) is mapped by \(g \in G\) to the word \(x^ g = y_ 0y_ 1 \dots y_{n-1}\) where \(y_ j = x_ i\) if \(i^ g = j\) \((0 \leq i,\;j \leq n - 1)\). The action of \(G\) partitions \(\Sigma^ n\) into a number of orbits, these being equivalence classes of \(\Sigma^ n\) by \(\sim\) where \(x \sim y\) iff there is \(g \in G\) mapping \(x\) to \(y\). The Pólya theory says that the number of orbits of \(\Sigma^ n\) under the action of \(G\) is \(P_ G (k, \dots, k)\) where \(P_ G\) is the cycle index polynomial of \(G\) \[ P_ G(z_ 1, \dots, z_ n) = | G |^{-1} \sum_{g \in G} z_ 1^{c_ 1(g)} \dots z_ n^{c_ n(g)} \] \(c_ i(g)\) denotes the number of cycles in \(g\) of length \(i\). For general groups \(G\) it seems that \(P_ G\) is hard to compute exactly. (Goldberg has shown that evaluating \(P_ G (2, \dots, 2)\) is \(\#P\)-complete problem even when \(G\) is an abelian 2-group.) The paper deals with the problem of whether there is an efficient approximation algorithm for \(P_ G\). The approach used here is to simulate a Markov chain on \(\Sigma^ n\) that converges to a uniform distribution on the orbits. The Markov chain may be rapidly mixing for all \(G\), but positive results are limited to some simple cases. The programme outlined in the paper may be a difficult one because it includes the mixing rate for Swendsen-Wang process as a special case.
For the entire collection see [Zbl 0777.00033].
Reviewer: M.Demlová (Praha)

MSC:

68Q25 Analysis of algorithms and problem complexity
60G50 Sums of independent random variables; random walks
60J20 Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.)
20B40 Computational methods (permutation groups) (MSC2010)
PDFBibTeX XMLCite