ABSTRACT

Games often provide a good introduction to interesting phenomena in mathematics. In this note, we examine three variations of an iterative sharing game played around a circular (or not so circular) table. More precisely, for each variation, we study the tendency toward equal distribution among the players. In the first variation, the players have discrete amounts at each step. The second variation removes this restriction, and the third one considers an infinitely long table with an infinite number of players.

Keywords: Equidistribution; Iteration; Linear Transformation; Limit Distribution

1. Sharing around a Table with Discrete Amounts

Suppose you have persons seated around a circular table, each having an even number of dimes. Number them from 1 to counterclockwise, and denote by the (even) number of dimes that the i-th person has,

The game is played by repeating the same two steps over and over, as follows: first, each person gives one half of her dimes to the person sitting on her right. In symbols,

(1)

with the convention. Note that the new’s are not all necessarily even. The second step, which allows us to repeat (1), is to add one dime to each odd:

(2)

We call this game the “discrete sharing game”.

Proposition 1.1 By iterating (1) and (2), after a finite number of steps, we will have, i.e. every person ends up with the same number of dimes.

This problem can be found in [1]. The proof follows easily from two observations. First, the maximum amount around the table cannot increase, nor can the minimum amount decrease. Second, if the minimum amount is strictly smaller than the maximum amount, then after the next step, either the minimum amount will have increased, or else the number of players having the minimum amount will have decreased. Together, these observations imply that after finitely many steps, the maximum and minimum amounts will coincide. We leave the details of the proof to the reader. Another interesting problem is to determine the number of iterations needed to reach equidistribution in terms of the initial data (see Figures 1, 2 and 3).

An iterative sharing game that tends toward the equal distribution of the players’ amounts is what we call an

“equidistribution process”. You may think that in the above example, the equidistribution is due to the fact that the sharing is done by halves. However, Proposition 1.1 generalizes without much effort: suppose all the’s are initially multiples of a fixed number. Replace (1) with

and (2) with a similar step where you add dimes until you reach the first multiple of greater than or equal to for all. Then again you will end up with after a finite number of steps.

2. Sharing around a Table with Complex Numbers

Suppose there are persons around a circular table, numbered counterclockwise as before. But this time each of them starts with an initial amount, that can be any complex number. Let be a positive real number,. It will play the role of above. We want to study the behavior of

as the number of iterations goes to infinity. Note that the balancing step (2) does not make sense here anymoreas neither the’s are necessarily integers nor for some. We can give a realistic feeling to the game if we restrict the’s to real numbers. Then at each step, each person is sharing her wealth or debt by giving a portion of her number to the person on her right. But this restriction is unnecessary, so we will work in the more general setting of complex numbers. In contrast to the discrete version of the last section, we call this the “complex sharing game”.

For, let be the amount that person has after the -th step. Then, and we also extend the definition by setting whenever, so that makes sense for any integer i. The rule for sharing at each step then yields

(3)

where the sub-indices are understood modulo.

Note that if, then Since clearly this sharing game with only two people is an equidistribution process. This is particularly trivial if in which case both persons will have the same number after just one step. From now on, we assume. Note also that the sum of the numbers around the table remains constant with each step. Let us denote this constant by, that is

2.1. The Sharing Transformation and Its Eigenvalues

We can model the sharing process (3) with the aid of the -linear transformation given by

With the notation as above, we see that where the exponent on indicates the number of times that this transformation is composed with itself:.

In the canonical basis of, has matrix

which has entries along the main diagonal, on the diagonal immediately below and at the upper right corner, and zero elsewhere. This is a “stochastic” or “Markov” matrix, as its entries are all non-negative and the sum of the entries in each row is equal to 1. For more information on these matrices and their interesting properties, we refer the reader to [2]. We will presently prove some of these properties for our matrix in order to make this note more self-contained, but the reader should be aware that both Propositions 1.1 and Theorem 2.2 below hold for any stochastic matrix.

Proposition 2.1 The matrix has n distinct eigenvalues with for.

Proof. Let be the characteristic polynomial of Computing it explicitly, we obtain

Let be the nth distinct complex roots of Then it is easy to see that the (distinct) roots of are

If we set then we have that For we have The inequality is strict, as is not a positive real number if □

An eigenvector associated to the eigenvalue 1 is In our game, this eigenvector corresponds to the case where every person has the same amount. Clearly, this situation is stable, i.e. does not change after applying. Let denote eigenvectors for the eigenvalues respectively. Thus for each Now we are ready for the main result of this section, which is that the complex sharing game also tends toward equal distribution among the players. (See Figures 4 and 5).

Theorem 2.2 The complex sharing game described by (3) is an equidistribution process. That is,

Proof. Note that is a basis for consisting of eigenvectors of. Write

with. Then

Proposition 2.1 now implies that

Therefore the game is indeed an equidistribution process. □

Note that, since the sum of the n numbers remains constant at each step of the iteration above, we must have

There is another way to obtain the value of. Let be the subspace of defined as

Lemma 2.1 Let be the basis of eigenvectors fixed above. Then is a basis of

Proof. Write for. Since we have

Adding the coordinates on each side of this identity, we get

Since for we conclude that Therefore, the subspace spanned by is contained in and since both of these spaces have dimension, we must have equality, proving the claim. □

We can use this statement to compute the value of. We have

Recall that we chose Since, the sum of the coordinates of this vector is equal

to zero, and hence From this we deduce again that

2.2. An Explicit Formula for

Recall that we defined, and in particular, whenever. Let us find a formula, in terms of the initial data, for the number that each person will have after any given step of the complex sharing game:

Proposition 2.3 For any and, we have

Proof. We use induction on, the initial step being obvious. Next, assume the formula holds for all and for all with for a fixed. Then,

so the formula holds for and the proof is complete. □

In particular, when each person shares one half of her amount at each step, we have Corollary. If then for all and.

By grouping the binomial coefficients in congruence classes of j modulo n, we obtain an equivalent formulation of this result (always for):

where each congruence is understood to be modulo If all the initial amounts are equal, the sharing process is stable from the beginning, and this formula reduces to the well known fact about the sum of the entries in the -th row of the Pascal triangle,. What is more interesting is that, in light of Theorem 2.2, for all i, regardless of the initial amounts. So given n, if we group the binomial coefficients by the congruence classes of j modulo n and give each class an arbitrary weight, then as we go further down the rows of the Pascal triangle, the weighed sum of the entries divided by the sum with no weights, , always tends to the average of the weights. More generally, regardless of the value of r, Theorem 2.2 shows that the sums given in the statement of Proposition 2.3 all tend to the same limit as

2.3. Eigenvectors of T_r and Vandermonde Matrices

Let be any n-th root of unity, i.e. Then it is easy to check that

That is, is an eigenvector of with eigenvalue, the latter being of course one of the above.

Therefore, if is a primitive n-th root of unity, then the vectors given by

form a basis for consisting of eigenvectors of. Note that we have again as above, and that the eigenvalue for is

Under the (ordered) basis has diagonal matrix

The matrix whose columns are the coordinates of the vectors changes the basis from the canonical to. This is a Vandermonde matrix

and it is well knwon that its inverse is another (normalized) matrix of the same type,

We can use this last matrix to express the vector of initial amounts in terms of the basis. As in the proof of Proposition 2, let Then

and a straightforward computation yields for. This gives us yet another way to obtain.

3. Sharing at an Infinite Table

Suppose now that, instead of a circular table, we have an infinite number of persons seated on one side of an infinitely long “rectangular” table , their number being unbounded both from the left and the right. Each person has an initial (complex number) amount to be shared in the same way as in the game with the circular table: at each step, each person gives a portion of her amount to the person on her right. As before, r is a fixed positive real number,. We call this version the “infinite sharing game”.

The initial data now is a sequence of complex numbers. We define as in (3) for and. Note that this time there is no “congruence modulo “, as there are infinitely many players, indexed by the integers. Indeed, the rectangular table can be regarded as the limit of circular tables having The recursion from sharing is the same as before:

(4)

Proposition 2.3 also holds here, and the proof is the same. The only difference is that now we do not have whenever, the condition that effectively made the game circular (and with players) before. So we still get

(5)

This formula shows something that is obvious in the new context, namely that the amount of the person in the i-th place will depend only on the initial amounts of those people seated to her left (and on her own initial amount, of course). So there is no reason to believe that this new game should be an equidistribution process. For instance, if there is a concentration of wealth (by which we mean numbers with large absolute value) in some section of the table, it will never spread to the left. However, as the following result shows, if one of the sequences converges, then the game will tend toward equal distribution.

Theorem 3.1 If exists for some, then exists for all, and all of these limits coincide.

Proof. Let be such that exists. Then, using (4), we have

i.e. exists and it is equal to. By induction, we have then that exists and for all.

Now, using (4) again,

(6)

for all. Since as, given there exists such that for all. But then we have that for,

(7)

because

thanks to (6), and

For, we can get which, together with (7), shows thatand from here we deduce (again by induction) that for all.  □

It would be an interesting problem to characterize those sequences of initial data that induce an equidistribution process in the infinite rectangular table. Note for instance that if is any periodic function and we set for, then the game will be an equidistribution process (this is essentially the complex game around a circular table, where the number of players is the period of, “lifted” to the infinite rectangular table). One natural question to ask is this: if the initial data is bounded, must the infinite game be an equidistribution process? Suppose that for all. Then, since

(8)

we see from (5) that for all and. Does this imply that the sequence converges for some (and hence all)? The answer is NO, as the following example shows.

Example 1 Suppose, and set

This sequence can be defined recursively by first setting all its values equal to zero for, then, and from there on we move to the left two zeroes, then three ones. Every time we end with a list of ones, we put a sequence of zeroes doubling in the number of the sequence already built so far (starting from). And every time we end with a list of zeroes, we put a sequence of ones equal to the number of the sequence already built so far (starting from), always moving to the left. So, the sequence looks like this (starting from on the right):

With this sequence as the initial data and (5), one can show that for any positive integer

so the sequence does not converge and, in light of Theorem 3.1, does not converge for any.

An immediate consequence of Theorem 3.1, is that if there exist and such that for all, then the infinite game is an equidistribution process. This is, in fact, a particular case of a more general fact: it turns out that equidistribution follows from the existence of (and not, as we just saw, from the boundedness of).

Theorem 3.2 Suppose that. Then for every.

Proof. Consider the sequence defined as for all. For a fixed, due to (4), it is easy to see that if and only if, so we can assume without loss of generality that. For a fixed, since the sequence converges, there exists such that

for all. Let be given. Since, there exists such that if

. For, we use (5) to write

(9)

As (because of (8)), we get easily

As for the first summand of (9), we have:

Since, for we get, and hence we can bound (9) as follows:

which proves that  □

When the initial amounts are all real, , one can similarly show that if (resp.), then (resp.) as, for every.

Note that the existence of is sufficient but not necessary for the infinite game to be an equidistribution process. This can be seen from the above example where the initial data take on the values of a periodic function. As mentioned above, it would be interesting to find more explicit necessary and sufficient conditions than the existence of for some, which is essentially the characterization we get from Theorem 3.1 and (5).

Acknowledgements

We are grateful to Adrián Paenza from whom we learnt about the discrete sharing game and the reference [1]. We would also like to thank José Ignacio Burgos for interesting discussions, Gervasio Gómez for programming several simulations and producing the figures, and Juan Sabia for suggesting the statement of Theorem 3.2 as it appears in the text, which is stronger and more general than what we had originally written.

The first author was partially supported by the research project MTM201020279 from the Ministerio de Ciencia e Innovacióon (Spain).

[1] REFERENCES

[2] G. Z. Chang and T. W. Sederberg, “Over and Over again,” New Mathematical Library, 39. Mathematical Association of America, Washington DC, 1997. xiv+309 pp. ISBN: 0-88385-641-7.

[3] G. Latouche and V. Ramaswami, “Introduction to Matrix Analytic Methods in Stochastic Modeling,” 1st Edition, PH Distributions, ASA SIAM, 1999.