6
$\begingroup$

I'm planning to simulate iid one-dim variates with continuous uniform distribution on a normalized circle (which circumference is $1$ instead of $2\pi$). Namely, a sample consists of $n$ points simultaneously on the circle (so one may call it a random vector) where each point has an "angle" $X_i \in (0,1)$ for $i = 1\sim n$.

The project involves generating $N > 10^9$ samples for each of the following values of $n$: 5,6,7,8,9,10,11 and 100,101,102,103,104,105. The scope might expand depending on the outcomes.

The fundamental quantity of interest to me is the pairwise distance between the points (intrinsic distance along the circular arc).

For various reasons, Matlab is my current choice of platform, which default PRNG is the Mersenne Twister. I've encountered some opinions that Mersenne Twister, although widely used, is bad for statistical purposes unless tweaked very carefully (and that most people are doing it wrong). This is further elaborated in the Appendix.

Main Question:

Are there some good choices of PRNG specifically designed for circular data? I feel uncertain about "wrapping around" the usual $\mathrm{Unif}(0,1)$. It seems to me that the gap might be twice the "typical size" between the smallest number around 0 and the largest around 1.

To be more precise theoretically: the gap between adjacent order statistics of uniform $G_i \equiv U_{(i+1)} - U_{(i)}$ has a Beta distribution that is identical to the min $G_i \overset{d}{=} U_{(1)}$. Meanwhile, the ""wrap-around" gap $G_0 \equiv 1 + U_{(1)} - U_{(n)}$ is identically distributed as $G_0 \overset{d}{=} U_{(2)}$.

As for the aspect of implementation, I'm more than happy to code for combinations of PRNG from different families. Time cost is indeed a concern but not very important. If it's beneficial, I can switching from using Matlab to R.


I have read the article back in 2010 by David Jones and the 2015 paper by Agner Fog, both of which are informative while at the same time a good portion of the content are out of my grasp.

In particular, I'm not sure how or which part of the discussions apply to circular data (or not).

Secondary Question:

If the PRNG is good, can I just generate $N$ samples for a big $n_0$, say, $n_0 = 105$, and then resample (via permutation the ensemble that was "intended" for $n_0$) to obtain data for the smaller $n = 5,6,7,$ etc? Or is this actually not faster or mathematically unsound?

(this seems to have been answered in the comments)

$$\color{white}. \\ \color{white}. \\ \color{white}.$$

Appendix: Possible Issues with Mersenne Twister in Statistics

First there's the words from George Marsaglia (yes, one must cite him in a post about PRNG!)

"(the Mersenne Twister) ... essentially a lagged Fibonacci RNG using the exclusive-or (xor) operation, and experience has shown that lagged Fibonacci generators using xor provide unsatisfactory 'randomness'... and even with very long lags, many people (I among them) are inclined to be cautious about sequences based on such a simple operation as the xor ..."

The above is my excerpt from Marsaglia post in 1999 on Sci.Stat.Math, which is preserved in web.archive.org (please reload a few times if needed).

In the 2015 paper I mentioned above, when commenting about the (then) new version of MT in 2013 (for graphic processors no less), Agner Fog said:

"This generator has known weaknesses, which are common to the Mersenne Twister family: It is vulnerable to tests based on algebra $\mathbb{F}_{_2}$; it has relatively poor diffusion; and it has subsequences with more 0's than 1's."

These issues are echoed in some posts on StackOverflow and comments therein, like here in 2015 or this one in 2017.

The point is not about the security in cryptography but about:

"(the Mersenne twistor as of 2007) ... it fails two Crunch Tests, the linear complexity tests which pure shift-register-type generators like MT are doomed to fail."

This comes from the 2010 article I mentioned above by David Jones. However, what's making me unsure is that Jones said in the same sentence:

"(failing the linear complexity tests) ... unlikely to be an issue in a simulation. It’s hard to imagine any real bioinformatics application failing with this generator."

$\endgroup$
  • 3
    $\begingroup$ I have never heard of difficulties with the Mersenne twister. In any case, the circular nature of the distribution should have no relevance for the choice of the PRNG, since it boils down to simulating from a uniform distribution. As for the second question, this is a correct way of proceeding, but you do not even need to resample. $\endgroup$ – Xi'an Jun 12 '18 at 13:28
  • $\begingroup$ @Xi'an Thanks for your input. (1) I'll edit the post and add some reference to clarify the issues I've read about Mersenne Twister. Of course, your opinion (that there's nothing lacking about MT) also matters a lot to me. (2) Yes, thanks for reminding me that I don't need resampling (that just taking parts in existing sequence is fine). $\endgroup$ – Lee David Chung Lin Jun 12 '18 at 14:26
  • 1
    $\begingroup$ At least one implementation of Mersenne twister has been shown to fail the PractRand suite of tests. Many of the PRNGs in the PCG family (for example the xorshift variant used in golang.org/x/exp/rand) pass PractRand. $\endgroup$ – deasmhumnha Jun 13 '18 at 4:38
  • $\begingroup$ @DezmondGoff oh yes I've just started reading about the PCG generators, and there have been some quite "energetic" discussions. Thanks for chiming in. $\endgroup$ – Lee David Chung Lin Jun 13 '18 at 8:50
  • $\begingroup$ @Xi'an I still have some doubt about how a uniform circular distribution can simply boil down to the usual (linear) uniform. Could you comment on the "wrap-around" gap issue I raised in the edited block of the "Main Question"? Thank you. $\endgroup$ – Lee David Chung Lin Jun 15 '18 at 8:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.