[math-fun] wavelet book, comet holmes, random permutation
Can anyone recommend a good introductory book for Wavelets? I have a technical friend who needs to learn about them. He's not a working mathematician, and is looking for a practical approach. Sines & cosines are ok, but triple summations probably not. ------------ Everyone should go look at Comet Holmes. We don't see a comet this bright very often, and it's conveniently located in the evening sky (at least for those of us in the Northern hemisphere.) It's 2nd or 3rd magnitude, in between Cassiopeia & the Pleiades. In binoculars, it's huge. The tail is hidden behind it for now. Google for a finder chart. ------------- I recently came across an old method for generating a random permutation. (Assuming you have a good source of random numbers.) Begin by writing down the identity permutation -- for (i=0;i<n;i++) perm[i] = i; Then pick pairs of locations and swap the contents. x = random(); y = random(); t = perm[x]; perm[x] = perm[y]; perm[y] = t; This isn't an especially good method, but if you do enough swaps, you'll eventually get a random looking result. The surprise is that you need to do a lot more swaps than you'd guess. In the application I encountered, the parameters are N=256 and the number of swaps is 1024, a bit light. The most evident weakness of the method is that it leaves too many cells of the array untouched, giving too many fixed points in the permutation. In the case at hand, I estimate an excess of roughly .1 extra fixed points beyond the expected 1. Depending on the application details, this might be an acceptable deviation from "random". I was inspired to ask a couple of questions. What else might be wrong with these permutations? Is the cycle structure disturbed in some way? Are there too many swaps or short cycles? Is the longest cycle shorter than it should be? Suppose the random number generator is mediocre: How do defects carry over into the generated permutation? Are they repaired by using more swaps? [If the RNG fails to generate some value at all, it's a fixed point of the permutation.] If the swap generator excludes cases when X=Y, but does a replacement swap (so that the total number of executed swaps is always the same), then the result permutation is always even (or odd). This particular defect is undetectable except by examining the entire permutation (minus one element). Even if the swapper doesn't exclude X=Y cases, the expected count is small, so the frequency of even:odd is likely disturbed. How much? Is any of these possible defects harder to remedy than the excess-fixed-points problem? Does getting e-f-p good enough mean you're covered for other kinds of deviations from randomness? Rich
On 11/16/07, Schroeppel, Richard <rschroe@sandia.gov> wrote:
... I recently came across an old method for generating a random permutation. (Assuming you have a good source of random numbers.) Begin by writing down the identity permutation --
for (i=0;i<n;i++) perm[i] = i;
Then pick pairs of locations and swap the contents.
x = random(); y = random(); t = perm[x]; perm[x] = perm[y]; perm[y] = t;
This isn't an especially good method, but if you do enough swaps, you'll eventually get a random looking result. The surprise is that you need to do a lot more swaps than you'd guess. In the application I encountered, the parameters are N=256 and the number of swaps is 1024, a bit light. The most evident weakness of the method is that it leaves too many cells of the array untouched, giving too many fixed points in the permutation. In the case at hand, I estimate an excess of roughly .1 extra fixed points beyond the expected 1. Depending on the application details, this might be an acceptable deviation from "random". I was inspired to ask a couple of questions.
You weren't by any chance poking around in Nijenhuis & Wilf, were you? They give such a method. It reminds me that I always found this book peculiarly disappointing. Wilf was quite well-known at the time; yet a single page (any page!) of Knuth contains more insight into Algorithmics (to coin a phrase) than this entire volume.
What else might be wrong with these permutations? Is the cycle structure disturbed in some way? Are there too many swaps or short cycles? Is the longest cycle shorter than it should be? Suppose the random number generator is mediocre: How do defects carry over into the generated permutation? Are they repaired by using more swaps? [If the RNG fails to generate some value at all, it's a fixed point of the permutation.] If the swap generator excludes cases when X=Y, but does a replacement swap (so that the total number of executed swaps is always the same), then the result permutation is always even (or odd). This particular defect is undetectable except by examining the entire permutation (minus one element). Even if the swapper doesn't exclude X=Y cases, the expected count is small, so the frequency of even:odd is likely disturbed. How much? Is any of these possible defects harder to remedy than the excess-fixed-points problem? Does getting e-f-p good enough mean you're covered for other kinds of deviations from randomness? ...
I've nothing sensible to say, having never thought about the problem, let alone realised how weak this algorithm is. But it begs the question --- what is a good random permutation generator? The only reference a web search turned up was Akl & Meier (1984), which I can't access from home. Does anybody know what's in it? Fred Lunnon
On 11/17/07, Fred lunnon <fred.lunnon@gmail.com> wrote:
... But it begs the question --- what is a good random permutation generator? The only reference a web search turned up was Akl & Meier (1984), which I can't access from home. Does anybody know what's in it?
Brain in gear now. Generate a random integer x in the interval [0, n!-1], and express x as a mixed-radix number to the sequence of bases n,n-1,...,i,...,1 [for larger n, maybe generate directly n integers in range [0, i] for each i]. There is now a simple correspondence with the x-th permutation in alphabetic order. WFL
WFL said:
Brain in gear now. Generate a random integer x in the interval [0, n!-1], and express x as a mixed-radix number to the sequence of bases n,n-1,...,i,...,1 [for larger n, maybe generate directly n integers in range [0, i] for each i]. There is now a simple correspondence with the x-th permutation in alphabetic order. WFL
I think the canonical implementation of this idea is to start with the identity permutation a_i=i, and then for each i=1...n swap a_i with some random a_j for i<=j<=n. That makes it really easy to see that you can get each of the n! permutations in exactly one way. --Michael Kleber -- It is very dark and after 2000. If you continue you are likely to be eaten by a bleen.
On 11/17/07, Michael Kleber <michael.kleber@gmail.com> wrote:
WFL said:
Brain in gear now. Generate a random integer x in the interval [0, n!-1], and express x as a mixed-radix number to the sequence of bases n,n-1,...,i,...,1 [for larger n, maybe generate directly n integers in range [0, i] for each i]. There is now a simple correspondence with the x-th permutation in alphabetic order. WFL
I think the canonical implementation of this idea is to start with the identity permutation a_i=i, and then for each i=1...n swap a_i with some random a_j for i<=j<=n. That makes it really easy to see that you can get each of the n! permutations in exactly one way.
--Michael Kleber
That's a neater way to do things --- ties in nicely with Richard's excavation too! And what a pity I didn't read Nijenhuis & Wilf more carefully --- it turns out this is actually the method they (correctly) gave in 1975. [Carefully wipes egg from face.] Apart from economising on random number generations --- say by extracting [log k / log n] iterations from each integer random in [0, k-1] --- it's hard to see how this might be improved upon. So what can Akl & Meier (1984) be about, I wonder? WFL
As far as random permutation generation by transpositions there is a large literature on this, starting with results of. Diaconis and Aldous. Here's a result of Matthews about it: P. Matthews. A strong uniform time for random transpositions. Journal of Theoretical Probability, vol. 1(4), 1988 Victor On 11/16/07, Schroeppel, Richard <rschroe@sandia.gov> wrote:
Can anyone recommend a good introductory book for Wavelets? I have a technical friend who needs to learn about them. He's not a working mathematician, and is looking for a practical approach. Sines & cosines are ok, but triple summations probably not. ------------
Everyone should go look at Comet Holmes. We don't see a comet this bright very often, and it's conveniently located in the evening sky (at least for those of us in the Northern hemisphere.) It's 2nd or 3rd magnitude, in between Cassiopeia & the Pleiades. In binoculars, it's huge. The tail is hidden behind it for now. Google for a finder chart.
-------------
I recently came across an old method for generating a random permutation. (Assuming you have a good source of random numbers.) Begin by writing down the identity permutation --
for (i=0;i<n;i++) perm[i] = i;
Then pick pairs of locations and swap the contents.
x = random(); y = random(); t = perm[x]; perm[x] = perm[y]; perm[y] = t;
This isn't an especially good method, but if you do enough swaps, you'll eventually get a random looking result. The surprise is that you need to do a lot more swaps than you'd guess. In the application I encountered, the parameters are N=256 and the number of swaps is 1024, a bit light. The most evident weakness of the method is that it leaves too many cells of the array untouched, giving too many fixed points in the permutation. In the case at hand, I estimate an excess of roughly .1 extra fixed points beyond the expected 1. Depending on the application details, this might be an acceptable deviation from "random". I was inspired to ask a couple of questions.
What else might be wrong with these permutations? Is the cycle structure disturbed in some way? Are there too many swaps or short cycles? Is the longest cycle shorter than it should be? Suppose the random number generator is mediocre: How do defects carry over into the generated permutation? Are they repaired by using more swaps? [If the RNG fails to generate some value at all, it's a fixed point of the permutation.] If the swap generator excludes cases when X=Y, but does a replacement swap (so that the total number of executed swaps is always the same), then the result permutation is always even (or odd). This particular defect is undetectable except by examining the entire permutation (minus one element). Even if the swapper doesn't exclude X=Y cases, the expected count is small, so the frequency of even:odd is likely disturbed. How much? Is any of these possible defects harder to remedy than the excess-fixed-points problem? Does getting e-f-p good enough mean you're covered for other kinds of deviations from randomness?
Rich
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (4)
-
Fred lunnon -
Michael Kleber -
Schroeppel, Richard -
victor miller