<p>Regarding question A, it is possible to adapt the PRNG to yield uniformly distributed numbers using <a href="http://en.wikipedia.org/wiki/Leftover_hash_lemma" rel="nofollow">this</a>. However, the range of this new uniform generator has size smaller than $K$, unless the PRNG is itself uniform. The number of possible outcomes of this new generator will depend on the min-entropy of the original generator. </p>

<p>To get some intuition on why this is so, try to view the problem from an adversarial point of view where the goal is to guess the outcome of the PRNG. If $P_{guess}&gt;1/K$ is the probability of the most probable outcome of the PRNG, then there is no deterministic way to lower the adversary's guessing probability without adding randomness. Therefore if you are to transform the outcome to a uniform distribution then all the equaly likely outcomes must happen with probability at least $P_{guess}$, so there can be at most $1/P_{guess}$ outcomes. Of couse, I'm assuming that the adversary knows the deterministic procedure that is applied, as is usually the case in cryptography.</p>

<p>So the answer to question B is that this nesting trick does not increase randomness, it can only decrease it. There is no deterministic procedure that can increase randomness.</p>

<p>Hope this helps</p>

CC BY-SA 3.0
2014-06-30T21:20:18.933Z
Thanks for the answer. I am not sure though about the last paragraph: isn't a PRNG by definition a deterministic procedure which increases randomness?
vnm
CC BY-SA 3.0
2014-07-01T15:50:47.663Z
PRNGs produce numbers that _look_ random but the only true randomness is in the seed. If you know the seed that was used, you can guess all the values that the PRNG will output. So it doesn't increase randomness since guessing the output of the PRNG is at most as hard as guessing the seed.
lamontap
CC BY-SA 3.0
2014-07-19T21:21:26.497Z
I think I used the word 'randomness' but I should have be more precise and rather use "apparent randomness". My question was if the "apparent randomness" of the PRNG can be increased or not using the nesting trick. Or, to put it in another way, if we can produce a better (in some sense) PRNG by using the nesting trick.
vnm
CC BY-SA 3.0
2014-06-26T21:54:16.750Z
2014-06-26T21:54:16.750Z
lamontap
<p>Suppose we have a pseudorandom number generator PRNG with number of possible seed states K. Let us denote PRNG(k) the number yielded by the generator when the seed state is k. Here k is an integer between 1 and K.</p>

<p>Question A: Is it possible to adapt PRNG to yield pseudorandom integer numbers uniformly distributed between 1 and K?</p>

<p>Assuming that the answer to this question is yes, let's denote by PRNG(k; 1, K) the number between 1 and K yielded by the adapted PRNG when the seed state is k.</p>

<p>We can then build a new pseudorandom number generator by nesting PRNG, i.e.</p>

<p>newPRNG(k) = PRNG(PRNG(k; 1, K))</p>

<p>Question B: From a theoretical point of view, can we say something about the properties of the new PRNG? In particular, does this nesting trick increase or decrease the randomness of the generator, in some sense? 
I think this question is a natural one but I didn't find any answer on the web.</p>

CC BY-SA 3.0
2014-06-27T13:25:18.683Z
(Mainly for question B) Are you picturing PRNG working like this? It has an internal state, is initially seeded, then produces a sequence of pseduorandom numbers in $\{1,...,K\}$, producing one such number and updating its state each time it is called.
usul
CC BY-SA 3.0
2014-06-30T21:12:45.337Z
@usul    Actually in my view of PRNG the internal state and the seed coincide. Basically, there exists a function f such that: if the random seed is k and we ask the PRNG for a number then it yields a number f(k) and automatically update the seed to k+1.  If at a later time we ask the PRNG for another number, it yields f(k+1) and update the seed to k+2. When the seed reaches the maximum K it restarts from zero. Is this view too simplistic and naive?
vnm
<randomness><pseudorandom-generators>
nested pseudorandom generator
vnm
# nested pseudorandom generator

(Asked by: username_0 on 2014-06-26)

Suppose we have a pseudorandom number generator PRNG with number of possible seed states K. Let us denote PRNG(k) the number yielded by the generator when the seed state is k. Here k is an integer between 1 and K.

Question A: Is it possible to adapt PRNG to yield pseudorandom integer numbers uniformly distributed between 1 and K?

Assuming that the answer to this question is yes, let's denote by PRNG(k; 1, K) the number between 1 and K yielded by the adapted PRNG when the seed state is k.

We can then build a new pseudorandom number generator by nesting PRNG, i.e.

newPRNG(k) = PRNG(PRNG(k; 1, K))

Question B: From a theoretical point of view, can we say something about the properties of the new PRNG? In particular, does this nesting trick increase or decrease the randomness of the generator, in some sense?
I think this question is a natural one but I didn't find any answer on the web.

**Tags:** randomness, pseudorandom-generators

> **Comments:**
> **username_1**: (Mainly for question B) Are you picturing PRNG working like this? It has an internal state, is initially seeded, then produces a sequence of pseduorandom numbers in $\{1,...,K\}$, producing one such number and updating its state each time it is called.  
> **username_0**: @username_1    Actually in my view of PRNG the internal state and the seed coincide. Basically, there exists a function f such that: if the random seed is k and we ask the PRNG for a number then it yields a number f(k) and automatically update the seed to k+1.  If at a later time we ask the PRNG for another number, it yields f(k+1) and update the seed to k+2. When the seed reaches the maximum K it restarts from zero. Is this view too simplistic and naive?  

---

## 1 answers

### Answer by username_2 on 2014-06-26. Score: 1

Regarding question A, it is possible to adapt the PRNG to yield uniformly distributed numbers using [this](http://en.wikipedia.org/wiki/Leftover_hash_lemma). However, the range of this new uniform generator has size smaller than $K$, unless the PRNG is itself uniform. The number of possible outcomes of this new generator will depend on the min-entropy of the original generator.

To get some intuition on why this is so, try to view the problem from an adversarial point of view where the goal is to guess the outcome of the PRNG. If $P\_{guess}>1/K$ is the probability of the most probable outcome of the PRNG, then there is no deterministic way to lower the adversary's guessing probability without adding randomness. Therefore if you are to transform the outcome to a uniform distribution then all the equaly likely outcomes must happen with probability at least $P\_{guess}$, so there can be at most $1/P\_{guess}$ outcomes. Of couse, I'm assuming that the adversary knows the deterministic procedure that is applied, as is usually the case in cryptography.

So the answer to question B is that this nesting trick does not increase randomness, it can only decrease it. There is no deterministic procedure that can increase randomness.

Hope this helps

> **Comments:**
> **username_0**: Thanks for the answer. I am not sure though about the last paragraph: isn't a PRNG by definition a deterministic procedure which increases randomness?  
> **username_2**: PRNGs produce numbers that _look_ random but the only true randomness is in the seed. If you know the seed that was used, you can guess all the values that the PRNG will output. So it doesn't increase randomness since guessing the output of the PRNG is at most as hard as guessing the seed.  
> **username_0**: I think I used the word 'randomness' but I should have be more precise and rather use "apparent randomness". My question was if the "apparent randomness" of the PRNG can be increased or not using the nesting trick. Or, to put it in another way, if we can produce a better (in some sense) PRNG by using the nesting trick.  

---

