Re: Reducing Pseudorandomness
From: Jyrki Lahtonen (lahtonen_at_utu.fi)
Date: 08/23/04
- Next message: Maarten Wiltink: "Re: Reducing Pseudorandomness"
- Previous message: Jamie: "Re: Infinite loop outside code"
- In reply to: Glenn Someone: "Reducing Pseudorandomness"
- Next in thread: Dr Engelbert Buxbaum: "Re: Reducing Pseudorandomness"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: Mon, 23 Aug 2004 10:22:27 +0300
Glenn Someone wrote:
>
> I've come across an interesting problem that I'm not sure how to
> solve. I have a case where I need a pseudorandom number generated.
> Simple enough, use the in-built procedure, right? Well, I'm finding
> really for my application that it is not truely random enough. The
> issue is the probability of appearance of the same number within a
> very short time frame. For example, I might call random(100) and get
> 30 within 2 or 3 calls of one another. For my application this is
> unacceptable.
>
> Statistics I found were very indicative of WHY it's called
> pseudorandom and not random number generation. (based on 1000
> generations of a pseudorandom number from 1 to 1000)
Others have already commented on the fact that RANDOM numbers behave
exactly like this.
>
> (average numbers)
>
> No Queuing : 63% of number range generated.
This sounds very random, indeed. For truly random numbers from 1..N
the chance of any particular number x not having appeared is
(1-(1/N))^N, which is well approximated by 1/e for large N. As
1/e is about 0.37, you should expect 37% of numbers not to have appeared
after N trials. Your test seems to confirm this, so the PRNG you used
passes this randomness test with flying colors!
> 20% queued: 71%
> 40% queued: 78%
> 60% queued: 85%
> 70% queued: 88%
> 80% queued: 90%
> 90% queued: 95%
> 100% queued: 100%
>
> Even to queue values towards the front end of this graph can be
> prohibitive for my application. Am I on the right path, and should
> just accept that I'm not going to see an equal likelihood higher than
> what I'm posting, or is there another way to approach this?
May you could try a simple algebraic gadget called an m-sequence
(or more generally "de Bruijn sequence" <- might work well as a
search engine buzzword)? These are strings of bits with the following
properties:
1) given a parameter n, the length of the string is L=(2^n)-1.
2) the sequence can be generated very efficiently by a device called
a linear shift register, (also very easy to implement) by initializing
the register to contain any seqeunce of n-bits (the all zeros being
excluded), and the sequence won't start repeating itself until after
exactly L bits
3) any string of n bits (save all zeros again) will appear exactly
once within the whole sequence of L bits (wrapped around cyclically
so that the last bit is followed by the first).
You could use this machinery to generated blocks of k (k<n) bits
at a time (run the shift register k rounds at each call) and have
this kind of "controlled randomness":
- consecutive blocks would be more or less independent, but
- after L blocks they would have appeared the same number of times
(save minor "error term" introduced by the prohibition of n
consecutive zeros).
If you absolutely want to prevent repetitions, then you could
generate n bits at a time, not have any repetitions sooner
than necessary, but the consecutive numbers would be otherwise
"pseudorandom" (not at all unpredictable though).
May be not what you want?
Cheers,
Jyrki Lahtonen, Turku, Finland
- Next message: Maarten Wiltink: "Re: Reducing Pseudorandomness"
- Previous message: Jamie: "Re: Infinite loop outside code"
- In reply to: Glenn Someone: "Reducing Pseudorandomness"
- Next in thread: Dr Engelbert Buxbaum: "Re: Reducing Pseudorandomness"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
