This issue tracker has been migrated to GitHub, and is currently read-only.
For more information, see the GitHub FAQs in the Python's Developer Guide.

classification
Title: random.jumpahead and PRNG sequence independence
Type: behavior Stage:
Components: Library (Lib) Versions: Python 2.7
process
Status: closed Resolution: fixed
Dependencies: Superseder:
Assigned To: rhettinger Nosy List: Joseph.Schaeffer, cmcqueen1975, rhettinger
Priority: high Keywords:

Created on 2010-09-10 07:29 by Joseph.Schaeffer, last changed 2022-04-11 14:57 by admin. This issue is now closed.

Files
File name Uploaded Description Edit
random_test.py Joseph.Schaeffer, 2010-09-10 07:29 Test case to find first agreement in PRNG.
Messages (7)
msg115985 - (view) Author: Joseph Schaeffer (Joseph.Schaeffer) Date: 2010-09-10 07:29
Reading the Python 2.6 docs, it appeared that using random.jumpahead would allow the initialization of several generators with the same seed but having much different internal states. While the resulting PRNG appear to have different internal states, the produced random numbers [via .random()] are exactly the same after a small initial segment.

Attached is some example code which shows the first point at which they all agree - in my testing (Mac OS X, Python versions 2.5, 2.6, 2.7) the generated numbers all agreed on the 12th number generated. For smaller differences in jumpahead it was noticeable a lot earlier - n=1,2 differ only in the first sample from each.

The internal state of the PRNGs is indeed different even after the successive sampling, so it may be that this is intended - however if so the docs may cause confusion: my particular case was where I need random numbers for a stochastic markov process and in addition needed many such generators [one for each trajectory] and was hoping to use random.jumpahead to have indepedent PRNG's without having to generate [and prove] my own independent set of seeds. Thus having a long sequence of non-independent random numbers near the initial start condition causes random.jumpahead to be unusable for my situation.

It appears that Python 3.1 removed random.jumpahead - if so, it may be useful to note in the 2.6 docs why this was / the issues with random.jumpahead: reading how it changed after 2.3 made it sound like it was exactly what I wanted. 

Possible cause: I suspect the issue may be related to how a Mersenne Twister algorithm can take a while to recover from poor seeding (excessive 0's), but do not know enough to explore that idea.
msg115990 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2010-09-10 09:41
Thanks for the report.  Something does appear to be broken.  When the states are different, the random numbers should be different.  Am looking in to it.

In the mean time, I recommend against using jumpahead() with MT.  It is better to separately seed three different generators and rely on the huge period of MT to keep the sequences from overlapping.

If you do use jumpahead(), it is intended to be supplied with large values of n (not 1, 11, or 21).

The function/method was removed in 3.x because it was an API defect.  The jumpahead concept as originally intended (move ahead n-steps) was something that could really only work with a generator like Wichmann-Hill.  Newer and more advanced generators aren't usually amenable to direct computation of a state that is n-steps forward.
msg115998 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2010-09-10 10:48
I see the problem now.  Random.jumpahead(n) does a very poor job of shuffling MT's state when n is small.  The first few numbers of the state are different but some of the later ones are not.  When random() crawls across parts of the state that are identical, it produces identical output.  Later when has wrapped around, the random() calls diverge again.

Fixed by salting the jumpahead value.  See r84665.
msg116066 - (view) Author: Joseph Schaeffer (Joseph.Schaeffer) Date: 2010-09-11 00:18
Thanks for looking into it! I'm glad that issue will be fixed, as at least one website was actually recommending using .jumpahead(i) for i in 1..100 for independent seed. 

I suspect in my use case I'll want to continue my previous methods; I work with stochastic Markov processes and I need to seed a large number (10k+) of generators - one per trajectory - and also have the requirement of needing a deterministic PRNG. So having a single Mersenne Twister seed plus salting values that worked with .jumpahead would be a simpler representation; my previous code in C did basically that with a LCG to create those seeding values for the Mersenne Twister. So that's roughly equivalent [I think?] to the fixed random.jumpahead. 

Thanks again!
msg202802 - (view) Author: Craig McQueen (cmcqueen1975) Date: 2013-11-13 23:59
I notice that the C++11 library has a discard() member function for its random generators, which is effectively a jumpahead operation. It seems that the C++11 library has implemented discard() for the Mersene Twister generator. If jumpahead() is technically possible for MT, can it be added back into the Python library?
msg202803 - (view) Author: Craig McQueen (cmcqueen1975) Date: 2013-11-14 00:06
C++11 Mersenne Twister discard() member function:
http://www.cplusplus.com/reference/random/mersenne_twister_engine/discard/
msg202804 - (view) Author: Craig McQueen (cmcqueen1975) Date: 2013-11-14 00:11
StackOverflow question about Mersenne Twister jumpahead:
http://stackoverflow.com/q/4184478/60075

which refers to this:
http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/JUMP/index.html
History
Date User Action Args
2022-04-11 14:57:06adminsetgithub: 54025
2013-11-14 00:11:28cmcqueen1975setmessages: + msg202804
2013-11-14 00:06:47cmcqueen1975setmessages: + msg202803
2013-11-13 23:59:11cmcqueen1975setnosy: + cmcqueen1975
messages: + msg202802
2010-09-11 00:18:45Joseph.Schaeffersetmessages: + msg116066
2010-09-10 10:48:52rhettingersetstatus: open -> closed
resolution: fixed
messages: + msg115998
2010-09-10 09:41:41rhettingersetpriority: low -> high

messages: + msg115990
2010-09-10 08:36:35rhettingersetpriority: normal -> low
assignee: rhettinger
2010-09-10 08:30:25ned.deilysetnosy: + rhettinger

versions: - Python 2.6, Python 2.5
2010-09-10 07:29:29Joseph.Schaeffercreate