What's "connected"? Everything in one big cycle? --Rich ________________________________________ From: math-fun-bounces@mailman.xmission.com [math-fun-bounces@mailman.xmission.com] On Behalf Of Joerg Arndt [arndt@jjj.de] Sent: Wednesday, February 17, 2010 6:01 AM To: math-fun Subject: Re: [math-fun] reference for a simple algorithm * Allan Wechsler <acwacw@gmail.com> [Feb 17. 2010 08:49]:
[...]
Obviously it works fine when the spaces being sampled are finite.
My application for this is to generate (uniformly random) connected permutations. For large n only approx n!/n of all permutations are _not_ connected (and the test for connectedness is fast), so the resulting algorithm is very good in practice, cf. http://www.jjj.de/pub/ (thesis-draft, sect. 8.2)
When the spaces are infinite, however, there needs to be a something-or-other -- a measure? a sigma-algebra? -- in order for it to be well-defined to sample the larger space. Furthermore, the measure of the small space in the big space has to be biggish to make the algorithm efficient. (You don't want to have to sample the big space a trillion times to get one hit in the small space.)
Efficiency in my finite universe: -------------------- The method is efficient if 1) generating a random object x ∈ V is fast, 2) the test whether x ∈ U is fast, and 3) |V|/|U| (the expected number of iterations) is not too large. -------------------- (let's see whether the UTF-8 chars for \in appear on the list)
The thing that is really bothering me, though, is the fear that although the small space might be a subset of the big one, the natural measures on the two might disagree, so that evenly-distributed samples of the big space might map into unevenly-distributed samples of the small. Perhaps somebody can convince me that this failure mode never occurs in practice. Or perhaps somebody can tell me that I've gone wrong much earlier in my thinking.
[...]
I'd be surprised if uniformity could fail in U. However, being clueless in these matters, I'd only be a bit be surprised. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun