Re: [math-fun] Statistics for a class of random solids
Wait — you mean that isn't the actual origin of the name "Box-Muller" ? —Dan ----- Note that the probability density function on R^2 where each coordinate is independently uniform [0, 1] is shaped like a box. As such, it seems reasonable to refer to the shape of the probability density function of a bivariate standard Gaussian as a 'muller', so that the Box-Muller transform lives up to its name. -----
Where higher dimensional geometry is involved, bear in mind that even a well-designed pseudo-random number generator is only independent to some fixed precision. Once dimension x (user-demanded precision) exceeds this quantity, the randomness becomes compromised: heed the awful warning in G. Marsaglia "Random numbers fall mainly in the planes" https://www.ncbi.nlm.nih.gov/pmc/articles/PMC285899/pdf/pnas00123-0038.pdf This effective precision is invariably omitted from a PRNG specification, and must instead be deduced from a detailed inspection of the algorithm. WFL On 3/10/19, Dan Asimov <dasimov@earthlink.net> wrote:
Wait — you mean that isn't the actual origin of the name "Box-Muller" ?
—Dan
----- Note that the probability density function on R^2 where each coordinate is independently uniform [0, 1] is shaped like a box. As such, it seems reasonable to refer to the shape of the probability density function of a bivariate standard Gaussian as a 'muller', so that the Box-Muller transform lives up to its name. -----
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
This failure of pseudorandom number generators was analyzed decades ago by Don Knuth in his "Art of Computer Programming". That is why I would insist on using a physical random number generator for anything important, and most particularly for encryption. -- Gene On Sunday, March 10, 2019, 3:32:22 PM PDT, Fred Lunnon <fred.lunnon@gmail.com> wrote: Where higher dimensional geometry is involved, bear in mind that even a well-designed pseudo-random number generator is only independent to some fixed precision. Once dimension x (user-demanded precision) exceeds this quantity, the randomness becomes compromised: heed the awful warning in G. Marsaglia "Random numbers fall mainly in the planes" https://www.ncbi.nlm.nih.gov/pmc/articles/PMC285899/pdf/pnas00123-0038.pdf This effective precision is invariably omitted from a PRNG specification, and must instead be deduced from a detailed inspection of the algorithm. WFL
Isn't this mainly a problem with linear congruential generators (especially the low bits of a power-of-two-modulus LCG), rather than all PRNGs? If you want good-quality random numbers, read from /dev/urandom. It's also quite fast -- even on my low-end 8-year-old laptop, it can produce over 10^8 random bytes per second: $ time bash -c 'head -c 500000000 /dev/urandom > /dev/null' real 0m3.901s user 0m0.070s sys 0m3.815s Best wishes, Adam P. Goucher
Sent: Sunday, March 10, 2019 at 10:31 PM From: "Fred Lunnon" <fred.lunnon@gmail.com> To: "Dan Asimov" <dasimov@earthlink.net>, math-fun <math-fun@mailman.xmission.com> Subject: Re: [math-fun] Statistics for a class of random solids
Where higher dimensional geometry is involved, bear in mind that even a well-designed pseudo-random number generator is only independent to some fixed precision. Once dimension x (user-demanded precision) exceeds this quantity, the randomness becomes compromised: heed the awful warning in G. Marsaglia "Random numbers fall mainly in the planes" https://www.ncbi.nlm.nih.gov/pmc/articles/PMC285899/pdf/pnas00123-0038.pdf
This effective precision is invariably omitted from a PRNG specification, and must instead be deduced from a detailed inspection of the algorithm.
WFL
On 3/10/19, Dan Asimov <dasimov@earthlink.net> wrote:
Wait — you mean that isn't the actual origin of the name "Box-Muller" ?
—Dan
----- Note that the probability density function on R^2 where each coordinate is independently uniform [0, 1] is shaped like a box. As such, it seems reasonable to refer to the shape of the probability density function of a bivariate standard Gaussian as a 'muller', so that the Box-Muller transform lives up to its name. -----
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On Sun, Mar 10, 2019 at 5:46 PM Adam P. Goucher <apgoucher@gmx.com> wrote:
Isn't this mainly a problem with linear congruential generators (especially the low bits of a power-of-two-modulus LCG), rather than all PRNGs?
Yes. If you can distinguish dev/urandom from random, that's a publishable attack on a cryptosystem.
If you want good-quality random numbers, read from /dev/urandom. It's also quite fast -- even on my low-end 8-year-old laptop, it can produce over 10^8 random bytes per second:
$ time bash -c 'head -c 500000000 /dev/urandom > /dev/null'
real 0m3.901s user 0m0.070s sys 0m3.815s
Best wishes,
Adam P. Goucher
Sent: Sunday, March 10, 2019 at 10:31 PM From: "Fred Lunnon" <fred.lunnon@gmail.com> To: "Dan Asimov" <dasimov@earthlink.net>, math-fun <math-fun@mailman.xmission.com> Subject: Re: [math-fun] Statistics for a class of random solids
Where higher dimensional geometry is involved, bear in mind that even a well-designed pseudo-random number generator is only independent to some fixed precision. Once dimension x (user-demanded precision) exceeds this quantity, the randomness becomes compromised: heed the awful warning in G. Marsaglia "Random numbers fall mainly in the planes" https://www.ncbi.nlm.nih.gov/pmc/articles/PMC285899/pdf/pnas00123-0038.pdf
This effective precision is invariably omitted from a PRNG specification, and must instead be deduced from a detailed inspection of the algorithm.
WFL
On 3/10/19, Dan Asimov <dasimov@earthlink.net> wrote:
Wait — you mean that isn't the actual origin of the name "Box-Muller" ?
—Dan
----- Note that the probability density function on R^2 where each coordinate is independently uniform [0, 1] is shaped like a box. As such, it seems reasonable to refer to the shape of the probability density function of a bivariate standard Gaussian as a 'muller', so that the Box-Muller transform lives up to its name. -----
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Mike Stay - metaweta@gmail.com http://math.ucr.edu/~mike https://reperiendi.wordpress.com
Agreed, the specific situation raised by Marsaglia involved LCG's; mentioning it was just confusing the point I intended to make here. The "effective precision" problem is instead much more general. To put it at its simplest, if your PRNG (or indeed your QED-based hardware) generates reliably independent n-bit values, and your d-dimensional geometry simulation expects m-bit values, you are in trouble once m d > n . I have yet to encountered PRNG software which clearly states the value guaranteed for n ... WFL On 3/11/19, Mike Stay <metaweta@gmail.com> wrote:
On Sun, Mar 10, 2019 at 5:46 PM Adam P. Goucher <apgoucher@gmx.com> wrote:
Isn't this mainly a problem with linear congruential generators (especially the low bits of a power-of-two-modulus LCG), rather than all PRNGs?
Yes. If you can distinguish dev/urandom from random, that's a publishable attack on a cryptosystem.
If you want good-quality random numbers, read from /dev/urandom. It's also quite fast -- even on my low-end 8-year-old laptop, it can produce over 10^8 random bytes per second:
$ time bash -c 'head -c 500000000 /dev/urandom > /dev/null'
real 0m3.901s user 0m0.070s sys 0m3.815s
Best wishes,
Adam P. Goucher
Sent: Sunday, March 10, 2019 at 10:31 PM From: "Fred Lunnon" <fred.lunnon@gmail.com> To: "Dan Asimov" <dasimov@earthlink.net>, math-fun <math-fun@mailman.xmission.com> Subject: Re: [math-fun] Statistics for a class of random solids
Where higher dimensional geometry is involved, bear in mind that even a well-designed pseudo-random number generator is only independent to some fixed precision. Once dimension x (user-demanded precision) exceeds this quantity, the randomness becomes compromised: heed the awful warning in G. Marsaglia "Random numbers fall mainly in the planes"
https://www.ncbi.nlm.nih.gov/pmc/articles/PMC285899/pdf/pnas00123-0038.pdf
This effective precision is invariably omitted from a PRNG specification, and must instead be deduced from a detailed inspection of the algorithm.
WFL
On 3/10/19, Dan Asimov <dasimov@earthlink.net> wrote:
Wait — you mean that isn't the actual origin of the name "Box-Muller" ?
—Dan
----- Note that the probability density function on R^2 where each coordinate is independently uniform [0, 1] is shaped like a box. As such, it seems reasonable to refer to the shape of the probability density function of a bivariate standard Gaussian as a 'muller', so that the Box-Muller transform lives up to its name. -----
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Mike Stay - metaweta@gmail.com http://math.ucr.edu/~mike https://reperiendi.wordpress.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I would really love it if somebody could set up the Monte Carlo experiment in Mathematica, which I think has all the pieces to make this easy. For a given N, do, say, 1000 trials, where each trial is: 1. Generate N Gaussian-random points in R^3. 2. Take the convex hull (I vaguely recall that Mma has this as a built-in) 3. Count the number of faces. My intuition is that the average number of faces converges to an upper limit, somewhere short of 30. If this is not true then I expect the number will increase very slowly. On Mon, Mar 11, 2019 at 12:51 PM Fred Lunnon <fred.lunnon@gmail.com> wrote:
Agreed, the specific situation raised by Marsaglia involved LCG's; mentioning it was just confusing the point I intended to make here.
The "effective precision" problem is instead much more general. To put it at its simplest, if your PRNG (or indeed your QED-based hardware) generates reliably independent n-bit values, and your d-dimensional geometry simulation expects m-bit values, you are in trouble once m d > n .
I have yet to encountered PRNG software which clearly states the value guaranteed for n ...
WFL
On 3/11/19, Mike Stay <metaweta@gmail.com> wrote:
On Sun, Mar 10, 2019 at 5:46 PM Adam P. Goucher <apgoucher@gmx.com> wrote:
Isn't this mainly a problem with linear congruential generators (especially the low bits of a power-of-two-modulus LCG), rather than all PRNGs?
Yes. If you can distinguish dev/urandom from random, that's a publishable attack on a cryptosystem.
If you want good-quality random numbers, read from /dev/urandom. It's also quite fast -- even on my low-end 8-year-old laptop, it can produce over 10^8 random bytes per second:
$ time bash -c 'head -c 500000000 /dev/urandom > /dev/null'
real 0m3.901s user 0m0.070s sys 0m3.815s
Best wishes,
Adam P. Goucher
Sent: Sunday, March 10, 2019 at 10:31 PM From: "Fred Lunnon" <fred.lunnon@gmail.com> To: "Dan Asimov" <dasimov@earthlink.net>, math-fun <math-fun@mailman.xmission.com> Subject: Re: [math-fun] Statistics for a class of random solids
Where higher dimensional geometry is involved, bear in mind that even a well-designed pseudo-random number generator is only independent to some fixed precision. Once dimension x (user-demanded precision) exceeds this quantity, the randomness becomes compromised: heed the awful warning in G. Marsaglia "Random numbers fall mainly in the planes"
https://www.ncbi.nlm.nih.gov/pmc/articles/PMC285899/pdf/pnas00123-0038.pdf
This effective precision is invariably omitted from a PRNG specification, and must instead be deduced from a detailed inspection of the
algorithm.
WFL
On 3/10/19, Dan Asimov <dasimov@earthlink.net> wrote:
Wait — you mean that isn't the actual origin of the name
"Box-Muller"
?
—Dan
----- Note that the probability density function on R^2 where each coordinate is independently uniform [0, 1] is shaped like a box. As such, it seems reasonable to refer to the shape of the probability density function of a bivariate standard Gaussian as a 'muller', so that the Box-Muller transform lives up to its name. -----
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Mike Stay - metaweta@gmail.com http://math.ucr.edu/~mike https://reperiendi.wordpress.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Yeah this is easy in Mma. normalPt[dim_] := Table[RandomVariate[NormalDistribution[]], {dim}] nPts[n_, dim_] := Table[normalPt[dim], {n}] randomHull[n_, dim_] := ConvexHullMesh[nPts[n, dim]] randomNumFaces[n_, dim_] := MeshCellCount[randomHull[n, dim], dim-1] randomTally[times_, n_, dim_] := Sort[Tally[Table[randomNumFaces[n, dim], {times}]]] So for 1000 random sets of 100 points in 3 dimensions: randomTally[1000, 100, 3] {{22, 1}, {24, 1}, {26, 4}, {28, 18}, {30, 30}, {32, 62}, {34, 104}, {36, 120}, {38, 142}, {40, 124}, {42, 123}, {44, 86}, {46, 74}, {48, 47}, {50, 30}, {52, 23}, {54, 9}, {56, 1}, {62, 1}} So for example 38 faces is the most common, occurring in 142 of the 1000 trials. I'm sure someone here knows how to make this into a Wolfram Demonstration or whatnot, so that you can set some inputs and click a button on a web page to do this yourself with other parameters... --Michael On Mon, Mar 11, 2019 at 1:35 PM Allan Wechsler <acwacw@gmail.com> wrote:
I would really love it if somebody could set up the Monte Carlo experiment in Mathematica, which I think has all the pieces to make this easy. For a given N, do, say, 1000 trials, where each trial is:
1. Generate N Gaussian-random points in R^3. 2. Take the convex hull (I vaguely recall that Mma has this as a built-in) 3. Count the number of faces.
My intuition is that the average number of faces converges to an upper limit, somewhere short of 30. If this is not true then I expect the number will increase very slowly.
On Mon, Mar 11, 2019 at 12:51 PM Fred Lunnon <fred.lunnon@gmail.com> wrote:
Agreed, the specific situation raised by Marsaglia involved LCG's; mentioning it was just confusing the point I intended to make here.
The "effective precision" problem is instead much more general. To put it at its simplest, if your PRNG (or indeed your QED-based hardware) generates reliably independent n-bit values, and your d-dimensional geometry simulation expects m-bit values, you are in trouble once m d > n .
I have yet to encountered PRNG software which clearly states the value guaranteed for n ...
WFL
On 3/11/19, Mike Stay <metaweta@gmail.com> wrote:
On Sun, Mar 10, 2019 at 5:46 PM Adam P. Goucher <apgoucher@gmx.com> wrote:
Isn't this mainly a problem with linear congruential generators (especially the low bits of a power-of-two-modulus LCG), rather than all PRNGs?
Yes. If you can distinguish dev/urandom from random, that's a publishable attack on a cryptosystem.
If you want good-quality random numbers, read from /dev/urandom. It's also quite fast -- even on my low-end 8-year-old laptop, it can produce over 10^8 random bytes per second:
$ time bash -c 'head -c 500000000 /dev/urandom > /dev/null'
real 0m3.901s user 0m0.070s sys 0m3.815s
Best wishes,
Adam P. Goucher
Sent: Sunday, March 10, 2019 at 10:31 PM From: "Fred Lunnon" <fred.lunnon@gmail.com> To: "Dan Asimov" <dasimov@earthlink.net>, math-fun <math-fun@mailman.xmission.com> Subject: Re: [math-fun] Statistics for a class of random solids
Where higher dimensional geometry is involved, bear in mind that even a well-designed pseudo-random number generator is only independent to some fixed precision. Once dimension x (user-demanded precision) exceeds this quantity, the randomness becomes compromised: heed the awful warning in G. Marsaglia "Random numbers fall mainly in the planes"
https://www.ncbi.nlm.nih.gov/pmc/articles/PMC285899/pdf/pnas00123-0038.pdf
This effective precision is invariably omitted from a PRNG specification, and must instead be deduced from a detailed inspection of the
algorithm.
WFL
On 3/10/19, Dan Asimov <dasimov@earthlink.net> wrote:
Wait — you mean that isn't the actual origin of the name
"Box-Muller"
?
—Dan
----- Note that the probability density function on R^2 where each coordinate is independently uniform [0, 1] is shaped like a box. As such, it seems reasonable to refer to the shape of the probability density function of a bivariate standard Gaussian as a 'muller', so that the Box-Muller transform lives up to its name. -----
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Mike Stay - metaweta@gmail.com http://math.ucr.edu/~mike https://reperiendi.wordpress.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush.
Allan, Generating 220,000 sets of 1000 points and finding their convex hulls, the number of faces varied from 36 to 114 with an average of 69.9. The histogram looks like a slightly skewed normal distribution. With 500 points, max 100, min 28 with average 60. Looks more normal. Certainly not enough data to suggest anything positive, but there it is. Steve On Mar 11, 2019, at 1:33 PM, Allan Wechsler <acwacw@gmail.com<mailto:acwacw@gmail.com>> wrote: I would really love it if somebody could set up the Monte Carlo experiment in Mathematica, which I think has all the pieces to make this easy. For a given N, do, say, 1000 trials, where each trial is: 1. Generate N Gaussian-random points in R^3. 2. Take the convex hull (I vaguely recall that Mma has this as a built-in) 3. Count the number of faces. My intuition is that the average number of faces converges to an upper limit, somewhere short of 30. If this is not true then I expect the number will increase very slowly. On Mon, Mar 11, 2019 at 12:51 PM Fred Lunnon <fred.lunnon@gmail.com<mailto:fred.lunnon@gmail.com>> wrote: Agreed, the specific situation raised by Marsaglia involved LCG's; mentioning it was just confusing the point I intended to make here. The "effective precision" problem is instead much more general. To put it at its simplest, if your PRNG (or indeed your QED-based hardware) generates reliably independent n-bit values, and your d-dimensional geometry simulation expects m-bit values, you are in trouble once m d > n . I have yet to encountered PRNG software which clearly states the value guaranteed for n ... WFL On 3/11/19, Mike Stay <metaweta@gmail.com<mailto:metaweta@gmail.com>> wrote: On Sun, Mar 10, 2019 at 5:46 PM Adam P. Goucher <apgoucher@gmx.com<mailto:apgoucher@gmx.com>> wrote: Isn't this mainly a problem with linear congruential generators (especially the low bits of a power-of-two-modulus LCG), rather than all PRNGs? Yes. If you can distinguish dev/urandom from random, that's a publishable attack on a cryptosystem. If you want good-quality random numbers, read from /dev/urandom. It's also quite fast -- even on my low-end 8-year-old laptop, it can produce over 10^8 random bytes per second: $ time bash -c 'head -c 500000000 /dev/urandom > /dev/null' real 0m3.901s user 0m0.070s sys 0m3.815s Best wishes, Adam P. Goucher Sent: Sunday, March 10, 2019 at 10:31 PM From: "Fred Lunnon" <fred.lunnon@gmail.com<mailto:fred.lunnon@gmail.com>> To: "Dan Asimov" <dasimov@earthlink.net<mailto:dasimov@earthlink.net>>, math-fun <math-fun@mailman.xmission.com<mailto:math-fun@mailman.xmission.com>> Subject: Re: [math-fun] Statistics for a class of random solids Where higher dimensional geometry is involved, bear in mind that even a well-designed pseudo-random number generator is only independent to some fixed precision. Once dimension x (user-demanded precision) exceeds this quantity, the randomness becomes compromised: heed the awful warning in G. Marsaglia "Random numbers fall mainly in the planes" https://urldefense.proofpoint.com/v2/url?u=https-3A__www.ncbi.nlm.nih.gov_pm... This effective precision is invariably omitted from a PRNG specification, and must instead be deduced from a detailed inspection of the algorithm. WFL On 3/10/19, Dan Asimov <dasimov@earthlink.net> wrote: Wait — you mean that isn't the actual origin of the name "Box-Muller" ? —Dan ----- Note that the probability density function on R^2 where each coordinate is independently uniform [0, 1] is shaped like a box. As such, it seems reasonable to refer to the shape of the probability density function of a bivariate standard Gaussian as a 'muller', so that the Box-Muller transform lives up to its name. ----- _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://urldefense.proofpoint.com/v2/url?u=https-3A__mailman.xmission.com_cg... _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://urldefense.proofpoint.com/v2/url?u=https-3A__mailman.xmission.com_cg... _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://urldefense.proofpoint.com/v2/url?u=https-3A__mailman.xmission.com_cg... -- Mike Stay - metaweta@gmail.com https://urldefense.proofpoint.com/v2/url?u=http-3A__math.ucr.edu_-7Emike&d=D... https://urldefense.proofpoint.com/v2/url?u=https-3A__reperiendi.wordpress.co... _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://urldefense.proofpoint.com/v2/url?u=https-3A__mailman.xmission.com_cg... _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://urldefense.proofpoint.com/v2/url?u=https-3A__mailman.xmission.com_cg... _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com<mailto:math-fun@mailman.xmission.com> https://urldefense.proofpoint.com/v2/url?u=https-3A__mailman.xmission.com_cg...
participants (8)
-
Adam P. Goucher -
Allan Wechsler -
Dan Asimov -
Eugene Salamin -
Fred Lunnon -
Lucas, Stephen K - lucassk -
Michael Kleber -
Mike Stay