Jean-Marc Luck
email: jean-marc.luck@ipht.fr

Parrondo games as disordered systems

Parrondo's paradox refers to the counter-intuitive situation where a winning strategy results from a suitable combination of losing ones. Simple stochastic games exhibiting this paradox have been introduced around the turn of the millennium. The common setting of these Parrondo games is that two rules, A and B, are played at discrete time steps, following either a periodic pattern or an aperiodic one, be it deterministic or random. These games can be mapped onto 1D random walks. In capitaldependent games, the probabilities of moving right or left depend on the walker's position modulo some integer K. In history-dependent games, each step is correlated with the Q previous ones. In both cases the gain identifies with the velocity of the walker's ballistic motion, which depends non-linearly on model parameters, allowing for the possibility of Parrondo's paradox. Calculating the gain involves products of non-commuting Markov matrices, which are somehow analogous to the transfer matrices used in the physics of 1D disordered systems. Elaborating upon this analogy, we study a paradigmatic Parrondo game of each class in the neutral situation where each rule, when played alone, is fair. The main emphasis of this systematic approach is on the dependence of the gain on the remaining parameters and, above all, on the game, i.e., the rule pattern, be it periodic or aperiodic, deterministic or random. One of the most original sides of this work is the identification of weak-contrast regimes for capital-dependent and history-dependent Parrondo games, and a detailed quantitative investigation of the gain in the latter scaling regimes.

Introduction

Parrondo's paradox refers to the counter-intuitive situation where a winning strategy results from a suitable combination of losing ones. Simple stochastic games exhibiting this paradox have been introduced by Parrondo and collaborators around the turn of the millennium [1][2][3][START_REF] Harmer | Proc. R. Soc. Lond. A[END_REF][START_REF] Parrondo | [END_REF]. References [6][7][8][9] provide comprehensive reviews of early developments of Parrondo games, including historical aspects and extensive discussions of their paradoxical nature. Parrondo games were originally devised as discrete analogues of Brownian ratchets. The latter ratchets are extensions of Feynman's celebrated thermal ratchet [START_REF] Feynman | Feynman Lectures on Physics[END_REF] to the microscopic scale, aimed at modeling the force-free motion of molecular motors [START_REF] Ajdari | [END_REF][12][13]. Flashing Brownian ratchets consist of a point particle undergoing Brownian diffusion on the line under the effect of a periodic potential which is both spatially asymmetric and periodically modulated in time. The interplay of these two properties breaks detailed balance. Under generic circumstances, it yields a rectification of thermal noise and induces a steady ballistic motion of the particle (see [14,15] for reviews).

Parrondo games belong to the realm of Markovian games of chance. The usual setting is that two stochastic rules, denoted as A and B, are played at discrete time steps in a specific order, following a periodic pattern such as ABBABB . . . or an aperiodic one, either deterministic or random. It is advantageous to describe Parrondo games within the framework of a random walker occupy-ing the sites of an infinite 1D lattice and moving to neighboring sites at discrete time steps according to the above stochastic rules. The discrete position n t of the walker at integer time t identifies with the capital of the player. In the generic situation where the walker's motion is ballistic, its velocity yields the gain G of the player per time step:

G = lim t→∞ n t t . (1)
Parrondo's paradox holds whenever the chosen game (rule pattern) yields a positive gain, whereas each rule, when played alone, either is fair or has a negative gain:

Parrondo's paradox: {G > 0, G A ≤ 0, G B ≤ 0} . ( 2
)
There are two main classes of Parrondo games. The first class is referred to as capital-dependent games. The rules, either A or B or both, depend explicitly on the walker's position (i.e., the player's capital) n t mod K, where K is some fixed integer 1 . The game originally proposed by Parrondo [1][2][3][START_REF] Harmer | Proc. R. Soc. Lond. A[END_REF] corresponds to K = 3. Parrondo's paradox also holds for some specific models with K = 2, where Rule B depends on the parity of the player's capital [16,17]. A second class of Parrondo games, referred to as history-dependent games [START_REF] Parrondo | [END_REF]18,19], has also been considered, even though it has not become as popular as capital-dependent games. There, the complexity of the dynamics originates in a memory effect between successive steps. The probability for the walker to move right or left is now independent of its position n t , but it depends on the Q previous steps, in a way that is different for Rules A and B. Parrondo's paradox already holds in some cases for Q = 1, and more generally for Q = 2 [16].

Consider for the time being a random walker on an infinite 1D lattice, with time-dependent probabilities of moving to neighboring sites. Let p t (resp. q t = 1 -p t ) be the probability that the walker moves to the right (resp. to the left) at time t. The mean position of the walker at time t reads

n t = n 0 + t s=1
(2p s -1).

(

) 3
This expression only depends on the sum of the probability differences p s -q s = 2p s -1, and not on the order in which single steps are performed. In other words, elementary steps commute with each other. In the case of an annealed disorder, where the time-dependent probabilities p t are themselves drawn from some distribution, the velocity of the walker is self-averaging and reads

G = 2p -1. (4)
The notations for averages used throughout this paper follow the usual conventions of the theory of disordered systems. Brackets, . . . , denote an average over realizations of the Markov process, i.e., over histories of the random walker, whereas a bar, . . . , denotes an annealed average over the distribution of the probabilities defining the Markov process, whenever the latter are themselves random.

In the case of Parrondo games, the existence of internal degrees of freedom (the walker's position n mod K for capital-dependent games, or the Q previous steps for history-dependent games) makes the corresponding random walk non-trivial. The gain G, i.e., the walker's velocity, depends non-linearly on model parameters, allowing for the possibility of Parrondo's paradox, defined by the inequalities (2). Parrondo games can be viewed as inhomogeneous Markov chains [6][7][8], whose study involves products of non-commuting Markov matrices acting on a finite-dimensional linear space with dimension

d = K or d = 2 Q , (5)
encoding internal degrees of freedom. These products of Markov matrices are somehow temporal analogues of the spatial products of non-commuting transfer matrices that are ubiquitous in investigations of 1D disordered systems (see [START_REF] Bougerol | Products of Random Matrices, with Applications to Schrödinger Operators[END_REF][START_REF] Crisanti | Products of Random Matrices in Statistical Physics[END_REF][START_REF] Luck | Systèmes désordonnés unidimensionnels[END_REF][START_REF] Pendry | [END_REF][24][START_REF] Comtet | Stochastic Processes and Random Matrices[END_REF] for reviews).

The goal of the present work is to elaborate on this analogy and to study Parrondo games by means of various analytical techniques freely inspired by the theory of 1D disordered systems. This line of thought allows us to deal with capital-dependent and history-dependent games on the same footing, and yields a wealth of new results on both classes of Parrondo games. We consider capitaldependent games in Sections 2 and 3 and history-dependent games in Sections 4 and 5. We choose for definiteness to work with one paradigmatic example of each class. Most of the time, we focus our attention onto the neutral situation where each rule, when played alone, is fair (G A = G B = 0). The main emphasis of this systematic approach is on the dependence of the gain G on the remaining free parameters and, more importantly, on the game, i.e., the rule pattern, be it periodic or aperiodic, deterministic or random. One of the most original sides of this work is the identification of a weak-contrast scaling regime and its systematic investigation for both classes of games (Sections 3 and 5). Section 6 contains a brief overview.

2 Capital-dependent games

Generalities

The game originally proposed by Parrondo [1][2][3][START_REF] Harmer | Proc. R. Soc. Lond. A[END_REF] is a prototypical example of a capital-dependent game with K = 3, where rules depend on the player's capital (i.e., of the walker's position) mod 3. It is sufficient to monitor the dynamics of the walker in the three-dimensional internal space parametrized by its position n mod 3 = 0, 1, 2. Within this framework, the most general Markovian stochastic rule is depicted in Figure 1 and corresponds to the Markov matrix

M = 0 q 1 p 2 p 0 0 q 2 q 0 p 1 0 , (6)
with the notation q n = 1 -p n . 0 1 2

p 0 q 0 p 1 p 2 q 2 q 1
Fig. 1. Most general Markovian stochastic rule of the capitaldependent Parrondo game in the internal space of the player's capital (i.e., of the walker's position) n mod 3 = 0, 1, 2, with the notation qn = 1 -pn.

The standard body of knowledge on Markov chains can be found in the classical references [START_REF] Doob | Stochastic Processes[END_REF][START_REF] Feller | An Introduction to Probability Theory and its Applications[END_REF][START_REF] Karlin | A First Course in Stochastic Processes[END_REF][START_REF] Van Kampen | Stochastic Processes in Physics and Chemistry[END_REF][START_REF] Kelly | Reversibility and Stochastic Networks[END_REF][START_REF] Stirzaker | Stochastic Processes and Models[END_REF]. Hereafter we not pretend at any mathematical rigor. We shall only need the following general result: the unique ergodicity of a discrete-time Markov chain, i.e., essentially the uniqueness of its stationary state, is ensured by the fact that the corresponding Markov matrix M has a simple (i.e., nondegenerate) unit eigenvalue, while all other eigenvalues are strictly less than unity in modulus.

We introduce the time-dependent state vector

φ t = X t Y t Z t , (7)
where X t , Y t and Z t are the probabilities that the walker's position n mod 3 at time t is respectively 0, 1 and 2.

Parrondo's historical game consists of a combination of the following rules [1][2][3][START_REF] Harmer | Proc. R. Soc. Lond. A[END_REF].

• Rule A. The three probabilities are equal:

p 0 = p 1 = p 2 = p. If Rule A is played at time t, we have φ t = M A φ t-1 , (8)
with

M A = 0 q p p 0 q q p 0 . ( 9
)
If Rule A is played alone, the walker executes a uniformly biased random walk. Its stationary state φ A , such that

φ A = M A φ A , (10)
is uniform:

φ A = φ uni = 1 3 1 1 1 . ( 11
)
We have

G A = J A • φ A , (12)
where the current vector reads

J A = (2p -1) ( 1 1 1 ) , (13)
and so

G A = 2p -1. (14)
• Rule B. It is defined by setting p 2 = p 1 , keeping p 0 and p 1 as free parameters. If Rule B is played at time t, we have

φ t = M B φ t-1 , (15)
with

M B = 0 q 1 p 1 p 0 0 q 1 q 0 p 1 0 . ( 16
)
If Rule B is played alone, the stationary state of the system is described by the normalized eigenvector φ B associated with the unit eigenvalue of M B , such that

φ B = M B φ B . (17)
We thus obtain

φ B = X B Y B Z B , (18)
with

X B = 1 -p 1 q 1 D , Y B = 1 -q 0 p 1 D , Z B = 1 -p 0 q 1 D (19) and D = 3 -p 0 q 1 -q 0 p 1 -p 1 q 1 . (20)
We have

G B = J B • φ B , (21)
where the current vector reads

J B = ( p 0 -q 0 p 1 -q 1 p 1 -q 1 ) , (22)
and so

G B = 3(p 0 p 2 1 -q 0 q 2 1 ) D . (23)
The Markov matrices M A and M B generically do not commute with each other. We have indeed

[M A , M B ] = (p 1 -p 0 ) 2p -1 0 0 q q p -p -q -p . ( 24
)
The commutator vanishes only for p 1 = p 0 , i.e., when each rule corresponds to a uniformly biased random walk, so that the dynamics in internal space can be forgotten.

Hereafter the main focus will be on the neutral situation where each rule, when played alone, is fair (G A = G B = 0). In this situation, a given game, such as e.g. the periodic game ABBABB . . ., exhibits Parrondo's paradox whenever the corresponding gain, denoted G ABB , is positive (see (2)). The condition that Rule A is fair reads

p = 1 2 , (25)
expressing that the corresponding random walk is unbiased, i.e., symmetric. The condition that Rule B is fair yields a relation between p 0 and p 1 ,

p 0 = (1 -p 1 ) 2 1 -2p 1 (1 -p 1 ) , (26)
leaving one free parameter. It is advantageous to choose the parametrization

p 0 = 1 2 - v 1 + v 2 , p 1 = 1 2 (1 + v), (27)
where the contrast parameter v in the range -1 < v < 1 provides a measure of the difference between both rules. The expression (24) becomes

[M A , M B ] = v(3 + v 2 ) 4(1 + v 2 ) 0 0 0 1 1 1 -1 -1 -1 . ( 28
)
We close this section by a discussion of symmetries.

• Parity, i.e., the change of sign of the walker's position (n ←→ -n), corresponds to changing the orientation of the circle shown in Figure 1. It therefore amounts to exchanging the probabilities as p ←→ q for Rule A, and p 0 ←→ q 0 , p 1 ←→ q 1 for Rule B. In the neutral situation, this amounts to changing v into its opposite (v ←→ -v). The gain G is therefore an odd function of v, irrespective of the game. • Time reversal amounts to the sole reversal of the order of letters for a general game of finite duration, such as

ABABBABBB ←→ BBBABBABA. ( 29
)
The model is indeed simple enough to ensure that each rule is reversible, i.e., coincides with its own timereversed, as soon as it is fair. This is obvious for Rule A.

For Rule B, the expression [START_REF] Pendry | [END_REF] shows that the condition for G B to vanish is p 0 p 2 1 = q 0 q 2 1 . This is nothing but Kolmogorov's criterion for the Markov chain defining Rule B to be reversible (see e.g. [START_REF] Kelly | Reversibility and Stochastic Networks[END_REF][START_REF] Stirzaker | Stochastic Processes and Models[END_REF]). There is indeed only one non-trivial cycle (see Figure 1), and so Kolmogorov's criterion amounts to one single equation. As a consequence of the above, the gain G is left unchanged under a reversal of the game, i.e., of the rule pattern, such as (29).

Random games

The first situation demonstrating Parrondo's paradox is that of an (infinitely long) random game, where at each time step Rule B is chosen with probability ρ and Rule A with the complementary probability 1 -ρ. In the following, we are only interested in the average gain G of this random game, and so it is sufficient to know the average state vector φ. The present problem is therefore easier than the investigation of usual 1D disordered systems, which requires the evaluation of the Lyapunov exponent of a matrix product (see [START_REF] Bougerol | Products of Random Matrices, with Applications to Schrödinger Operators[END_REF][START_REF] Crisanti | Products of Random Matrices in Statistical Physics[END_REF][START_REF] Luck | Systèmes désordonnés unidimensionnels[END_REF][START_REF] Pendry | [END_REF][24][START_REF] Comtet | Stochastic Processes and Random Matrices[END_REF] for reviews). The timedependent average state vector φ t obeys a recursion of the form

φ t = M φ t-1 , (30)
where the average Markov matrix,

M = (1 -ρ)M A + ρM B , (31)
has the same functional form as M B , albeit with effective parameters [7,8]

p 0 = (1 -ρ)p + ρp 0 , p 1 = (1 -ρ)p + ρp 1 . (32)
The average gain G of the random game is obtained by replacing in (23) p 0 and p 1 by the above effective values.

For the uniformly random game (ρ = 1/2), where at each time step Rules A and B are chosen with equal probabilities, we obtain

G = 3((p + p 0 )(p + p 1 ) 2 -(q + q 0 )(q + q 1 ) 2 ) D , (33)
with D = 2(12 -(p + p 0 )(q + q 1 ) -(q + q 0 )(p + p 1 ) -(p + p 1 )(q + q 1 )). (34) The expression (33) allows one to measure how rare is Parrondo's paradox. In the present setting, it is natural to define the probability of observing Parrondo's paradox as the volume of the three-dimensional domain in (p, p 0 , p 1 ) space such that the inequalities (2) hold, with G given by (33). A numerical integration yields Prob(Parrondo's paradox) ≈ 0.000306. (35) This very small number is in perfect agreement with an earlier estimate [START_REF] Crisan | [END_REF].

From now on, until the end of Section 3, we restrict the analysis to capital-dependent Parrondo games in the neutral situation where both rules, when played alone, are fair (G A = G B = 0), Using the parametrization ( 25), [START_REF] Feller | An Introduction to Probability Theory and its Applications[END_REF], we obtain the following expression for the average gain:

G = 6ρ(1 -ρ 2 )v 3 9(1 + v 2 ) + ρ 2 v 2 (v 2 -3) . ( 36
)
The above result exhibits several features of interest. It is an odd function of the contrast parameter v, as expected from the above considerations on parity. The average gain has the sign of v, irrespective of ρ. Parrondo's paradox therefore holds for all v > 0 and all non-trivial probabilities (0 < ρ < 1). There is no discrepancy with the tininess of the probability (35), since we have fixed two of the three model parameters by focussing our attention onto the neutral situation. The average gain vanishes as ρ → 0 and ρ → 1, where random games respectively degenerate to Rule A and Rule B. It reaches its absolute maximum,

G max = 8 √ 2 -5 √ 5 = 0.133368, ( 37
) for ρ = 2 √ 2 - √ 5 = 0.592359 (38)
and v → 1. The latter limit is however singular, as it corresponds to p 0 → 0 and p 1 → 1. In this limit, the Markov matrix M B looses the property of unique ergodicity, as its eigenvalues become 0 and ±1.

In the weak-contrast regime (v → 0), the average gain vanishes cubically. We shall see in Section 3 that this cubic law holds for arbitrary games. We are thus led to introduce the gain amplitude (or amplitude, for short)

g = lim v→0 G v 3 . ( 39
)
For random games, the expression (36) yields

g = 2ρ(1 -ρ 2 ) 3 . ( 40
)
For the uniformly random game (ρ = 1/2), the average amplitude reads

g = 1 4 . ( 41
)
When the probability ρ of choosing Rule B varies between 0 and 1, the amplitude (40) reaches its maximum

g = 4 √ 3 27 = 0.256600 (42) for ρ = √ 3 3 = 0.577350. ( 43
)

Periodic games

In this section we consider periodic games, i.e., periodic rule patterns, defined by the infinite repetition of a unit cell W of length P , like e.g. W = ABB, which has period P = 3. We shall alternatively consider W as a word consisting of P letters, A or B, and introduce the symbols

τ n = A σ n = 0 or τ n = B σ n = 1, (44)
according to whether the nth letter in W is A or B. The stationary state of the game has the same period P as the game itself. It is encoded in P state vectors φ n obeying

φ n = M τn φ n-1 (n = 1, . . . , P ), (45)
with periodic boundary conditions (φ P = φ 0 ). The associated gain reads

G W = 1 P P n=1 J τn • φ n-1 , (46)
where the current vectors J A and J B are evaluated in the neutral situation, with parameters ( 25), [START_REF] Feller | An Introduction to Probability Theory and its Applications[END_REF], i.e.,

J A = 0, J B = - 2v 1 + v 2 v v . (47)
The recursion (45) amounts to a system of 3P linear equations, whose solution may be obtained by means of a computer algebra system such as MACSYMA. The complexity of the expressions of the gain G however grows very rapidly with the period P . We recall that the gain is invariant under cyclic permutations and reversal of the unit cell. Its expressions for all games with periods 2 and 3 are given below.

• P = 2. There is only one non-trivial unit cell with period 2, namely W = AB. The corresponding gain vanishes [19]:

G AB = 0. ( 48
)
This result comes as a surprise, as it is not dictated by any obvious symmetry. • P = 3. There are two inequivalent unit cells with period 3. The corresponding gains read

G AAB = 16v 3 81 + 78v 2 + v 4 , (49)
G ABB = 8v 3 (7 + 10v 2 -v 4 ) 81 + 204v 2 + 118v 4 -20v 6 + v 8 . (50)
The above expressions demonstrate that the gain vanishes cubically in the weak-contrast regime (v → 0), which will be the subject of Section 3. The corresponding amplitudes g AB = 0, g AAB = 16/81 and g ABB = 56/81 (see [START_REF] Albuquerque | [END_REF]) are listed in the first three lines of Table 1.

3 Weak-contrast scaling regime of capital-dependent games

Generalities

In the weak-contrast scaling regime (v → 0), both rules are close to symmetric random walks, so that state vectors are expected to become close to the uniform one, given by [START_REF] Ajdari | [END_REF]. It can indeed be checked, in full generality, that the differences between Y n or Z n and 1/3 are of order v, whereas the difference between X n and 1/3 is of order v 2 , and the resulting gain is of order v 3 .

Hereafter we use the shorthand notation

κ = - 1 2 . ( 51
)
Let us focus for a while our attention onto periodic games, considered in Section 2.3. The matrix recursion (45) between state vectors φ n boils down to two coupled linear recursions for the rescaled co-ordinates

y n = lim v→0 3(Y n -Z n ) v , (52)
x n = lim v→0 1 -3X n v 2 , (53)
namely

y n = κ (y n-1 + 6σ n ) , (54)
x n = κ (x n-1 -σ n y n-1 ) , (55)
with periodic boundary conditions (y P = y 0 , x P = x 0 ). The gain amplitude (see [START_REF] Albuquerque | [END_REF]) reads

g W = lim v→0 G W v 3 = 1 3P P n=1 σ n (3x n-1 + 2). ( 56
)
The recursions (54), (55) are instrumental in the investigation of the weak-contrast regime. Their key property is the occurrence of the uniform damping factor κ, whereas the rule pattern, encoded in the symbol σ n = 0 or 1, according to (44), enters linearly. The above formalism extends to aperiodic games, either deterministic or random (see Section 3.4).

Random games

As a first application of the above formalism, let us revisit random games, already considered in Section 2.2. In (55), σ n and y n-1 are statistically independent, and we have σ n = ρ. The stationary averages y and x therefore obey

y = κ (y + 6ρ) , (57) x = κ (x -ρy) , (58)
hence

y = -2ρ, x = - 2ρ 2 3 , (59)
and

g = ρ 3 (3x + 2) = 2ρ(1 -ρ 2 ) 3 . ( 60
)
The result ( 40) is thus recovered.

Periodic games

We now turn to the case of periodic games, already considered in Section 2.3. The explicit solution to (54), ( 55) with periodic boundary conditions reads

y n = - 3 1 -κ P P -1 m=0 κ m σ n-m , (61)
x n = - 3 2(1 -κ P ) 2 × P -1 l,m=0 κ l+m σ n-m σ n-l-m-1 . (62)
Inserting the latter expression for x n into (56), we obtain after some algebra

g W = 6 P (1 -κ P ) 2 × P k,l,m=1 κ l+m σ k (1 -σ k+l σ k-m ). ( 63
)
In the above, all indices of σ symbols are to be understood mod P . The result (63) provides an explicit expression of the gain of Parrondo's historical game for an arbitrary periodic rule pattern in the weak-contrast regime. The cyclic and reversal invariance of the gain appear manifestly. The extension of the above result to aperiodic games will be considered in Section 3.4.

For the time being we keep the focus onto periodic games. For a given period P , (63) shows that all amplitudes are rational numbers whose denominator divides P (2 P -(-1) P )2 . In the case where the unit cell W consists of only two blocks,

W = A M B N , (64)
with arbitrary integers M , N ≥ 1, so that P = M + N , the expression (63) simplifies to

g A M B N = 4(1 -κ M ) 9P (1 -κ P ) 2 (65) × 3N κ N (1 -κ M ) + 2(1 -κ N )(1 -κ P ) .
When both block lengths M and N become large, the amplitude falls off as

g A M B N ≈ 8 9P , (66)
up to exponentially small corrections. This decay law in 1/P can be interpreted as follows. Both rules A and B are fair, and so only the interfaces between blocks yield some gain. More generally, when one of the block lengths gets large, the other one being kept finite, (65) yields

g A M B N ≈ a M N , a M = 8 9 (1 -κ M ) (67)
for N → ∞ at fixed M , and

g A M B N ≈ b N M , b N = 4 9 (2 + (3N -2)κ N ) (68)
for M → ∞ at fixed N . Both sequences a M and b N converge to 8/9, consistently with (66), with exponentially damped oscillations. The smallest of them are a 2 = 2/3 and b 3 = 1/2, whereas the largest read a 1 = b 2 = 4/3. We now turn to general features of interest exhibited by the gain amplitudes of periodic games. The dependence of g W on the unit cell W defining the periodic game appears to be very intricate in general. The result (65) indeed virtually exhausts all cases where (63) yields manageable closed-form expression.

Table 1 gives the exact rational and numerical expressions of the gain amplitude g W for all periodic games with primitive 2 period P ≤ 6. The explicit result (65) yields 15 of the 20 expressions given there, whereas the remaining five cases need a specific evaluation of the triple sum entering (63). The last column gives the corresponding rotation number ω of the cut-and-project sequence (see Section 3.4.2), when applicable.

For a given -not necessarily primitive -period P , the 2 P possible unit cells W of length P can be enumerated by means of a computer routine, and the associated amplitudes g W evaluated by using (63). The finite-size average amplitude g ave P , obtained as a flat average of the 2 P values of g W thus generated, is shown in Figure 2 against period P ≤ 30. The last point involves 2 30 = 1 073 741 824 different games. The plotted quantity oscillates as a function of the period. These finite-size effects are however exponentially damped, and so g ave P converges very fast to the asymptotic limit 1/4, consistently with (41).

Let us now investigate which game yields the largest Parrondo effect, i.e., the largest gain amplitude. The maximal amplitude g max P among all 2 P periodic games with given period P is shown in Figure 3 against P . For the sake of clarity, the plotted range has been limited to 5 ≤ P ≤ 30. The amplitude of the periodic game with period 5 and unit cell W = ABABB, i.e., (see Table 1), appears as the absolute maximum of the gain amplitudes of all games, irrespective of their periods. Whenever the period P is a multiple of 5, the absolute maximum g max is reached for the game whose unit cell is a repetition of p/5 times W . If P is not a multiple of 5, there are suboptimal periodic games whose gains converge, albeit rather slowly, to (69). We make a digression out of the weak-contrast regime to mention that the periodic game ABABB yields the highest gain for all values of the contrast parameter v. Its gain in the v → 1 limit, i.e.,

g
G max = G max ABABB = 9 25 = 0.36, (70)
is the absolute maximal gain of the model in the neutral situation where each rule, when played alone, is fair (G A = G B = 0). The v → 1 limit is however singular (see below [START_REF]Quasicrystals and Geometry[END_REF]). The universal optimality of the game ABABB was already demonstrated by Dinis [33] by means of an algorithmic approach based upon backward induction.

It is interesting to notice that the values of ρ yielding the maximal gain of random games, given by [START_REF]Quasicrystals and Geometry[END_REF] for v → 1 and (43) for v → 0, are very close to 3/5, characteristic of the optimal periodic game ABABB. The gains achieved by those optimal random games are however far below the truly optimal values, given by (70) for v → 1 and (69) for v → 0.

Aperiodic games

The expression (63) for the gain amplitude extends to any aperiodic game, either deterministic or random. Taking formally the P → ∞ limit, forgetting about boundary conditions, we obtain

g = 2ρ 3 -6 ∞ l,m=1 κ l+m C l,m . (71)
In this expression,

ρ = σ n = lim P →∞ 1 P P n=1 σ n (72)
is the density of letters B, i.e., the fraction of steps where Rule B is chosen, whereas

C l,m = σ n σ n+l σ n-m = lim P →∞ 1 P P n=1 σ n σ n+l σ n-m (73)
are the three-point correlation functions of the distribution of letters B, depending on two distances l and m. The damping factor κ l+m ensures an exponential convergence of (71) for all aperiodic games with well-defined translationally invariant correlations.

Hereafter we consider two examples of aperiodic games in more detail. Games generated by chaotic dynamical systems have already been considered in the past [34].

The following examples are more directly inspired by the physics of 1D systems. The first example (Section 3.4.1) consists of an enrichment of the random games considered in Section 3.2 by the introduction of a memory kernel. The gain amplitude exhibits a smooth dependence on parameters (see Figure 5). The second example (Section 3.4.2) is based on quasiperiodic cut-and-project sequences. The amplitude has an irregular dependence on parameters (see Figure 7).

Random games with Markovian memory

In Sections 2.2 and 3.2 we have considered random games where at each time step the rule is chosen at random, irrespective of past and future. In other words, the symbols σ n introduced in (44) are independent random variables.

The goal of this section is to consider a richer type of random games based on random sequences with Markovian memory, where at each step the rule is chosen with probabilities depending on the rule at the previous step. This setting allows two free parameters, namely the probabilities α and β, such that3

σ n-1 = 0 ⇒ σ n = 0 w. p. 1 -α, 1 w. p. α, σ n-1 = 1 ⇒ σ n = 0 w. p. β, 1 w. p. 1 -β. (74)
In other words the game, i.e., the rule pattern, is generated by an auxiliary Markov chain, whereas each rule, either A or B, itself amounts to a Markov chain -as before. The above setting can be encoded into the Markov matrix

m = 1 -α β α 1 -β . ( 75
)
The stationary state of the auxiliary Markov process is described by the eigenvector r such that r = mr, i.e.,

r = 1 α + β β α . ( 76
)
We have therefore

ρ = α α + β . ( 77
)
The second eigenvalue of the Markov matrix m, characterizing the range of the memory effect, reads

λ = 1 -α -β. (78)
In order to determine correlation functions, an explicit representation of powers of m is required. We have

m k = 1 -α k β k α k 1 -β k , (79)
with α k+1 = α + λα k and β k+1 = β + λβ k , and so

α k = ρ(1 -λ k ), β k = (1 -ρ)(1 -λ k ). ( 80
)
The Markovian property of the sequence defining the random game implies

C l,m = ρ(1 -β l )(1 -β m ). ( 81
)
Inserting this expression into (71), the double sum boils down to geometric series. We are thus left with the explicit result

g = 8ρ(1 -ρ)(1 -λ)((1 -λ)ρ + 2λ + 1) 3(2 + λ) 2 . ( 82
)
The amplitude vanishes as ρ → 0 and ρ → 1, where random games respectively become Rule A and Rule B. The random games considered in Sections 2.2 and 3.2 correspond to an absence of memory, i.e., λ = 0. The result (40) is thus recovered for the third time.

Figure 4 shows the parameter space of random sequences with Markovian memory. Allowed values of density ρ and memory rate λ lie inside the black curve. For λ > 0, where successive symbols are positively correlated, all values of the density ρ can be realized. The gain vanishes linearly as λ → 1, i.e., when the mean block length diverges. For λ < 0, where successive symbols are negacorrelated, only a limited range of densities, i.e.,

- λ 1 -λ ≤ ρ ≤ 1 1 -λ , (83)
can be realized. The upper (resp. lower) bound corresponds to α = 1 (resp. β = 1), where letters A (resp. B) are isolated. In the λ → -1 limit, the range shrinks to the single point ρ = 1/2, where the random game reduces to the periodic game AB.

Figure 5 shows the dependence of the amplitude g on the density ρ of letters B, as given by (82), for several values of the memory rate λ.

For fixed λ, g reaches its maximum

g max = 8 2 √ 3(1 + λ + λ 2 ) 3/2 -9λ(1 + λ) 27(1 -λ)(2 -λ) 2 (84)
for The dependence of this optimal density on λ is shown in Figure 4 as a red curve. The latter leaves the range of allowed densities as it hits the α = 1 boundary for β = 1/2, i.e., λ = -1/2 and ρ = 2/3, where g = 32/81 = 0.395061.

ρ = √ 3(1 + λ + λ 2 ) 1/2 -3λ 3(1 -λ) . (85)
The gain amplitude however reaches a slightly higher absolute maximum,

g max = 2 9 (16 √ 2 -13) 1/3 -7(16 √ 2 -13) -1/3 + 3 = 0.408187, (86)
somewhere further along the α = 1 boundary, i.e., for

λ = (1 + √ 2) -1/3 -(1 + √ 2) 1/3 = -0.596071, (87)
ρ = 1 6 (8 + 6 √ 2) 1/3 -2(8 + 6 √ 2) -1/3 + 2 = 0.626538. ( 88
)
This optimal point is shown as blue square symbols in Figures 4 and5.

Cut-and-project quasiperiodic games

Our second example of aperiodic games is very different in spirit. It is generated by the deterministic quasiperiodic cut-and-project sequences. These sequences, investigated first by de Bruijn [35], are in correspondence with irrational numbers ω. They have been extensively used to build model quasiperiodic structures that are 1D analogues of quasicrystals. In particular, for ω = 1/τ and ω = 1/τ 2 , where τ = (1 + √ 5)/2 = 1.618033 is the golden mean, Fibonacci sequences are obtained, which are germane to the first icosahedral quasicrystals, discovered in 1984 [36] (see [START_REF] Janot | Quasicrystals: A Primer[END_REF][START_REF]Quasicrystals and Geometry[END_REF] for overviews). Since then, much attention has been paid to cut-and-project and other deterministic aperiodic sequences and to various physical models based upon these structures (see [START_REF] Albuquerque | [END_REF]40] for reviews).

The cut-and-project sequence is based on an irrational rotation number in the range 0 < ω < 1. Consider the points obtained by rotating around the unit circle in discrete steps by the angle ω, measured in revolutions, i.e., in units of 2π. The angle reached after n steps reads

x n = Frac(nω), (89)
where Frac(x) = x -Int(x) is the fractional part of a real number x, with Int(x) being its integer part. The binary cut-and-project sequence of symbols σ n is defined by setting

σ n = χ(x n ), (90)
where

χ(x) = 1 (0 ≤ x < ω), 0 (ω ≤ x < 1). ( 91
)
In other words, we have σ n = 1 if the angle x n is in the interval [0, ω[, and σ n = 0 otherwise. We consider the infinitely long Parrondo game defined by choosing Rule A (resp. Rule B) at step n if σ n = 0 (resp. σ n = 1), consistently with (44). For all irrational rotation numbers ω, the sequence x n is uniformly distributed over [0, 1], so that the density of letters B, i.e., the fraction of steps where Rule B is chosen, reads

ρ = ω. ( 92
)
The fluctuations in the letter numbers, measured by the differences

δ n = n m=1 σ m -nω, (93)
belong to the interval -1 ≤ δ n ≤ 0. They are therefore bounded, whereas they would typically grow as √ n for a random sequence.

The correlation function C l,m is given by the length of the set of values of x such that the three numbers x, Frac(x + lω) and Frac(x -mω) all belong to [0, ω]. The construction of this set is sketched in Figure 6, with the notations

s l = max(ω -x l , 0), t l = min(1 -x l , ω), u m = max(ω -1 + x m , 0), v m = min(x m , ω). (94) 0 ω 0 ω s l t l u m v m
Fig. 6. Construction of the set involved in the determination of the three-point correlation function C l,m of the cut-andproject sequence. The latter quantity is the length of the intervals marked by red arrows, defined as the intersection of the blue sets drawn on each axis. Notations are given in (94).

The expression

C l,m = min(u m , s l ) + ω -max(t l , v m ) + max(s l -v m , 0) + max(u m -t l , 0) (95)
synthesizes the six different possible orders between the four points s l , t l , u m and v m (we have always s l < t l and u m < v m ).

Figure 7 shows the gain amplitude g against the rotation number ω of the cut-and-project game, as obtained by inserting the expressions (92) and ( 95) into (71), evaluating individual terms and performing the sum numerically.

The amplitude g appears to be a continuous function of ω, exhibiting cusps at rational values of ω, around which it varies linearly, albeit with two different slopes to the left and to the right. If ω goes to a rational Q/P , assumed irreducible, the corresponding sequence becomes periodic, with period P . Only a very specific subset of periodic sequences is attained in this way. The last column of Table 1 gives the values of ω corresponding to all periodic games thus obtained with primitive periods P ≤ 6. The corresponding data points are shown as blue symbols in Figure 7. The amplitude vanishes only for ω = 0 (Rule A), ω = 1 (Rule B) and ω = 1/2 (periodic game AB). It reaches its maximum (see ( 69)) for ω = 3/5.

The amplitude vanishes linearly in the vicinity of both endpoints (ω → 0 and ω → 1), up to exponentially small deviations. For ω → 0, the smallest distances yielding a 0 0.2 0.4 0.6 0.8 1 ω 0 0.3 0.6 0.9 g Fig. 7. Dependence of the gain amplitude g for the capitaldependent Parrondo game against the rotation number ω defining the cut-and-project sequence. Blue symbols: rational rotation numbers with denominator P ≤ 6 (see Table 1).

non-zero three-point correlation function C l,m are m = l -1 = Int(1/ω). A similar line of reasoning applies to ω → 1 as well. We thus obtain the estimates

g = 2ω 3 + O(2 -2/ω ) (ω → 0), (96)
g = 4(1 -ω) 3 + O(2 -1/(1-ω) ) (ω → 1). ( 97
)
4 History-dependent games

Generalities

We now turn to history-dependent Parrondo games [START_REF] Parrondo | [END_REF]18,19]. In this second class of games, the walker moves either right or left at step t, i.e., its tth step

ε t = n t -n t-1 (98)
is chosen to be either ε t = +1 or ε t = -1, with probabilities which are independent of its position n t , but depend on the Q previous steps, in a way that is different for Rules A and B.

Hereafter we restrict the analysis to the smallest relevant memory range, i.e., Q = 2. It is sufficient to characterize the system by the four-dimensional time-dependent state vector

φ t =    X t Y t Z t T t    , (99)
with

X t = Prob (ε t-1 = +1 and ε t = +1), Y t = Prob (ε t-1 = +1 and ε t = -1), Z t = Prob (ε t-1 = -1 and ε t = +1), T t = Prob (ε t-1 = -1 and ε t = -1). ( 100
)
The mean displacement during the tth step reads

ε t = X t -Y t + Z t -T t = J • φ t , (101)
where the displacement vector reads

J = ( 1 -1 1 -1 ) . ( 102
)
The expression (1) of the gain therefore translates to

G = lim t→∞ 1 t t s=1 J • φ s . ( 103
)
The usual class of history-dependent Parrondo games consists of a combination of the following rules [START_REF] Parrondo | [END_REF]18,19].

• Rule A. This rule coincides with Rule A in capitaldependent games. In the present setting, each step is chosen according to

ε t = +1 w. p. p, -1 w. p. q = 1 -p, (104)
irrespective of the past, where the notation p is consistent with Sections 2 and 3. Therefore, if Rule A is played at time t, we have

φ t = M A φ t-1 , (105)
with

M A =    p 0 p 0 q 0 q 0 0 p 0 p 0 q 0 q    . (106)
If Rule A is played alone, the walker executes a uniformly biased random walk. Its stationary state reads

φ A =    p 2 pq pq q 2    . ( 107
)
We have (see ( 103))

G A = J • φ A , (108)
i.e.,

G A = 2p -1, ( 109
)
consistently with ( 14). • Rule B. This is the most general rule with memory range Q = 2, If Rule B is played at time t, the displacement ε t = ±1 is chosen according to the following stochastic rules, depending on the two previous steps (ε t-2 , ε t-1 ):

(+1, +1) ⇒ ε t = +1 w. p. p 1 , -1 w. p. q 1 , (+1, -1) ⇒ ε t = +1 w. p. p 2 , -1 w. p. q 2 , (-1, +1) ⇒ ε t = +1 w. p. p 3 , -1 w. p. q 3 , (-1, -1) ⇒ ε t = +1 w. p. p 4 , -1 w. p. q 4 , (110)
with the notation q i = 1 -p i . The p i are considered as four free parameters.

We have therefore

φ t = M B φ t-1 , (111)
with

M B =    p 1 0 p 3 0 q 1 0 q 3 0 0 p 2 0 p 4 0 q 2 0 q 4    . ( 112
)
If Rule B is played alone, the stationary state of the system reads

φ B =    X B Y B Z B T B    , (113)
with

X B = p 3 p 4 D , Y B = Z B = q 1 p 4 D , T B = q 1 q 2 D ( 114
)
and

D = q 1 q 2 + 2q 1 p 4 + p 3 p 4 . ( 115
)
We have (see ( 103))

G B = J • φ B , (116)
i.e.,

G B = p 3 p 4 -q 1 q 2 D . (117)
Hereafter the main focus will again be on the neutral situation where each rule, when played alone, is fair (G A = G B = 0). The condition for Rule A to be fair is again [START_REF] Comtet | Stochastic Processes and Random Matrices[END_REF], expressing that the corresponding random walk is symmetric. The condition that Rule B is fair reads

p 3 p 4 = q 1 q 2 . (118)
This non-linear relation leaves three free parameters. We choose the parametrization

q 1 = ab c , q 2 = ac b , p 3 = a bc , p 4 = abc, (119)
and introduce for further convenience the logarithmic co-

ordinates a = e -λ , b = e u , c = e v . ( 120
)
Figure 8 shows the parameter space of the neutral situation in the (u, v) plane, for a fixed value of a in the range 0 < a < 1. Allowed parameter values lie inside a square with vertices C(λ, 0), E(0, λ), F(-λ, 0) and H(0, -λ). The edges of the square correspond to limiting cases: we have p 4 = 1 along CE, q 2 = 1 along EF, p 3 = 1 along FH and q 1 = 1 along HC. Symbols + and -refer to the sign of the gain (see below (126)). The midpoints D (q 1 = q 2 = a, p 3 = a 2 , p 4 = 1) and G (q 1 = q 2 = a, p 3 = 1, p 4 = a 2 ) of the edges CE and FH play a part in the subsequent discussion.

Parity, i.e., the change of sign of the walker's position (n ←→ -n), amounts to exchanging parameters according to p ←→ q for Rule A, and for Rule B p 4 ←→ q 1 , p 3 ←→ q 2 , i.e., c ←→ 1/c or v ←→ -v. Parity therefore amounts to a reflection of Figure 8 with respect to its horizontal u-axis. No symmetry is associated with the reflection of Figure 8 with respect to its vertical v-axis. Moreover, at variance with the capital-dependent games considered in Sections 2 and 3, the history-dependent Parrondo games considered here do not exhibit any simple transformation under time reversal.

Random games

The first situation of interest demonstrating Parrondo's paradox is again that of random games, where at each time step Rule B is chosen with probability ρ and Rule A with the complementary probability 1-ρ. In order to determine the average gain G of games, it is sufficient to know the stationary average state vector φ. The average Markov matrix M (see [START_REF] Stirzaker | Stochastic Processes and Models[END_REF]) again has the same functional form as M B , with effective parameters

q 1 = (1 -ρ)q + ρq 1 , q 2 = (1 -ρ)q + ρq 2 , p 3 = (1 -ρ)p + ρp 3 , p 4 = (1 -ρ)p + ρp 4 . (121)
The average gain G is obtained by replacing all parameters entering (117) by the above effective values.

For the uniformly random game (ρ = 1/2), where at each time step Rules A and B are chosen with equal probabilities, we thus obtain

G = p 3 p 4 -q 1 q 2 + p(p + p 3 + p 4 ) -q(q + q 1 + q 2 ) D , (122) with
D = q 1 q 2 + 2q 1 p 4 + p 3 p 4 + p(p + p 3 + p 4 + 2q 1 ) + q(q + q 1 + q 2 + 2p 4 ). (123)
The expression (122) again allows one to measure the rarity of Parrondo's paradox. We define the probability of observing Parrondo's paradox as the volume of the fivedimensional domain in (p, p 1 , p 2 , p 3 , p 4 ) space such that the inequalities (2) hold, with G given by (122). A numerical integration again yields a very small number (see (35))

Prob(Parrondo's paradox) ≈ 0.000505. ( 124
)
From now on, we restrict the analysis to history-dependent Parrondo games in the neutral situation where each rule, when played alone, is fair (G A = G B = 0). Using the parametrization ( 25), (119), we obtain the following expression for the average gain:

G = aρ(1 -ρ)(b 2 -1)(c 2 -1) D , (125)
with

D = 2(1 -ρ) 2 bc + ρ(1 -ρ)a(3b 2 + 1)(c 2 + 1) + 4ρ 2 a 2 bc(b 2 + 1). ( 126
)
The expression (125) shows that the gain has the sign of the product (b 2 -1)(c 2 -1), i.e., equivalently, of the product uv, irrespective of a and of the probability ρ. Therefore, in the neutral situation under consideration, Parrondo's paradox holds in one half of parameter space, i.e., in the two regions marked by + signs in Figure 8. The average gain vanishes as ρ → 0 and ρ → 1, where random games respectively degenerate to Rule A and Rule B. It reaches its absolute maximum,

G max → 1, (127)
in the limit where a → 0 and ρ → 1 simultaneously. More precisely, for a fixed small value of a, the average gain G reaches its maximum with respect to ρ, b and c for

ρ ≈ 1 - √ 2 a, b ≈ 2 -1/4 √ a, c ≈ 2 1/4 √ a. (128)
The corresponding point in Figure 8 is along the edge FH and close to its midpoint G. This maximum reads

G max (a) ≈ 1 -8 √ 2 a, (129)
so that (127) is attained in the a → 0 limit. This limit is however singular -irrespective of the parameters b and c, provided they remain in the allowed range -as another eigenvalue of the Markov matrix M B goes to unity, so that the latter matrix loses its property of unique ergodicity. The weak-contrast scaling regime is defined by the conditions that both parameters b and c are close to unity, i.e., that u and v are simultaneously small. This scaling regime therefore corresponds to zooming on the center of Figure 8. At variance with the situation of capitaldependent games, in the present case the weak-contrast regime keeps one free parameter, a. For random games, the expression (125) for the average gain vanishes proportionally to uv. We shall see in Section 5 that a similar scaling holds for arbitrary games. We are thus led to introduce the gain amplitude

g = lim u,v→0 G uv . (130)
For random games, (125) yields

g = 2aρ(1 -ρ) (1 + (2a -1)ρ) 2 .
(131)

For the uniformly random game (ρ = 1/2), this reads

g = 2a (1 + 2a) 2 . ( 132
)
When the probability ρ of choosing Rule B varies between 0 and 1, the amplitude (131) reaches its maximum

g = 1 4 ( 133
) for ρ = 1 1 + 2a . ( 134
)

Periodic games

We now turn to periodic games, defined by the periodic repetition of a unit cell W of length P . Here, too, the stationary state of the game has the same period P as the game itself. It is encoded in P state vectors φ n obeying

φ n = M τn φ n-1 (n = 1, . . . , P ), (135)
with the notation (44), and with periodic boundary conditions (φ P = φ 0 ). The associated gain reads

G W = 1 P P n=1 J • φ n (136)
(see ( 103)). The recursion (135) amounts to a system of 4P linear equations. The complexity of the expressions of the gain G again grows very rapidly with the period P . The gain is invariant under cyclic permutations, but not under reversal of the unit cell. Its expressions for periods 2 and 3 are as follows.

• P = 2. There is only one unit cell with period 2. The corresponding gain reads

G AB = (b 2 -1)(c 2 -1) 2(b 2 + 1)(c 2 + 1) . (137)
• P = 3. There are two unit cells with period 3. The corresponding gains read

G AAB = a(b 2 -1)(c 2 -1) 6bc , (138)
G ABB = a(b 2 -1)(c 2 -1) 3b N D , (139)
with

N = 3b 2 c -ab(2b 2 + 1)(c 2 + 1) + a 2 c(b 2 + 1) 2 , D = 2b 2 c 2 + abc(b 2 -1)(c 2 + 1) -a 2 (b 2 + 1)(b 2 -2c 2 + b 2 c 4 ). ( 140
)
The above expressions demonstrate that the gain vanishes proportionally to (b 2 -1)(c 2 -1), i.e., to uv in the weak-contrast regime. The corresponding gain amplitudes (see (130)) are listed in the first three lines of Table 2.

5 Weak-contrast scaling regime of history-dependent games

Generalities

The problem again simplifies in the weak-contrast regime (u, v → 0). Hereafter we use the shorthand notation

µ = 1 -2a, (141)
so that 0 < a < 1 translates to |µ| < 1.

For the periodic games considered in Section 4.3, the matrix recursion (135) boils down to two coupled linear recursion relations for the rescaled co-ordinates

x n = 1 + lim u,v→0 X n -Y n -Z n + T n u , (142)
y n = lim u,v→0 X n -Y n + Z n -T n uv , (143)
namely, with the notation (44):

σ n = 0 ⇒ x n = 1, y n = 0, (144)
σ n = 1 ⇒ x n = µx n-1 , y n = µy n-2 + (1 -µ)x n-1 , (145)
with periodic boundary conditions (y P = y 0 , x P = x 0 ). The gain amplitude (see ( 130)) reads

g W = lim u,v→0 G W uv = 1 P P n=1 y n . (146)
Here, too, the above formalism extends to aperiodic games (see Section 5.4).

There are analogies and differences between the studies of the weak-contrast regimes exposed in Sections 3.1 and 5.1. The main difference is that in (54), (55) the damping factor κ is uniform and the variable σ n encoding the rule applied at step n enters linearly, whereas the full structure of the recursions (144), (145) depends on σ n .

Random games

As a first application of the above formalism, let us revisit random games, considered in Section 4.2. As a consequence of (144), (145), the stationary averages x and y obey

x = 1 -ρ + µρx, (147) y = ρ(µy + (1 -µ)x), (148)
hence

x = 1 -ρ 1 -µρ , (149)
g = y = (1 -µ)ρ(1 -ρ) (1 -µρ) 2 . ( 150
)
The result (131) is thus recovered.

Periodic games

We now revisit the situation of periodic games, considered in Section 4.3. At variance with (54), (55), where the variable σ n enters linearly, allowing for the explicit solution (63), in the present situation (144), (145) cannot be solved in closed form for periodic games with arbitrary unit cell W . An explicit formula for the gain amplitude can however be obtained in the case where the unit cell consists of only two blocks (see (64)), i.e.,

W = A M B N , (151)
with M , N ≥ 1 and P = M + N . The form of the result depends on whether M is one or larger, and on the parity of N . Omitting details, we obtain

• M = 1, N = 2k : g A M B N = (1 -µ k )(1 -µ 2k+1 ) P (1 -µ) , (152)
• M = 1, N = 2k + 1 :

g A M B N = 1 -µ k+1 P (1 -µ) , (153)
• M ≥ 2, N = 2k :

g A M B N = (1 -µ k )(1 -µ k+1 ) P (1 -µ) , (154)
• M ≥ 2, N = 2k + 1 :

g A M B N = (1 -µ k+1 ) 2 P (1 -µ) . ( 155
)
When both blocks lengths M and N become simultaneously large, the amplitude falls off as

g A M B N ≈ 1 P (1 -µ) = 1 2aP , (156)
up to exponentially small corrections. This 1/P fall-off can again be interpreted by stating that only the interfaces between blocks yield some gain. We now turn to general features of interest exhibited by the amplitudes of periodic games. The dependence of the amplitude g W on the unit cell W again appears to be very intricate in general. Table 2 gives the product P g W for all periodic games with primitive period P ≤ 6. The explicit results (152)-(155) yield 15 of the 21 expressions given there, whereas the remaining six cases require a specific solution of the recursion (144), (145).

The following characteristics emerge from the results listed in Table 2. For all periodic games, the product P g W is a polynomial in µ with integer coefficients. At variance with the case of capital-dependent games, the gain amplitude is not invariant under time reversal. The two unit cells of period 6 marked by asterisks are the shortest ones exhibiting this lack of symmetry. They are time-reversed of each other and have different amplitudes.

The situation where µ = 0, i.e., a = 1/2, is very special. Indeed, for u = v = 0 both Rule A and Rule B correspond to symmetric random walks. This is the only case where an exact expression of the gain amplitude g W can be obtained for all periodic games, namely

P W P gW 2 AB 1 3 AAB 1 -µ ABB 1 -µ 3 4 AAAB 1 -µ AABB 1 -µ 2 ABBB 1 + µ 5 AAAAB 1 -µ AAABB 1 -µ 2 AABAB (1 -µ)(2 + µ) AABBB (1 -µ)(1 + µ) 2 ABABB (1 -µ 2 )(2 + µ 2 ) ABBBB (1 -µ 5 )(1 + µ) 6 AAAAAB 1 -µ AAAABB 1 -µ 2 AAABAB (1 -µ)(2 + µ) AAABBB (1 -µ)(1 + µ) 2 ⋆ AABABB 2(1 -µ 2 ) ⋆ AABBAB (1 -µ)(2 + µ + µ 2 ) AABBBB (1 -µ 3 )(1 + µ) ABABBB 2 + µ ABBBBB 1 + µ + µ 2
g W = ν P , ( 157
)
where ν is the number of blocks of letters A (or, equivalently, of blocks of letters B) in the unit cell W . In other words, 2ν is the number of interfaces between blocks per period.

The maximal gain amplitude is reached for either the first or the second of the periodic games listed in Table 2, according to values of a, namely

g max =      g AB = 1 2 for 0 < a < 3/4, g AAB = 2a 3 for 3/4 < a < 1. (158)
It has been checked by means of an exhaustive enumeration that no higher gain is reached for periods up to P = 30. For a = 1/2, the above result is a consequence of (157), as the ratio ν/P reaches its maximum 1/2 for the periodic game AB. It however comes as a surprise that AB remains the optimal game over three quarters of the range of the parameter a.

We again make a digression out of the weak-contrast regime in order to look at the maximal gain of the historydependent Parrondo game all over its parameter space. For fixed a, the periodic games AB and AAB reach their respective highest gain, namely

G max AB = (1 -a) 2 2(1 + a) 2 , G max AAB = (1 -a) 2 6 , (159)
at both midpoints D and G (see Figure 8). For fixed a in the range a > 1/2, the maximal gain -over b and c and over all possible rule patterns -is always the larger of both expressions given in (159). The situation is however different for a < 1/2. There, the optimal periodic game undergoes an infinite sequence of transitions towards longer and longer periods as a becomes smaller and smaller. The absolute maximal gain is given by

G max → 1. ( 160
)
This limiting value was already encountered in the framework of random games (see ( 127)). It is approached in the coupled singular limit where a → 0, whereas the periods of optimal rule patterns diverge.

Aperiodic games

The formalism of Section 5.1 extends to any aperiodic game, either deterministic or random. We do not have any analytical result such as (71). Nevertheless, the recursions ( 144), (145) can be iterated by numerical means for any given aperiodic sequence. Because of the exponential damping property of these recursions, very accurate numerical values of the amplitude g can be obtained, especially in situations where the fluctuations δ n defined in (93) are small. We again consider the cut-and-project aperiodic game introduced in Section 3.4.2. Figure 9 shows plots of the gain amplitude g against the rotation number ω defining the cut-and-project sequence, for several values of the parameter a. Curves for a ≤ 1/2 and a ≥ 1/2 are shown in two separate panels, for the sake of clarity.

For a = 1/2, the result (157) translates to

g = ω for 0 ≤ ω ≤ 1/2, 1 -ω for 1/2 ≤ ω ≤ 1. (161)
The corresponding triangular shape is shown in black in both panels of Figure 9. For ω ≤ 1/3, all letters B are isolated and separated from each other by at least two letters A. Setting k = 0 in the expression (155), we predict that each letter B in the sequence brings a contribution 1 -µ = 2a to the gain. We thus obtain the linear law

g = 2aω (0 ≤ ω ≤ 1/3), (162)
that is clearly visible to the left of the vertical dashed lines in both panels of Figure 9. As a general rule, the dependence of the amplitude g on the rotation number ω exhibits more and more pronounced fine details as |µ| grows, i.e., as a departs from 1/2 on both sides. Red curves correspond to the largest values of |µ|, namely µ = 4/5 (a = 1/10) in the upper panel, and µ = -4/5 (a = 9/10) in the lower panel. Figure 10 shows the dependence of the amplitude g on the parameter a for four typical irrational rotation numbers:

ω 1 = 1/τ = ( √ 5 -1)/2, ω 2 = 1/τ 2 = (3 - √ 5)/2, ω 3 = √ 2 -1, ω 4 = 2 - √ 2.
The first two numbers are related to Fibonacci (or golden-mean) sequences, the last two to octonacci (or silver-mean) sequences (see [START_REF] Janot | Quasicrystals: A Primer[END_REF][START_REF]Quasicrystals and Geometry[END_REF] for overviews). The amplitude g of the uniformly random game (see (132)) and the maximal amplitude g max (see (158)) are also shown for comparison.

Overview

This paper is aimed at being part of a special issue on the theory of disordered systems. It has been written in a fully self-contained manner. Of course, we have no claim to compete with either historical [6][7][8][9] or very recent [41] motivation was to draw on the analogy between the temporal products of non-commuting Markov matrices involved in the study of Parrondo games and the spatial products of non-commuting transfer matrices which are ubiquitous in the physics of 1D disordered systems. There are many similarities as well as differences between both situations. The most salient common feature is that the non-commutativity of the matrix products ascribes a crucial role to the order of factors, representing either the rule pattern in Parrondo games or the positions of impurities in disordered chains. Markov matrices however enjoy a very specific property. They conserve probability, and so the entries of products of Markov matrices are bounded by unity. The concept of Lyapunov exponent, which is otherwise central in most situations involving products of random matrices, is therefore virtually useless in the present setting.

The investigations of Parrondo games reported here have been freely inspired by the theory of 1D disordered systems. We have dealt with both capital-dependent and history-dependent Parrondo games on the same footing in a systematic way, by means of a mapping onto a random walker on the 1D lattice. Within this unifying framework, the gain G of the player identifies with the velocity of the walker's ballistic motion. For definiteness, we have chosen one paradigmatic game in each class, and focussed our attention onto the neutral situation where each rule, when played alone, is fair (G A = G B = 0). The main emphasis is on the dependence of the gain on the remaining free parameters and, more importantly, on the game, i.e., the rule pattern, be it periodic or aperiodic, deterministic or random.

One of the most original sides of this work is the identification of weak-contrast regimes for both classes of Parrondo games considered here, and a detailed quantitative investigation of the gain in the latter scaling regimes.

For the capital-dependent game mod 3 introduced in Section 2, encompassing Parrondo's historical example, one single asymmetry parameter v characterizes the neutral situation. The weak-contrast regime, studied in Section 3, corresponds to v → 0, where the gain of a generic game scales as G ≈ gv 3 . For the two-step history-dependent game introduced in Section 4, the neutral situation is richer, as it depends on three parameters. The weak-contrast regime, studied in Section 5, corresponds to both relevant asymmetry parameters u and v being simultaneously small. The gain of a generic game now scales as G ≈ guv. For both classes of games, the determination of the gain amplitude g has been reduced to the solution of two coupled linear recursions. This reduction allowed us to derive a wealth of novel results on both classes of Parrondo games. It is expected that more complex Parrondo games, with either K > 3 for capital-dependent games or Q > 2 for history-dependent games, admit weak-contrast scaling regimes in full generality, even though the number of remaining relevant parameters in those regimes grows very fast with the complexity of the game.

Fig. 3 .

 3 Fig. 3. Maximal gain amplitude g max P of periodic capitaldependent Parrondo games with period 5 ≤ P ≤ 30. Horizontal black line: absolute maximum g max (see (69)).

Fig. 8 .

 8 Fig. 8. Parameter space of Rule B of the history-dependent Parrondo game in the (u, v) plane for a fixed value of a in the range 0 < a < 1. Allowed parameters lie inside the square (see text).

Fig. 9 .

 9 Fig. 9. Dependence of the gain amplitude g of the historydependent Parrondo game on the rotation number ω defining the cut-and-project sequence, for several values of a (see legend). Upper panel: a ≤ 1/2. Lower panel: a ≥ 1/2. Vertical dashed lines: upper edge (ω = 1/3) of validity of the linear law (162).

Table 1 .

 1 Exact

	max = g ABABB =	488 605	= 0.806611	(69)

rational and numerical expressions of the gain amplitude gW of the capital-dependent Parrondo game with all periodic rules W with primitive period P ≤ 6. For each period P , unit cells W are ordered according to increasing gains. Last column: corresponding rational rotation number ω of the cut-and-project sequence (see Section 3.4.2), when applicable.

Table 2 .

 2 Exact expressions of P times the gain amplitude gW for all periodic history-dependent Parrondo games W with primitive period P ≤ 6.

  reviews on Parrondo games and Parrondo's paradox. Our Dependence of the gain amplitude g of the historydependent cut-and-project game on the parameter a, for four typical irrational rotation numbers (see legend). AVE: amplitude g of the uniformly random game (see (132)). MAX: maximal amplitude g max (see (158)).

		0.6 0.8	ω 1 ω 2 ω 3 ω 4
			AVE
			MAX
	g	0.4
		0.2
		0 0	0.2	0.4	a	0.6	0.8	1
	Fig. 10.

n mod K = 0, . . . , K -1 is the rest of the Euclidean division of n by K.

The primitive period P of a periodic sequence is its smallest positive period.

Here and throughout the following, w. p. is a shorthand for 'with probability'.