2005 RISP International Workshop on Nonlinear
Circuit and Signal Processing (NCSP'05)
Hawaii, USA, Mar. 4-6, 2005.

Run Test of Pseudo-Random Numbers Generated by Chaotic Maps
Yuki Nakaaji, Shuichi Aono and Yoshifumi Nishio
Deapartment of Electrical and Electronic Engineering,
Tokushima University
2-1 Minami-Josanjima, Tokushima 770-8506, Japan
TEL: +81-88-656-7470, FAX: +81-88-656-7471
Email: {nakaaji, aoichi, nishio}@ee.tokushima-u.ac.jp

1. Introduction

is given as
1 xnPseudo-random numbers are useful for wide-ranging ap(0 ≤ xn ≤ a)aplications [1][2]. However, it is not easy to generate truely xn+1 = fC (xn ) =
 1 xn − a(a < xn ≤ 1).
random numbers. There are several tests to investigate the1−a1−arandomness of limited amount of numbers; the frequency test,(1)
the run test, the random walk test, etc.
The parameter a is usually chosen to be 0.5.
Recently, several researchers have investigated pseudo[Tent Map]
random numbers generated from chaotic systems [3][4].
The tent map is shown in Fig. 2 and the equation of theIn this study, the run test is executed for the pseudo-random
map is given as
numbers generated by some chaotic maps, and the featuresof the run length of the pseudo-random numbers are investi1 xn(0 ≤ xn ≤ a)gated.
axn+1 = fT (xn ) = 1 − 1 xn (a < xn ≤ 1).
1−a 1−a(2)2. Chaotic Maps
The parameter a is usually chosen to be 0.5.
Xn+11We consider the cut map and the tent map as basic chaoticmaps generating pseudo-random numbers.
Xn+110a1Xn

Figure 2: Tent map.
0a1 Xn3. Run Test
Figure 1: Cut map.
The runs within a sequence is one of important statistics ofpseudo-random numbers. A run is a monotonic subsequence;[Cut Map]
Run up is increasing subsequences and Run down is decreasThe cut map is shown in Fig. 1 and the equation of the map ing subsequences. The expected distribution of the number of- 57 -

Pd 1

runs for a truly random sequence is known as follows [1].
2n(d2 + 3d + 1) 2(d3 + 3d2 − d − 4)−(d + 3)!
(d + 3)!

(3)

where rd∗ is the expected number of runs with the length dand n is the length of the total sequence. The expected distribution is compared against the sample distributions using thestandard χ2 formula.
We investigated the distributions of runs in pseudo-random
numbers generated by the cut map and the tent map. Further,for comparison, we also investigated the sequence generated
by random() function in FreeBSD C Library. As a result,the pseudo-random numbers generated by the cut map andthe tent map do not pass the run test, though those from therandom function pass.
In order to investigate the reason why the pseudo-random
numbers generated by the chaotic maps do not pass the runtest, we examin the distributions of the generated runs. Figures 3, 4 and 5 show the probability distribution function of
the runs in the psudo-random numbers generated by the cut
map, the tent map and the random function, respectively.
Pd0.8

Probability

rd∗ =

0.6

0.4

0.2

005

10Run length1520dFigure 5: Distribution of runs (random function).
From the figures, we can see that the probability of length
1 for the cut map is smaller than that for the random function,
while that for the tent map is larger than that for the randomfunction. We consider that these are the special features of
the corresponding chaotic maps.

14. Theoretical Analysis

Probability

0.8

0.6

0.4

0.2

005

10

1520dRun length

Figure 3: Distribution of runs (cut map).
Pd

In this section, we consider the theoretical analysis of theruns in the pseudo-random numbers generated by the chaoticmaps.
The characteristic of the cut map generating runs is symmetric with respect to the center a as shown in Fig. 6.
Namely, a run up with the length 1 is generated from an interval [r1, a], and a run down with the length 1 is genarated
from an interval [a, r10 ]. The values of r1 and r10 can be calculated easily because the map is piecewise linear. Moreover,intervals generating runs with the length 2 are also calculated
as [r2, r1] and [r10 , r20 ]. In the same way, intervals generating runs with the length d can be calculated. Hence, for thecase of a = 0.5, the probability of runs generated by the cutmap can be expressed as1

Pd =Probability

0.8

0.60.40.20051015Run length

Figure 4: Distribution of runs (tent map).

20dµ ¶d1.
2(4)Figure 7 shows the theoretical probability distributionfunction of runs generated by the cut map, which is calculated from Eq. (5). The result in Fig. 7 agree well with theresult in Fig. 3.
The characteristic of the tent map generating runs differsfrom the cut map, namely the tent map is not symmetric withrespect to the center a as shown in Fig. 8. Namely, the lengthof all run down is equal to be 1 and they are generated from aninterval [r10 , 1]. Moreover, after every run up ends, the run
down is generated without fail. Considering this feature, theprobability of runs generated by the tent map with a = 0.5- 58 -can be expressed asXn+1
1P1

Pd

µ ¶2
11+
22..
.
µ ¶d+11=.
2=(5)Figure 9 shows the theoretical probability distributionfunction of runs generated by the tent map, which is calculated from Eq. (6). The result in Fig. 9 agree well with theresult in Fig. 4.
0r3 r2

r1r1’r2’ r3’

a1 Xn

Pd
10.8

Pd

Probability

Figure 6: Generation of runs (cut map).

1

Probability

0.8

0.6

0.4

0.2

0.6

00510Run length

1520d0.4

Figure 9: Theoretical distribution of runs (tent map).

0.2005101520dRun length

Figure 7: Theoretical distribution of runs (cut map).

Xn+11From the above theoretical analysis, we can understandthat the distributions of runs generated by chaotic maps depend on the characteristics of the maps. This is why thepsudo-random numbers generated by chaotic maps do notpass the run test. However, we consider that this is an advantage of chaotic maps as pseudo-random number generators,
because they could produce colored pseudo-random numbers.
5. Further Examples
5.1. Composite Maps

0r3

r2

r1

ar1’

1 Xn

Figure 8: Generation of runs (tent map).

In this section we consider the composite maps of the cutmap as a pseudo-random number generator. Because somerandom functions in computer libraries passing the run test
use the linear congruential method and the method uses a similar function to the composite maps of the cut map.
Figure 10 shows the composite maps of the cut map and theprobability distribution function of runs of pseudo-random
numbers generated by the corresponding composite maps.
We can see that the distribution becomes closer to thatof the random function, as the composite number increases.
Further, we excute the run test for the pseudo-random numbers generated by the composite map. As a result, the- 59 -

pseudo-random numbers generated by the composite maps in different values of a. The theoretical distribution of runs canFigs. 10(a), (b) and (c) do not pass the testm but the pseudo- be calculated as
random number generated by Fig. 10(d) pass the test.
1
1Pd = ad−1 (1 − a) + a(1 − a)d−1(6)
22Pd1

1

Xn+2
0.8

0.6

0.4

Pd0.6
0.6

Xn+1
1

0.5

Probability

Probability

0.8

0.4
0.8

0.20.20.600000.2

0.4

0.6

0.8

51101520dRun lnegth

Xn

0.2
0.4

0Xn

000.2

0.4

0.6

Probability

0.6

0.4

0.8

02

1(a)

0.8

0.8

a=0.9

0.2

Pd 1

1

a=0.8
0.3

0.1

(a)
Xn+3

a=0.5

0.4

46

Run Length

810

d(b)

0.6

Figure 11: (a) Cut map with a = 0.8. (b) Distribution of runs
(cut map with different a).

0.4

0.2

0.2

0000.2

0.4

0.6

0.8

0151015Run length

Xnd20

6. Conclusions(b)
Xn+4

Pd 1

1

In this study, the run of the pseudo-random numbers generated by the chaotic maps was tested, and the reason why thegeneration probability of the length of the run was different
from truly random numbers was clarified theoretically. Further, various characteristics of the runs generated by chaoticmaps were investigated.

0.8

Probability

0.8

0.6

0.4

0.6

0.4

0.2

0.2

00

0
0

0.2

0.4

0.6

0.8

510151Run lengthXnd20

References

(c)
Pd 1

[1] O. Miyatake and K. Wakimoto, “Random Number andMonte Carlo Method,” Morikita Shuppan Co., 1978.

Xn+51

Probability

0.8

0.80.6[2] D.E. Knuth, “Art of Computer Programming, Volume2: Seminumerical Algorithms, 3rd Edition,” AddisonWesley, 1997.

0.6

0.4

0.4

0.2

0.2

00000.2

0.4

0.6

0.8

5Xn110Run length

1520d(d)[3] S. Kawamura, H. Yoshida and M. Mimura, “Characteristics of Pseudo-Random Numbers Generated by
Chaos Nural Networks,” Technical Report of IEICE,
vol. NLP2004-6, pp. 29-34, 2004.

Figure 10: Composite maps and the distribution of runs.
(a) Two times composite. (b) Three times composite. (c) Four [4] M.E. Yalcin, J.A.K. Suykens and J. Vandewalle, “TrueRandom Bit Generation from a Double-Scroll Attractor,”
times composite. (d) Five times composite.
IEEE Trans. on Circuits Syst. I, vol. 51, no. 7, pp. 13951404, 2004.
5.2. Asymmetric Maps
Next, we consider the effect of changing the value of a.
Figure 11(a) shows the map for the case of a = 0.8 andFig. 11(b) shows the probability distribution function of runsof pseudo-random numbers generated by the cut maps with- 60 -