A new random number generator from permutation groups

We describe a new random number generator, RPGM, which is based on the cryptographic system PGM invented by Magliveras in 1976 and subsequently studied by Magliveras and Surkan [10]. PGM relies on a certain method of machine representation for permutation groups. This method allows for encryption and decryption algorithms based on a space-efficient data structure which is called a logarithmic signature for the group. The efficacy of RPGM is studied by means of an extensive analysis of generated data of 100,000 numbers using the Mathieu groupM ₂₄ in its 5-transitive representation on 24 points.     

Spectrum and entropy of C-systems MIXMAX random number generator

The uniformly hyperbolic Anosov C-systems defined on a torus have very strong instability of their trajectories, as strong as it can be in principle. These systems have exponential instability of all their trajectories and as such have mixing of all orders, nonzero Kolmogorov entropy and a countable set of everywhere dense periodic trajectories. In this paper we are studying the properties of their spectrum and of the entropy. For a two-parameter family of C-system operators A(N, s), parameterised by the integers N and s, we found the universal limiting form of the spectrum, the dependence of entropy on N and the period of its trajectories on a rational sublattice. One can deduce from this result that the entropy and the periods are sharply increasing with N. We present a new three-parameter family of C-operators A(N, s, m) and analyse the dependence of its spectrum and of the entropy on the parameter m. We are developing our earlier suggestion to use these tuneable Anosov C-systems for multipurpose Monte-Carlo simulations. The MIXMAX family of random number generators based on Anosov C-systems provide high quality statistical properties, thanks to their large entropy, have the best combination of speed, reasonable size of the state, tuneable parameters and availability for implementing the parallelisation.     

A novel dynamic model of pseudo random number generator

An interesting hierarchy of random number generators is introduced in this paper based on the review of random numbers characteristics and chaotic functions theory. The main objective of this paper is to produce an ergodic dynamical system which can be implemented in random number generators. In order to check the efficacy of pseudo random number generators based on this map, we have carried out certain statistical tests on a series of numbers obtained from the introduced hierarchy. The results of the tests were promising, as the hierarchy passed the tests satisfactorily, and offers a great capability to be employed in a pseudo random number generator.     

Combined random number generator via the generalized Chinese remainder theorem

The combined random number (RN) generator has been considered by many scholars as a good RN generator. One promising type of combined RN generator, recommended by L'Ecuyer (Oper. Res. 44 (1996) 816; 47 (1999) 159), is the combined multiple recursive generator (MRG). This paper analyzes the combined MRG via the Chinese remainder theorem. A new combined generator based on the generalized Chinese remainder theorem and on the Ore algorithm (Amer. Math. Monthly 59 (1952) 365) is presented. The proposed combined generator improves the combined MRG in terms of both the suitability for various types of RN generators and the restriction on the moduli of the individual generators. Therefore, the proposed combined generator is an ideal RN generator and is most recommended.     

A multiple recursive non-linear congruential pseudo random number generator

On-linear multiple recursive congruential pseudo random number generator with prime modulus p is introduced. Let x, n0, be the sequence generated by a usual linear (r+1)-step recursive congruential generator with prime modulus p and denote by N(n), n0, the sequence of non-negative integers with x_N(n)0 (mod p). The non-linear generator is defined by z_nx_N(n)+1·x _N(n) ^–1 (mod p), n0, where x _N(n) ^–1 denotes the inverse element of x_N(n) in the Galois field GF(p). A condition is given which ensures that the generated sequence is purely periodic with period length p^r and all (p–1)^r r-tupels (y₁,...,y_r) with 1y₁,...,y_rp are generated once per period when r-tupels of consecutive numbers of the generated sequence are formed. For r=1 this generator coincides with the generator introduced by Eichenauer and Lehn [2].     

The additive congruential random number generator—A special case of a multiple recursive generator

This paper considers an approach to generating uniformly distributed pseudo-random numbers which works well in serial applications but which also appears particularly well-suited for application on parallel processing systems. Additive Congruential Random Number (ACORN) generators are straightforward to implement for arbitrarily large order and modulus; if implemented using integer arithmetic, it becomes possible to generate identical sequences on any machine.     

Asymptotic number of isometric generalized Fibonacci cubes

For a binary word f, let Q_d(f) be the subgraph of the d-dimensional cube Q_d induced on the set of all words that do not contain f as a factor. Let G_n be the set of words f of length n that are good in the sense that Q_d(f) is isometric in Q_d for all d. It is proved that lim_n→∞|G_n|/2ⁿ exists. Estimates show that the limit is close to 0.08, that is, about eight percent of all words are good.     

The golden number and Fibonacci sequences in the design of voting structures

Some distinguished types of voters, as vetoes, passers or nulls, as well as some others, play a significant role in voting systems because they are either the most powerful or the least powerful voters in the game independently of the measure used to evaluate power. In this paper we are concerned with the design of voting systems with at least one type of these extreme voters and with few types of equivalent voters. With this purpose in mind we enumerate these special classes of games and find out that its number always follows a Fibonacci sequence with smooth polynomial variations. As a consequence we find several families of games with the same asymptotic exponential behavior except for a multiplicative factor which is the golden number or its square. From a more general point of view, our studies are related with the design of voting structures with a predetermined importance ranking.     

The chromatic number of random graphs

For a fixed probabilityp, 0<p<1, almost every random graphG _n,p has chromatic number $$\left( {\frac{1}{2} + o(1)} \right)\log (1/(1 - p))\frac{n}{{\log n}}$$ ,     

The chromatic number of random graphs

Let χ(G(n, p)) denote the chromatic number of the random graphG(n, p). We prove that there exists a constantd ₀ such that fornp(n)>d ₀,p(n)→0, the probability that $$\frac{{np}}{{2 log np}}\left( {1 + \frac{{\log log np - 1}}{{\log np}}} \right)< \chi (G(n,p))< \frac{{np}}{{2 log np}}\left( {1 + \frac{{30 \log \log np}}{{\log np}}} \right)$$ tends to 1 asn→∞.     

The concentration of the chromatic number of random graphs

We prove that for every constant >0 the chromatic number of the random graphG(n, p) withp=n ^–1/2– is asymptotically almost surely concentrated in two consecutive values. This implies that for any <1/2 and any integer valued functionr(n)O(n ) there exists a functionp(n) such that the chromatic number ofG(n,p(n)) is preciselyr(n) asymptotically almost surely.Research supported in part by a USA Israeli BSF grant and by a grant from the Israel Science Foundation.Research supported in part by a Charles Clore Fellowship.     

The choice number of random bipartite graphs

A random bipartite graphG(n, n, p) is obtained by taking two disjoint subsets of verticesA andB of cardinalityn each, and by connecting each pair of verticesaA andbB by an edge randomly and independently with probabilityp=p(n). We show that the choice number ofG(n, n, p) is, almost surely, (1+o(1))log₂(np) for all values of the edge probabilityp=p(n), where theo(1) term tends to 0 asnp tends to infinity.Research supported in part by a USA-Israeli BSF grant, a grant from the Israel Science Foundation, a Sloan Foundation grant No. 96-6-2 and a State of New Jersey grant.Research supported by an IAS/DIMACS Postdoctoral Fellowship.     

The number of possibilities for random dating

Let G be a regular graph and H a subgraph on the same vertex set. We give surprisingly compact formulas for the number of copies of H one expects to find in a random subgraph of G.     

The expected node-independence number of random trees

We shall derive a formula for the expected value μ(n) of the node-independence number of a random tree with n labelled nodes and we shall determine the asymptotic behaviour of μ(n) as n tends to infinity.     

Fibonacci lengths involving the wall number k(n)

Two infinite classes of special finite groups considered (The groupG is special, ifG’ andZ(G) coincide). Using certain sequences of numbers we give explicit formulas for the Fibonacci lenghts of these classes which involve the well-known Wall numbers k(n).     

An elementary proof that random Fibonacci sequences grow exponentially

We consider random Fibonacci sequences given by xn+1=±βxn+xn−1. Viswanath [Divakar Viswanath, Random Fibonacci sequences and the number 1.13198824…, Math. Comp. 69 (231) (2000) 1131-1155, MR MR1654010 (2000j:15040)] following Furstenberg [Harry Furstenberg, Noncommuting random products, Trans. Amer. Math. Soc. 108 (1963) 377-428, MR MR0163345 (29 #648)] showed that when β=1, limn→∞|xn|^1/n=1.13…, but his proof involves the use of floating point computer calculations. We give a completely elementary proof that 1.23375?(E(|xn|))^1/n?1.12095 where E(|xn|) is the expected value for the absolute value of the nth term in a random Fibonacci sequence. We compute this expected value using recurrence relations which bound the sum of all possible nth terms for such sequences. In addition, we give upper and lower bounds for the second moment of the |xn|. Finally, we consider the conjecture of Embree and Trefethen [Mark Embree, Lloyd N. Trefethen, Growth and decay of random Fibonacci sequences, R. Soc. Lond. Proc. Ser. A Math. Phys. Eng. Sci. 455 (1987) (1999) 2471-2485, MR MR1807827 (2001i:11098)], derived using computational calculations, that for values of β<0.702585 such sequences decay. We show that as β decreases, the critical value where growth can change to decay is in fact .     

The dominating number of a random cubic graph

We show that if G is a random 3-regular graph on n vertices, then its dominating number, D(G), almost surely satisfies .2636n ≤ D(G) ≤ .3126n. © 1995 John Wiley & Sons, Inc.