New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

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

Open
msegado opened this Issue Aug 13, 2016 · 8 comments

Comments

Projects
None yet
3 participants
@msegado

msegado commented Aug 13, 2016

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

This comment has been minimized.

Show comment
Hide comment
@dreeves

dreeves Aug 13, 2016

Member

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.

Member

dreeves commented Aug 13, 2016

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

This comment has been minimized.

Show comment
Hide comment
@msegado

msegado Aug 13, 2016

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!

msegado commented Aug 13, 2016

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

This comment has been minimized.

Show comment
Hide comment
@Insti

Insti Aug 14, 2016

Collaborator

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.

Collaborator

Insti commented Aug 14, 2016

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 comment has been minimized.

Show comment
Hide comment
@Insti

Insti Aug 14, 2016

Collaborator

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.

Collaborator

Insti commented Aug 14, 2016

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

This comment has been minimized.

Show comment
Hide comment
@msegado

msegado Aug 14, 2016

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

msegado commented Aug 14, 2016

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

@msegado msegado closed this Aug 14, 2016

@Insti

This comment has been minimized.

Show comment
Hide comment
@Insti

Insti Aug 15, 2016

Collaborator

@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.

Collaborator

Insti commented Aug 15, 2016

@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 Insti changed the title from Ran0 PRNG used in Android app yields correlated pings to Ran0 PRNG used yields correlated pings approx. one in a million times. Aug 15, 2016

@Insti Insti reopened this Aug 15, 2016

@Insti

This comment has been minimized.

Show comment
Hide comment
@Insti

Insti Aug 15, 2016

Collaborator

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

Collaborator

Insti commented Aug 15, 2016

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

@Insti Insti changed the title from Ran0 PRNG used yields correlated pings approx. one in a million times. to Ran0 PRNG used yields correlated pings approximately one in a million times. Aug 15, 2016

@Insti

This comment has been minimized.

Show comment
Hide comment
@Insti

Insti Aug 15, 2016

Collaborator

Added note to readme: #63

Collaborator

Insti commented Aug 15, 2016

Added note to readme: #63

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment