Ran0 PRNG used yields correlated pings approximately one in a million times.

[msegado]

I tried to use the Android version of TagTime some time ago but noticed more clustering than expected in the ping times [EDIT: nope, my expectation of randomness is just bad. The ran0 PRNG seems to be fine for this application]. This is probably caused by the use of "ran0" as a PRNG (https://github.com/dreeves/TagTime/blob/master/src/and/tagTime/src/main/java/bsoule/tagtime/PingService.java#L236)... "ran0" is known to yield multiple small numbers in a row, which leads to clusters of closely spaced pings.

One way to fix is to use "ran1" instead, which contains a shuffling step and should yield ping intervals with less sequential correlation.

[dreeves]

Can you point me to the randomness test that ran0 fails? I'm certain the mean ping time is right but am less confident about higher moments.

[msegado]

It looks like section 7-1 (page ~279) of Numerical Recipes in C has some explanation on the serial correlation issues with ran0; if you don't have a copy accessible you can try to use the free archived version they provide online: http://numerical.recipes/oldverswitcher.html (...not sure if that's actually functional though since I'm writing from my phone and the online versions doesn't work on this device)

The short summary is that small numbers are likely to be followed by more small numbers unless a scrambling step is used.

Hope that helps!

[Insti]

One time in 10^6, for example, there will be a value < 10^-6 returned (as there should be), but this will always be followed by a value less than about 0.0168

Assuming this is correct. (which I cannot comment on.)

Due to the uniform to exponential conversion, this correlates to longer ping gaps rather than short ones. if there is a ping gap > 13.815 periods, the next one will be > 4.086 periods

Todo: check to see if this has or will happen based on the "universal" tagtime seed

(10^6 is about 85 years of 45 minute pings.)

Edit: math / statement ordering.

[Insti]

This does appear to be true.

(Spoiler warning - avert eyes if you do not want to know the future.)

The first time it will happen under the universal schedule is at ping: 1,403,465
Most recent ping number at time of posting: 106,563 @ 1471207109 = 2016-08-14 20:38:29 +0000

So in about 110 years or so.
I will try to remember to warn my great-grandchildren about the problem.

[msegado]

Mea culpa... sorry for the hassle, both of you. I've edited my initial post to correctly identify the problem as my own poor expected of randomness =P

[Insti]

@msegado thanks for pointing it out, it is a problem with the RNG that will affect us in the future and should be documented. It will affect others with a different seed or ping gap differently.

The proper solution is probably to switch the rng and schedule a switchover date sometime in the next 110 years, so by the time we get there everyone's software has been updated.

[Insti]

Reopening because the RNG correlation problem is still an issue even if it will not be problematic for a while.

[Insti]

Added note to readme: #63