Unix Shell - Why are the same $RANDOM numbers repeated?

Question

I was experimenting with the $RANDOM variable in a Unix shell and noticed something peculiar. I ran the following command, which reads $RANDOM in a loop 100k times and then pipes the output to "uniq" to find the duplicates.

$ for i in {1..100000}; do echo $RANDOM; done | uniq -d

I ran the command above 7 times, and the same two numbers (4455 and 4117) were repeated all 7 times. The screenshot below shows the command line output.

kali@kali:~% for i in {1..100000}; do echo $RANDOM; done | uniq -d
4455
4117
kali@kali:~% for i in {1..100000}; do echo $RANDOM; done | uniq -d
4455
4117
kali@kali:~% for i in {1..100000}; do echo $RANDOM; done | uniq -d
4455
4117
kali@kali:~% for i in {1..100000}; do echo $RANDOM; done | uniq -d
4455
4117
kali@kali:~% for i in {1..100000}; do echo $RANDOM; done | uniq -d
4455
4117
kali@kali:~% for i in {1..100000}; do echo $RANDOM; done | uniq -d
4455
4117
kali@kali:~% for i in {1..100000}; do echo $RANDOM; done | uniq -d
4455
4117

See: https://i.stack.imgur.com/5bpEe.png

I also opened another terminal window and repeated the process. In the second terminal, the numbers were different, but repeated from in a similar fashion. This makes me wonder about when the entropy of the $RANDOM variable, and how it is seeded.

My guess is that it is re-seeded whenever bash is invoked, but I was wondering if anyone has any info about why the same values are repeated when I repeat the command in a single terminal window.

Answer 1

This is due to a zsh bug / "behaviour" for RANDOM in subshells. This bug doesn't appear in bash.

echo $RANDOM # changes at every run  
echo `echo $RANDOM` # always return the same value until you call the first line

Because RANDOM is seeded by its last value, but in a subshell the value obtained is not updated in the main shell.

In man zshparam:

RANDOM <S>
A  pseudo-random  integer  from 0 to 32767, newly generated each
time this parameter is referenced.  The random number  generator
can be seeded by assigning a numeric value to RANDOM.

The   values   of   RANDOM   form   an  intentionally-repeatable
pseudo-random sequence; subshells  that  reference  RANDOM  will
result  in  identical  pseudo-random  values unless the value of
RANDOM is referenced or seeded in the parent  shell  in  between
subshell invocations.

There is even crazier because calling uniq creates a subshell

for i in {1..10}; do echo $RANDOM; done # changes at every run 
for i in {1..10}; do echo $RANDOM; done | uniq # always the same 10 numbers

Source : Debian bug report 828180

Answer 2

Pseudorandom number generators are not perfect. The Lehmer random number generator is used in bash sources with the "standard" constants:

x(n+1) = 16807 * x(n) mod (2**31 - 1)

moreover bash limits the output to 15 bits only:

#  define BASH_RAND_MAX 32767
...
return ((unsigned int)(rseed & BASH_RAND_MAX));

With the seed your shell has been seeded, it just so happens that numbers 4455 and 4117 appear one after another in consecutive output of 10000 random numbers. Nothing surprising there really. You could calculate the seed to get two consecutive numbers knowing that:

# We know that lower 15 bits of previous number are equal to 4455
x(n) mod 32768 = 4455
# We know that lower 15 bits of previous number are equal to 4455
x(n+1) mod 32768 = 4455
# We know the relation between next and previous number
x(n+1) = 16807 * x(n) mod (2**31 - 1)
# You could find x(n)

Why are the same $RANDOM numbers repeated?

Because the used pseudorandom generator method in bash sources with the current seed in your shell happens to repeat the same number.