Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Challenge of the week: random numbers
Replies: 2   Last Post: Jun 30, 2014 8:08 PM

 Messages: [ Previous | Next ]
 David Bernier Posts: 3,892 Registered: 12/13/04
Re: Challenge of the week: random numbers
Posted: Jun 30, 2014 8:08 PM

On 06/30/2014 06:37 PM, Herman Rubin wrote:
> On 2014-06-29, Vincent Granville <datashaping@gmail.com> wrote:
>

>> Most random number generators use an algorithm a(k+1) = f(a(k))
> to produce a sequence of integers a(1), a(2), etc. that behaves like
> random numbers. The function f is integer-valued and bounded; because
> of these two conditions, the sequence a(k) eventually becomes periodic
> for k large enough. This is an undesirable property, and many public
> random number generators (those built in Excel, Python, and other
> languages) are poor and not suitable for cryptographic applications,
> Markov Chains Monte-Carlo associated with hierarchical Bayesian models,
> or large-scale Monte-Carlo simulations to detect extreme events (example:
> fraud detection, big data context).
>

>> This challenge involves identifying natural transcendental numbers with
> expansions (series, continued fractions) converging very fast to easily
> produce the decimals of the numbers in question. It starts with Log 10 -
> 2 Log 3 an a series that produces one new digit for each new term.
>

>> In this challenge, you will learn how to build non-periodic,
> high-quality random number generators, test the strength of your random
> number generator, and design generators that are easy to implement, fit
> for big data and extreme events simulation, and run fast. Dr. Vincent
> Granville has promised to participate, so this should add more fun to
> this challenge.
>
> The above condition, combined with the standard mathematical definition
> of a random number, is impossible. If one can compute the number ti a
> specified accuracy in a finite number of steps, one can easily give
> a stopping rule so that the digits at the stopped position are not
> asymptotically uniform. But what does asymptotic tell one about the
> first 10^10 anyhow?
>
> I mistrust all computer genrated sequences as random; von Neumann
> stated that to even think of using systematic numbers as random
> puts one in a state of sin. For SOME purposes of computing integrals
> over the unit k-cell, there are what are called quasi-random numbers,
> which will, at least asymptotically, do better than random numbers
> for sufficiently smooth functions.
>
> What I have suggested is that one take a "good" pseudo-random sequence,
> possibly using some of Mr. Granville's suggestions, as a binary sequence
> and exclusive OR it with a reasonable random sequence. The pseudo-random
> part will guarantee the uniformity and more, and the physical random numbers
> will break up any periodicities of the pseudo-random ones.
>
>

>> Here's the URL:
> http://www.analyticbridge.com/forum/topics/challenge-of-the-week-random-numbers
>
>

mix:
(a) "strong" pseudo-random bit generator (deterministic)
with:
(b) a "high-entropy" source of (what else?) physically generated
"random bits" . (non-deterministic).

via XOR.

--
http://meditationatae.wordpress.com/

Date Subject Author
6/29/14 vincent64@yahoo.com
6/30/14 Herman Rubin
6/30/14 David Bernier