Marc A A Van Leeuwen

Some simple bijections involving lattice walks and ballot sequences

research documents, whether they are published or not. The documents may come

Some simple bijections involving lattice walks and ballot sequences

Introduction

When considering a combinatorial formula that can be interpreted as equating the outcomes of two (families of) enumeration problems, a proof in the form of a bijection (or family thereof) between the sets in question is often considered to be of more value than one based on other methods, such as manipulations of formal power series. Whether this is really the case depends to a large extent on the nature of the bijection. The best situation is one where the bijection can be interpreted as simply relating two ways describing the same underlying combinatorial object; for instance the bijection between Dyck paths and balanced sequences of parentheses, which simply interprets up-steps as '(' and down-steps as ')', is of this nature. A bijection that consists of transforming an object of the first kind into an object of the second kind by a single traversal performing some kind of substitution, and in such a way that the relation between input and final output can be easily perceived, will do almost just as well. In both cases it is often possible to relate one or more additional statistics on the input with an statistics on the output, and thus refine a simple identity of natural numbers into an one of polynomials with non-negative coefficients (the idea of q-analogues is largely based on this principle). However when the bijection is based on a more complicated algorithm, or is obtained by a composition of several bijections, then the situation may become much less transparent, to the point of providing no more insight (possibly even less) than a proof by formal algebraic manipulations.

The dividing line between simple and complicated bijections is not always clear, and a bijection may be rendered more transparent by a particular point of view. For instance, one can map binary plane trees with n internal nodes (and n + 1 leaves) to Dyck paths of length 2n by traversing the tree in preorder, recording an up-step for each internal node encountered and a down-step for every leaf except the final one (cf. [START_REF] Stanley | Enumerative combinatorics[END_REF], proposition 6.2.1(i),(ii)), and such a path P can be further transformed into a plane tree with n + 1 vertices, namely one whose root node has descendents that correspond (in order) to the minimal Dyck-path factors of P , and are obtained by recursively transforming those factors after removing their two extremal steps. The resulting bijection from binary plane trees to plane trees appears to be rather opaque, and not provide much more insight than the observation that the generating series for both enumeration problems satisfy (for simple reasons) the quadratic relation C = 1 + XC 2 that characterises the series C = n C n X n of the Catalan numbers, which numbers therefore solve both problems. However, from the point of view of a programming language like LISP (in which non-empty lists are represented by a binary node with links pointing to the first element and to the remainder of the list), one can interpret the binary tree as the internal representation of the recursively nested list of lists corresponding to the planar tree (of which each node is interpreted as the list of its descendents). This point of view makes the correspondence, at least to us, much more transparent.

On the other hand, when a bijection is defined by an algorithm that involves the repetition of some operation a (finite but) variable number of times, until reaching some desired condition, then this bijection is likely to be quite opaque. This is for instance probably the reason that use of the "involution principle" (due to Garsia and Milne) is generally considered to be less desirable in bijective proofs. An example where such iteration can arise, is when one is given a bijection f : A → B where A, B are finite subsets of some set X, and one deduces from it a bijection g : X \ B → X \ A between their complements, by iterating f as often as possible; in other words g(x) = f n (x) for the smallest n ∈ N for which f n (x) / ∈ A (which must exist because all other f i (x) are distinct elements of A). Whether the bijection g obtained by this "complementation principle" is transparent at all, depends on whether the effect of iterating f can be easily understood, and notably on whether it is easy to predict the number n of iterations that can be applied to a given element x. 1 In this note we will consider the particular case of some well known enumerative results involving lattice paths, or equivalently walks on the one-dimensional lattice Z. Our walks will always start at 0, and we first consider the "binary" 1 In fact the involution principle can be seen as an application of the complementation principle to the situation of a "signed set" Y consisting of disjoint union of a set X of "positive" elements and a finite set N of "negative" elements, equipped with injections

f 1 , f 2 : N → X; one can obtain a bijection X \ f 1 (N ) → X \ f 2 (N ) by taking A = f 2 (N ), B = f 1 (N ), and f = f 1 • f -1 2 .
The injections can be extended to fixed-point free involutions of the union of N and its image, and then to involutions of Y by fixing the remaining points of X; this explains the name of the principle. In practice the fixed-point free involutions in this description are usually directly obtained as sign-reversing partial involutions of Y that are always defined at negative elements, and which are then artificially extended as we did to involutions of Y .

case where each step changes the position either by +1 or by -1. Each walk can be transformed into a lattice path in (the "diagonal" index 2 sub-lattice of) Z 2 starting at the origin, in which steps advancing by ε become path segments advancing by (1, ε) (which we draw with the first "time" coordinate increasing downwards). We shall switch between these points of view whenever convenient.

We call a finite walk "recurrent" if it ends at 0, and "positive" if it is a walk on N ("non-negative" would be more precise, but tiresome). Viewed as lattice paths, (binary) recurrent positive walks correspond precisely to Dyck paths.

The most basic case of the enumerative coincidences that we shall study is the fact that there are 2n n positive walks of length 2n, a number that also (and more obviously) counts the recurrent walks of that length. This result appears to be well known, at least in the lattice path community, but in view of its simplicity it is somewhat surprising that it does not receive prominent mention in the enumerative combinatorics literature. We do not know whether any nice bijective proofs for this result are known, but it would at least seem that none are "well known". This note proposes a simple bijective proof that, although it involves the iteration of an operation a varying number of times to transform recurrent walks into positive ones or vice versa, is about as transparent as one could wish for; notably the number of iterations required can be immediately read off from the initial walk, and it is possible to transform the initial to the final path in a single "pass" along the path. This bijection also allows giving a bijective proof of the generating series identity ( n∈N

2n n X n ) 2 = 1 1-4X
, for which there does not appear to be an equally transparent proof using either of the above interpretations of the number 2n n individually. The result can be slightly generalised, while essentially keeping the same proof, in a few ways. One can drop the restriction to walks of even length provided the "recurrent" requirement is relaxed to ending either at 0 or at 1 (since clearly being recurrent is a tall order for odd-length walks). One can also consider "ternary" walks by allowing steps that stay in place (so that the paths corresponding to recurrent positive walks are Motzkin paths), in which case the positive walks are still in bijection with the "almost recurrent" walks, those that end either at 0 or at 1 (the nature of our proof will make clear why one must leave a unit of freedom for the ending point of the walk). Finally one can formulate a corresponding result for n-dimensional walks with a fairly large choice for the set of basic steps allowed: no coordinate should be allowed to change by more than a unit at a time, and the set should be symmetric with respect to negation of each of the coordinates individually.

The bijection we propose is defined by iterating a basic "raising" operation as often as possible. We do not consider it as obtained from the complementation principle mentioned above (although it can be), but rather from a telescoping sum of identities, each of which is closely related to the famous "ballot problem" of J. Bertrand, [START_REF] Bertrand | Solution d'un probléme[END_REF]. Our bijective proof gives rise to a bijective solution of that problem, which appears to be new; at least it is different both from the original proof of D. André [START_REF] André | Solution directe d'un probléme résolu par M. Bertrand[END_REF] (which performs a cyclic rearrangement of votes), and from proofs based on diagonal reflection of part of a lattice path (the "reflection method"). However we shall see that conversely any bijective proof of the ballot problem can be iterated so as to obtain a proof of the identities relating positive and recurrent walks, of which we therefore obtain several different ones. Comparing these, we find that some proof methods that transparently solve the ballot problem lead to rather opaque bijective proofs after iteration.

Positive and (almost) recurrent walks

A very basic kind of lattice walks is that of walks on the one dimensional lattice Z, starting at 0 and moving a unit in either direction at each step. The parity of the point reached after n steps is necessarily that of n, and the statistic of the end point on the set of the 2 n such walks gives a binomial distribution on the points of the required parity. Another, more restricted, class of walks that we shall consider is that of walks on the subset N of the one dimensional lattice, still starting at 0 and moving a unit in either direction at each step; these form the subset of the walks on Z that never visit the value -1. For comparison, here is an initial portion of Pascal's triangle, displayed in the usual fashion with rows symmetrically growing as one moves downwards,2 and a corresponding array of numbers counting walks on N. Note that the second array obeys the same recurrence relation that the first one does (every "internal" entry is the sum of those directly above it), only the boundary condition is changed, namely by requiring the entries in the column of -1 (the leftmost ones displayed) to be 0, reflecting the fact that walks that would visit negative numbers are excluded. In fact the second array can be obtained from the first by subtracting from it a copy of itself that is shifted two units (the distance between adjacent entries) to the left, which produces values 0 in the column -1 for symmetry reasons; one retains the part to the right of that column. It follows that the sum of the entries in any row of the second array is equal to the (most) central entry in the corresponding row of the first array; in the terminology of the introduction, there are as many walks of a given length that are recurrent or (in the case of odd length) almost recurrent (ending at 1) as there are positive walks. It is this "coincidence" that we wish to bijectively explain in this note. We can illustrate the classes of paths between which we seek a bijection graphically as follows (the drawn paths are just examples):

The way in which we obtained the equality of the number of paths of these two types is rather simple, and one may seek to obtain a bijection from it by applying general principles; this will be discussed in the next section. Here however we shall directly consider a correspondence between all positive walks and recurrent walks, without first constructing one corresponding to the fact, implicitly mentioned in the reasoning above, that for any n 2 ≤ k ≤ n there are n k -n k+1 positive walks that end at the value 2kn. If a recurrent walk w happens to be positive as well (it corresponds to a Dyck path), then it can be made to correspond to itself, without applying any operations. In the contrary case there will certainly be a first down-step in w that reaches -1, and then later on possibly a first down-step that reaches -2, and so forth. All these down-steps that for the first time reach a given negative number are changed into up-steps to form the positive walk w ′ corresponding to w; if there were d such steps (so that -d is the most negative number that w visits), then w ′ will end at the number 2d. Any positive walk of even length ends in an even non-negative number; the unique recurrent walk w corresponding to it can be found by setting d to half that final number, and changing the d up-steps that immediately follow the last visit to respectively the numbers 0, 1, . . . , d -1 into down-steps. This correspondence can be extended straightforwardly to include odd-length walks, making those that end at 1 and reach -d as most negative number correspond to positive walks ending at 2d + 1.

Note that the bijection establishes a fact that was not evident in our original argument, namely that n k -n k+1 not only counts the positive walks that end at 2kn, but also the walks of "depth" k -⌈ n 2 ⌉ ending at 0 or 1. Before we state more formally the result thus obtained, we shall generalise it slightly by allowing in addition to up-steps and down-steps also neutral steps, which stay at the same point. Both our initial reasoning and the construction of a correspondence remain valid without much modification for these more general walks, although of course the numbers of walks increase, and there is no longer a parity condition for the end point of the walks. Instead of Pascal's triangle and it anti-symmetrised counterpart we obtain as arrays of numbers the coefficients of (X -1 + 1 + X) n , somewhat ambiguously called trinomial coefficients: 1 1 1 1 1 2 3 2 1 1 3 6 7 6 3 1 1 4 10 16 19 16 10 4 The entries of the second array are differences of trinomial coefficient two places apart, so each of its row sums is given by the corresponding middle trinomial coefficient plus one its neighbours. Like for the first correspondence, we illustrate graphically the types of paths matched by the bijection, and as in the first case the paths depicted actually match under our correspondence.

We can now formulate our main result.

Theorem 1. Within the class of walks on Z starting at 0 and with steps advancing by +1, 0 or -1, there is a bijection, conserving both the length of the walk and the number of steps 0, between on one hand the walks that end either at 0 or at 1, and on the other hand the walks that do not visit negative numbers. The bijection maps walks ending at e ∈ {0, 1} and whose minimal number visited is -d, to walks ending at 2d + e, and is realised by reversing the direction of the d down-steps that first reach respectively the numbers -1, -2, . . . , -d.

Proof. Calling "Motzkin walk" any sub-walk starting and ending at a same number m while not visiting any number less than m (these correspond to Motzkin sub-paths in the lattice path point of view), any walk in the class considered ending at e ∈ Z and whose minimal number visited is -d can be uniquely written as a composition of 2(2d+e)+1 sub-walks that are alternatingly a (possibly empty) Motzkin walk and a single non-stationary step, those 2d + e single steps being (in order) d down-steps and d + e up-steps; they are precisely the steps not contained in any Motzkin walk. The domain and codomain of the bijection are characterised by e ∈ {0, 1} respectively by d = 0, and the bijection, which reverses the d down-steps in this decomposition, produces the same Motzkin walk factors, changing the parameters from (d, e) to (0, 2d + e).

Although we have described the bijection as a single transformation, it can be obtained by repeating a same operation, which reverses only the direction of a single step, d times in succession. Doing so, there is no choice but to start reversing the last one of those d steps, the one that first attains the global minimum -d of the walk: reversing any of the other ones would result in a step that becomes part of a Motzkin walk without in general any means to tell from that walk alone which step it was. The final step however remains outside any Motzkin walks after reversal, and in fact becomes the last up-step that starts at the global minimum of the modified walk, which has become -d + 1; this description shows that the original walk can be reconstructed given only the modified walk. Now repeating the operation of reversing the down-step that first attains the global minimum of the walk will successively reverse the d steps indicated in our bijection, in reverse order of appearance in the walk; after this the operation cannot be further repeated because the global minimum has become 0, and no down-step is needed to first attain it. The successive steps of the transformation are illustrated in figure 1, in a case with d = 3.

-→ -→ -→

Figure 1: From a recurrent walk to a positive walk by pushing minimum upwards

The reverse procedure then consists of repeating the following operation, which decreases the end point of the walk by 2, until that end point is 0 or 1: reverse the first up-step that starts at the global minimum of the walk. Unlike the forward operation, this backward operation could in general be repeated in a reasonable way even after the terminating condition is reached. Doing so until no up-step of the given type can be found would result in a bijection from the set of all positive walks to those ending at their global minimum, and mapping those of the former kind ending at k to those of the latter kind ending at -k. There is more obvious bijection with the same property, namely the one consisting of taking the steps of the walk in reverse order and in the opposite direction (in terms of the corresponding lattice paths, this corresponds to reflection in a horizontal line, and then shifting horizontally to match the starting point).

The operation described on walks or paths is certainly not new. It appears that its most prominent occurrence is in the representation theory of Lie groups: it is an instance of Littelmann's root operator e α on paths of [START_REF] Littelmann | Paths and root operators in representation theory[END_REF], for the most basic case of type A 1 . However, in diverse settings and under various equivalent descriptions, this operation had been known long before; notably it occurs in [START_REF] Littlewood | Group characters and algebra[END_REF] where it is used to prove the simplest case of the Littlewood-Richardson rule.

In those applications there can in fact be more than one such operation, acting on paths in a space of higher dimension, and involving reflections (applied to path segments) in different directions, namely the simple reflections for a root system. It would be interesting to find enumerative consequences of the operations in those settings, but it appears that there are none that are easy to state if the simple reflections, and therefore the associated root operators, do not commute. In fact, although iterating the "raising operators" does give, in spite of their non-commutation, a well defined map from arbitrary paths to dominant ones (those that remain on the positive side of each reflection hyperplanes considered), this map restricted to for instance the recurrent paths is not injective (the size of the fibre above a given dominant path ending at λ is the dimension of the zero-weight space of a representation associated to λ).

For this reason we shall state only a generalisation corresponding to the type A n 1 , where the reflections commute. In this case we can in fact ignore the Lie theoretic point of view, which adds nothing that is not obvious combinatorially. We can treat each of the n coordinate directions separately, repeatedly applying reflections in that direction to certain segments of a path until that coordinate is non-negative throughout the path. These operations for different coordinates commute and can therefore be applied independently. The set of basic steps from which the paths may be constructed may however involve some dependence between the coordinate directions (it could for instance insist that exactly two coordinates change at each step), as long as it is symmetric with respect to each of the n coordinate reflections, and no step involves a change outside the set {-1, 0, 1} to any one coordinate. Therefore we state the result as follows.

Theorem 2. Let any subset S of {-1, 0, 1} n be fixed that is stable under each reflection that negates a single coordinate. Then within the set of walks on Z n starting at the origin and with steps in S, there is a length preserving bijection from those walks that end in a point of {0, 1} n (a vertex of the unit hypercube) to those walks that remain at all times inside the (weakly) positive orthant. It is defined by applying the bijection of theorem 1 to each coordinate separately.

Convolution of central binomial coefficients

There is another enumerative identity for which the bijection we studied provides insight. It is well known that the generating series S = n∈N 2n n X n of central binomial coefficients is given by S = 1 √ 1-4X ; this can for instance be established by developing (1 -4X) -1 2 using the power series binomial formula with arbitrary exponent (cf. [START_REF] Stanley | Enumerative combinatorics[END_REF], Chapter 1, exercise 4). However, the formula means that S 2 is a geometric series with ratio 4X and constant term 1, so that one has

i+j=n 2i i 2j j = 2 2n for all n ∈ N. (1)
The question of explaining this identity combinatorially is an old one; according to [START_REF] Stanley | Enumerative combinatorics[END_REF] p. 52 and [START_REF] Sved | Counting and Recounting, The Aftermath[END_REF] it was raised by P. Veress and solved by G. Hajos in the 1930s. In spite of the simple form of (1), it is remarkably difficult to do this if one interprets the summand in the most obvious way as counting pairs of recurrent walks of lengths 2i and 2j respectively. Although many answers have been proposed, often involving operations closely related to those we have been discussing (see [START_REF] Sved | Counting and Recounting, The Aftermath[END_REF]), none appear so transparent as to really explain the simplicity of the identity. With what we have seen above, we may however also interpret the central binomial coefficients as counting the positive walks of the indicated lengths. Doing so for both coefficients does not make the problem much easier, but if one interprets the first one as counting recurrent walks and the second on as counting positive walks, then a solution presents itself naturally.

From the concatenation of a recurrent walk and a positive walk, the factors cannot in general be uniquely reconstructed, but this decomposition becomes unique if one inserts a single up-step between the two factors, as this will be the last step to start at 0. The result is a walk of odd length 2n + 1 ending at a number > 0, and conversely any such walk has a well defined last up-step starting at 0, allowing a decomposition of the indicated kind. Thus we are led to interpret the second member 2 2n not as counting the set of all walks of length 2n, but as counting the set of walks of length 2n + 1 ending at a positive number. This is the most subtle twist: the latter set clearly has 2 2n+1 /2 = 2 2n elements as well, but is not in obvious bijection with the former set. 3 Thus in our opinion the key to understanding (1) does not lie in finding a clever bijection, but in choosing the correct interpretation of its expressions; the bijection (concatenation with an up-step interposed) then becomes a triviality.

Since the correspondence between recurrent walks and positive ones continues to hold in the presence of neutral steps, we can generalise the identity (1) to this setting. We shall allow any fixed number t of distinguished kinds of neutral steps, so that we shall recover the previous binary case for t = 0, and the ternary case (Motzkin type walks) for t = 1 (or one may consider that we are doing just the latter case, but keeping track of the number of neutral steps in the exponent of t, viewed as an indeterminate). The number R t,l of all such walks that are recurrent and of length l is then equal, due to theorem 1, to the number of positive walks of the same length ending at an even number; the parity condition is due to the fact that the basic raising operation advances the end point by 2, and the positive walks ending at an odd number similarly correspond to the almost recurrent walks ending at 1.

Given a pair consisting of a recurrent walk of length i and a positive walk of length li ending at a positive number, one can concatenate them with a single up-step inserted between them, to obtain a walk of length l + 1 ending at a positive odd number. Again one obtains, by combining all cases 0 ≤ i ≤ l, a bijection to the set of all walks of the latter type, as these can be uniquely decomposed at their last (up-)step starting at 0. Counting all walks of length l + 1 ending at a positive odd number is only slightly more difficult than in the case t = 0. Their number is half that of all walks of that length ending at an odd number, while the number of all walks of that length, and the difference between the number of those ending at even and odd numbers, are respectively given by the evaluations at X = 1 and X = -1 of (X

-1 + t + X) l+1 . Combining this one gets i+j=l R t,i R t,j = (t + 2) l+1 -(t -2) l+1 4 ( 2
)
where R t,i is the coefficient of X 0 in (X -1 + t + X) i . One has R 0,i = 0 whenever i is odd; this makes the equation trivial when t = 0 and l is odd, while for t = 0 and l = 2n one recovers equation [START_REF] André | Solution directe d'un probléme résolu par M. Bertrand[END_REF]. For arbitrary t one can convert this equation into one of generating series, summing the individual geometric series i (t ± 2) i+1 X i obtained from the right hand side to t±2-(t 2 -4)X 2 1-2tX+(t 2 -4)X 2 , and simplifying

to i∈N R t,i X i 2 = 1 1 -2tX + (t 2 -4)X 2 .
(

) 3
This leads in particular to the expression i∈N R 1,i X i = 1/ √ 1 -2X -3X 2 for the generating series of the middle trinomial coefficients. This also explains why that "diagonal" series, and its relative S for the middle binomial coefficients, not only satisfy a quadratic relation over the rational functions in X (cf. [START_REF] Stanley | Enumerative combinatorics[END_REF], theorem 6.3.3), but are actually are square roots of a rational function (cf. [loc. cit.] exercise 6.42), unlike the series for Motzkin paths and Dyck paths, although the latter satisfy simpler recurrences.

The form of equation ( 3) begs consideration of the case t = 2 as well, for which we obtain i∈N R 2,i X i = 1/ √ 1 -4X, the same generating series as S above. This leads to the question: why is the number of recurrent walks of length n with steps advancing +1 or -1 and two distinguished kinds of neutral steps the same as the number of recurrent walks of length 2n with only steps advancing +1 or -1? We leave this as an (easy) exercise to the reader.

Relation with Bertrand's ballot problem

Finally we want to make explicit a relation of our basic bijections with the famous "ballot problem" of Joseph Bertrand [START_REF] Bertrand | Solution d'un probléme[END_REF]. The problem he presented, and immediately solved, is to compute the conditional probability, given that an election between persons A and B is won by A with m out of µ votes (so 2m > µ), that during the sequential counting of the votes A has had a strict lead over B, from the counting of the first vote onwards. The answer given, 2m-µ µ , is justified by an argument counting the number P m,µ of "favourable" ballot sequences as a function of µ and m > µ 2 , stating that it satisfies the same recurrence as the binomial coefficients µ m (but without mentioning them), from which recurrence (and the implicit condition P m,2m = 0) the general formula for P m,µ can be deduced. Ballot sequences correspond straightforwardly to walks on Z, and the favourable ones are those that start with an up-step (a vote for A), and then never return to 0. Their number equals that of the positive walks of length µ -1 with m -1 up-steps; as we have seen this gives P m,µ = µ-1 m-1 -µ-1 m , and one must assume this is the general formula Bertrand hinted at. Indeed after division by µ m one obtains m µ -µ-m µ = 2m-µ µ as claimed. Apparently Joseph's solution method differs little from the one by which we initially counted positive walks. Yet he remarks that "it seems probable that so simple a result could be proved by a more direct method". This challenge is taken up by Désiré André, who in the very same issue of the Comptes Rendues proposes a solution based on a combinatorial argument [START_REF] André | Solution directe d'un probléme résolu par M. Bertrand[END_REF]. He renames the parameters as α = m and β = µm (the respective numbers of votes for A and B), and bases his argument on the observation that the proposed probability α-β α+β means that the complementary probability 2β α+β (for the cases where A did not maintain a strict lead) is due for exactly half of it to the possibility that A already failed to win the very first vote, and for the other half to the possibility that A obtains an initial lead, but fails to maintain it. To simplify our discussion we shall call these parts of the unfavourable scenario respectively "bad" and "ugly", and the favourable scenario "good". The conditional probability of the bad case, where B wins the first vote, is clearly equal to the proportion β α+β of votes cast for B; in fact André just computes this probability as the quotient α+β-1 α / α+β α . The heart of his proof is a bijection establishing equality of the numbers of bad and ugly cases.

Representing ballot sequences, or walks on Z by lattice paths (drawn as before with path segments in downward diagonal directions), the three scenarios considered are illustrated in figure 2. The equality observed by André means the following: among the lattice paths across a given rectangle, there are as many that start with a step along the short side as there are that start with a step along the long side and then later return at least once to the line bisecting the angle of the rectangle at the starting point. The number of good cases, corresponding to lattice paths from (1, 1) (which we take to be on the long side) to (α + β, αβ) that avoid the indicated line, can therefore be computed as the total number of cases minus twice the number of bad cases, corresponding Figure 2: The good, the bad and the ugly cases to lattice paths from (1, -1) to (α + β, αβ); this gives

α + β α -2 α + β -1 α = α + β -1 α -1 - α + β -1 α . (4)
This matches the formula n k -n k+1 we found for the number of positive walks of length n ending at 2kn ≥ 0, with n = α + β -1 and k = α -1.

Clearly that formula is directly related to the arguments of both Bertrand and André. Passing from it to the formula for all positive walks just requires summing over all k ≥ n 2 , which gives a telescoping sum adding up to n ⌈n/2⌉ . (The same argument shows that there are n k positive walks ending at a number that is at least 2k-n.) It may therefore be expected that there is a close relation between bijections proving respectively André's claim of parity between of bad and ugly cases, and the enumerative statement of our theorem 1.

Consider our basic raising operation, which as we recall reverses the first step of a walk that reaches the global minimum of that walk. Within the set of all walks ending at non-negative numbers, it is defined on the subset of walks that do descend at least once to a negative number, and its image is the set of walks that end at a value ≥ 2. Note that these sets are the complements of respectively the set of positive walks and the set of walks that end at 0 or 1, so that we can interpret the fact that iteration of this raising operation defines a bijection between those complements (in the opposite direction) as an instance of the "complementation principle" evoked in the introduction.

Upon restriction to the walks that end at a given value i ≥ 0, the domain of the raising operation is still limited by the requirement that the walk descend below 0, but the image is the full set of walks ending at i + 2. We can match these two sets with set of ballot sequences for the ugly and bad cases, provided we omit from those sequences the initial vote (whose outcome is fixed in either case). Thus we get walks starting at 1 respectively at -1, of length n = α+β-1, and the ending at α-β; this point is ahead of the starting point by the margin of A over B among the votes remaining after the first one, namely i = (α-1)-β in the ugly cases and α -(β -1) = i + 2 in the bad cases. Since the ugly cases now start with a one vote lead for A, the condition of subsequently losing this strict lead at least once matches the condition of descending below the starting point Figure 3: The raising operator as a starting-point shifting transformation that characterises the domain of the raising operation. Thus we now interpret the raising operation as one that fixes the end point, and shifts back the starting point by 2 units, as illustrated in figure 3. So the raising operation does indeed provide a bijection that proves the claim in André's argument.

This does not of course imply that the raising operation defines the same bijection that André did; it does not. We shall give the details of the latter bijection below, as well as the descriptions of other bijections that link the sets of bad and ugly ballot sequences, and therefore could be used instead to complete André's argument. But we first want to observe that any such bijection can be iterated to obtain a bijection between almost recurrent and positive paths: this is not a particularity of the raising operation. Proposition 3. Let a bijection f be given that maps ugly ballot sequences to bad ones, without changing the number of votes for either candidate. One can then bijectively map the set of non-bad ballot sequences in which A has a final margin of 1 or 2 votes over B to arbitrary good ballot sequences of the same length, by iterating the following step as long as the ballot sequence is ugly: apply f to change it into a bad sequence, then replace the initial vote for B by one for A.

Proof. Termination is ensured since A gains one vote at each iteration, and bijectivity of the resulting correspondence follows immediately from that of f . One may view the proposition as a mere instance of the complementation principle, within the set of all ballot sequences starting with a vote for A and resulting in a victory for A. In fact, this shows that the hypothesis of not changing the number of votes for either candidate is superfluous, as long as A still wins after applying f ; but without it one would not have such a good upper bound for the number of iterations required as one has with the hypothesis, namely the initial number of votes for B. From the bijection obtained by this iteration, an alternative proof for the enumerative statement of our theorem 1 can be deduced by removing the initial vote (for A) from each sequence. Bijections f as in the proposition are often naturally thought of as acting on lattice paths, going from the origin by downwards diagonal steps to a common end point (n, i), with i ≥ 0; in this point of view the change of the initial vote (back) into one for A done at the end of each iteration shifts the whole remaining path to the right. It might in some cases be more transparent to present the iteration instead as involving a move of the origin to the left at each step.

It is clear that like ugly ones, bad ballot sequences must reach a point where the votes for A and B are in balance. This circumstance provides an occasion, when seeking a bijection f as in the proposition, to focus on the sequences up to this point of equality, and leave their remainders unchanged. Moreover the most obvious way to see that there are as many sequences of a given length ending in equality, but with A ahead of B at all intermediate times, as there are with B similarly ahead of A, is to simply interchange the roles of A and B. In terms of lattice paths this amounts to reflecting their part up to the first encounter of the vertical line through the origin, which is the symmetry axis with respect to A and B, in that axis. Using the resulting bijection is known as the "reflection method" for solving the ballot problem. Surprisingly, and in spite of the fact that it is often attributed to him, the reflection method is not what André used to complete his proof either (see [START_REF] Renault | Lost (and Found) in Translation: Andrés Actual Method and Its Application to the Generalized Ballot Problem[END_REF] for details about the intriguing history of this problem). So let us finally describe the bijection he did define.

To transform an ugly sequence into a bad one, one may split the former sequence just before the vote where it turns ugly (the vote for B after which the initial lead of A is levelled); the two parts of the sequence are then concatenated in the opposite order. The result clearly has the same distribution of votes, and is bad since it starts with a vote for B. That the operation is bijective follows from the fact that the initial vote for A in the ugly sequence has become the last of the votes for A in the bad sequence to make the margin of A over B attain its ultimate value; it can therefore be located in the result, and the cyclic rearrangement of votes reversed. If one considers the sequences without their initial vote, as is more practical for the purpose of iteration, then the description changes slightly: one should remove the first vote that gives B a lead over A, and concatenate the remaining parts of the sequence in opposite order with a vote for A inserted in between. Curiously the description André originally gave includes the initial vote for A in the ugly sequence but maps to a bad sequence deprived of its initial vote for B, so his recipe is: remove the offending vote, and combine the remaining sequences in the opposite order.

It appears there is ample choice for a bijection proving André's claim. In fact, it is not hard to find more bijections, as variations of the reflection method. In the lattice path view, one is not obliged to take the first visit of the axis as the point up to which the reflection is applied (unless it is the unique visit): one could equally well choose say the second visit (if possible), or the last one; indeed one could fix any rule that depends only on properties of the path that are unchanged by the reflection. Alternatively, reflection in the axis is not the only way to map Dyck paths bijectively to those staying at the opposite side of the axis: central symmetry with respect to the midpoint on the axis works as well; this corresponds to reversing the order of counting votes rather than changing individual votes. In this case, unlike for the reflection method, one must insist on transforming only the part up to the first encounter of the axis, to ensure that then result corresponds to a sequence starting with a vote for B.

By our proposition, each of these bijections gives rise to a bijection between (almost) recurrent walks and positive walks of the same length. We conclude this note by comparing the various possibilities with respect to the transparency of the resulting bijection. As indicator we consider understanding the number of iterations required to turn a given walk into a positive walk. It is clear that this number will equal half the value of the ending point of that positive walk (rounded down in the odd-length case), and so it will in all cases define a statistic with values in {0, 1, . . . , ⌊ n 2 ⌋} on the set of (almost) recurrent paths of length n. Moreover this statistic will have the same distribution as the "half the ending value rounded down" statistic has on positive walks of length n, namely n k -n k-1 instances for the value k -⌈ n 2 ⌉ ≥ 0. For the bijection of theorem 1, iterating the raising operation, we have seen that this statistic is just the depth of the walk (minus the value of its global minimum), which is easily read off.

In contrast, finding the number of iterations required for a given walk when using the bijection given by the reflection method is not at all easy; as far as we can see it requires essentially simulating the entire iteration process. The reason for this difficulty is that the part of the walk affected by each successive reflection might be either smaller or larger than for the previous reflection, and as a result, computing where a given path segment will end up after a certain number of iterations becomes a somewhat messy affair.

This difficulty is present also for the variations of the reflection method we indicated, with one exception: if we systematically reflect the largest possible part of the path, namely up to the last encounter of the axis, then successive iterations are guaranteed to affect ever smaller parts of the path. We can then deduce the following computation of the number of iterations required for this case: trace the walk (as before taken to not include a step for the initial vote, and to start at 0) backwards in time, seeking first the last visit to -1 (if any), then the preceding visit to 1, then the preceding visit to -1, and so on alternatingly until no visit of the indicated kind remains; the requested number is the number of visits found. For what it's worth, we formulate the fact that this statistic has the mentioned distribution; this is actually not too hard to see directly. 2 ⌉+d walks on Z of length n starting at 0 and ending at n mod 2 ∈ {0, 1} that make at least d alternating visits to 1 and -1, the last of which is a visit to -1; the number of such walks for which d is the length of the longest such sequence of visits is

n ⌈ n 2 ⌉+d - n ⌈ n 2 ⌉+d+1
. For André's original method, we find that the number of iterations required is the same as when using the raising operation, namely the depth of the walk. Indeed each iteration decreases the depth by 1, since the part of the sequence moved to the end corresponds to a Dyck path, and the following down-step is removed; coming after the absolute minimum is reached, the additional up-step that is inserted does not affect the depth. In fact the downs-steps removed in successive iterations are the same ones as those that iteration of the raising operation would change into up-steps, although the latter would proceed in the opposite (rear to front) order. Indeed it is easy to describe the final walk obtained by iteration using André's bijection in terms of the one of theorem 1: from the latter walk remove the last of the (up-)steps that were obtained by reversing down-steps, and combine the remaining parts of the walk in the opposite order, separated by an up-step. This close relation is remarkable, as it seems unlikely that this kind of iteration was of any concern to André. In conclusion, although one can mechanically transform bijective solutions to the ballot theorem into alternative bijections for our theorem 1, this turns the more obvious solutions (notably the reflection method) into rather opaque bijections. In contrast, the raising operation as well as André's almost forgotten original method, although less obvious in relation to the ballot problem, lead to quite transparent bijections after iteration.

Corollary 4 .

 4 Given 0 ≤ d ≤ ⌊n/2⌋, there are n ⌈ n

This is not the way Pascal drew his "Triangle Arithmetique"; he used a horizontal grid of cells and the rule "Le nombre de chaque cellule est egal à celuy de la cellule qui la precede dans son rang perpendiculaire, plus à celuy de la cellule qui la precede dans son rang parallele."[START_REF] Pascal | Traité du triangle Arithmetique, avec quelques autres petits traitez sur la mesme matiere[END_REF]

Bijections between these sets can be found, but do not add much understanding to the obvious fact that their numbers agree. One such bijection uses by cut-and-paste involving two unequal size parts: interpreting walks as ballot sequences as in the next section, one can map a sequence of length 2n + 1 in which A beats B to an arbitrary one of length 2n, by singling out and removing one particular vote (the first or the last one are obvious choices); if it is a vote for A then the remaining sequence (weakly favourable for A) is returned, and otherwise its complement (all votes inverted) is returned, which is strictly favourable for B.

* Partially supported by NSF grant DMS-0554278


Konstantin Avrachenkov
email: k.avrachenkov@sophia.inria.fr

Sreenath Ramanath
email: sreenath.ramanath@sophia.inria.fr

Keywords: Resource allocation, Multiscale fairness, α-fairness, T -scale fairness, Wireless networks

Fair resource allocation is usually studied in a static context, in which a xed amount of resources is to be shared. In dynamic resource allocation one usually tries to assign resources instantaneously so that the average share of each user is split fairly. The exact denition of the average share may depend on the application, as dierent applications may require averaging over dierent time periods or time scales. In this paper we address the question of dening and computing resource allocation in such situations. We examine how the constraints on the averaging durations impact the amount that each user gets.

Équité a plusieurs échelles de temps et ses applications dans l'allocation dynamique des ressources dans les réseaux sans l Résumé : L'allocation équitable des ressources est étudiée d'habitude dans un contexte statique, où une quantité xe de ressource doit être partagée. Dans l'allocation dynamique des ressources, on a comme objectif de contrôler l'allocation instantanée de manière à ce que la quantité moyenne soit distribuée équitablement. La dénition exacte de la notion de quantité moyenne pourrait dépendre de l'application, surtout que des application diérentes pourraient avoir des contraintes diérentes sur la durée des périodes sur lesquelles on va moyenner . Nous allons étudier quel est l'impact de ces contraintes (sur les périodes pour calculer les moyennes), sur la quantité de ressource que chaque usager obtient.

Mots-clés : allocation des ressources; équité multi-échelle; alpha-équité; équité T-échelle; réseaux sans-l.

Introduction

Let us consider some set S of resource that we wish to distribute among I users by assigning user i a subset S i of it. We shall be interested in allocating subsets of the resource fairly among the users. The set S may actually correspond to one or to several resources. We shall consider standard fairness criteria for sharing the resources among users. We shall see, however, that the denition of a resource will have a major impact on the fair assignment.

We associate with each user i a measurable function x i that maps each point in S to some real number. Then, we associate with each i a utility u i which maps all measurable subsets S i to the set of real numbers. We shall say that S is a resource if u i (S i ) can be written as

u i (S i ) = f Si x i (s)ds
for each S i ⊂ S.

As an example, consider I mobiles that wish to connect to a base station between 9h00 and 9h10 using a common channel. The time interval is divided into discrete time slots whose number is N . Assume that the utility for each mobile s of receiving a subsets N i of slots depend only on the number of slots N i it receives. Then the set of N slots is considered to be a resource.

Next assume that if mobile i receives the channel at time slot t then it can transmit at a throughput of X i t . Assume that the utility of user i is a function of the total throughput it has during this fraction of an hour. Then again the N slots are considered as a resource.

We adopt the idea that fair allocation should not be dened in terms of the object that is split but in terms of the utility that corresponds to the assignments. This is in line with the axiomatic approach for dening the Nash bargaining solution for example. With this in mind, we may discover that the set of N slots cannot always be considered as a resource to be assigned fairly. Indeed, a real time application may consider the N slots as a set of n resources, each containing B = N/n consecutive slots. A resource may correspond to the number of time slots during a period of 100 msec. The utility of the application is dened as a function of the instantaneous rate, i.e. the number of slots it receives during each period of 100 msec. (With a playout buer that can store 100 msec of voice packets, the utility of the mobile depends only on how many slots are assigned to it during 100 msec and not which slots are actually assigned to it.) What is the impact on data transfer applications of splitting the resource of N slots into B smaller resources? We shall show that allocating fairly each of these B resources results in performance degradation for the data transfer applications. This raises the question of how to dene fair assignment when the very notion of a resource varies from one user to another.

Another example where this question arises is frequency allocation. Assume that frequency bandwidth needs to be split between users, who bid for N carriers, each of bandwidth b. There may be users who need carriers of bandwidth mb. They can make use of a carrier only if they receive a set of m consecutive carriers. For these users, a resource may correspond to the set of N/m group of carriers, each of which containing m consecutive carriers.

Related work

Our work is based on the α-fairness notion introduced by Mo and Walrand [START_REF] Mo | Fair End-to-end Window-based Congestion Control[END_REF]. This notion provides a continuum of fairness denitions through the real parameter α and it includes various known fairness concepts that are obtained for some specic values of the real parameter α (the max-min fairness, the proportional fairness and the harmonic fairness). This, as well as other fairness notions can be dened through a set of axioms, see [START_REF] Lan | An Axiomatic Theory of Fairness for Resource Allocation[END_REF]. This paper is inspired by several papers which already observed or derived fairness at dierent time-scales [START_REF] Altman | Fairness in MIMD Congestion Control Algorithms[END_REF][START_REF] Altman | Generalized Alpha-Fair Resource Allocation in Wireless Networks[END_REF][START_REF] Altman | Alpha-Fair Resource Allocation under Incomplete Information and Presence of a Jammer[END_REF][START_REF] Bredel | Understanding Fairness and its Impact on Quality of Service in IEEE 802[END_REF][START_REF] Ramaiyan | Fixed Point Analysis of Single Cell IEEE 802.11e WLANs: Uniqueness and Multistability[END_REF]. However, we would like to mention that the T -scale fairness (a unifying generalization of long-and short-term fairness) and multiscale fairness are new concepts introduced in the present work.

Structure of the paper

The paper is organized as follows: In the next Section 2 we introduce a resource sharing model which is particularly suitable for wireless network applications. In Section 2 we also dene several fairness criteria, illustrate them by examples and prove theoretical properties of the introduced fairness criteria. In Section 3 we derive explicit formulae for instantaneous α-fairness in the case of linear resources. The case of linear resources corresponds to the frequency as a resource in wireless networks. In Sections 4 and 5 we apply dierent fairness criteria to spectrum allocation in fading channels and to indoor-outdoor scenario, respectively. Section 6 concludes the paper and provides avenues for future research.

Resource Sharing model and dierent fairness denitions

Consider n mobiles located at points x 1 , x 2 , ..., x n , respectively. We assume that the utility U i of mobile i depends on its location x i and on the amount of resources s i it gets. Let S be the set of assignments; an assignment s ∈ S is a function from the vector x to a point in the n-dimensional simplex. Its ith component, s i (x) is the fraction of resource assigned to mobile i. Denition 2.1 (α-fair assignment) An assignment s is α-fair if it is a solution of:

Z(x, α) := max s i Z i (s i , x i , α) s.t. i s i = 1, s i ≥ 0∀i = 1, ..., n (1)
INRIA where,

Z i (x i , s i , α) := (U i (x i , s i )) 1-α 1 -α for α = 1.
For α = 1 we dene

Z i (x i , s i , α) := log(U i (x i , s i ))
We shall assume throughout that U i is non-negative, strictly increasing and is concave in s i . Then for any α > 0, Z i (x i , s i , α) is strictly concave in s i . We conclude that Z(x i , s i , α) is strictly concave in s for any α > 0 and therefore there is a unique solution s * (α) to (1). Denition 2.2 (Mo and Walrand [START_REF] Mo | Fair End-to-end Window-based Congestion Control[END_REF]) We call Z i (s i , •, α) the fairness utility of mobile i under s i , and we call Z(s, •, α) the instantaneous degree of α-fairness under s.

In applications, the state X will be random, so that the instantaneous amount of resource assigned by an α-fair allocation will also be a random variable. Thus, in addition to instantaneous fairness we shall be interested in the expected amount assigned by being fair at each instant. Denition 2.3 We call E[Z(s, X, α)] the expected instantaneous degree of α-fairness under s.

In Section 2.1 we introduce the expected long-term fairness in which the expected amount of resource is assigned fairly. Denition 2.4 We say that a utility is linear in the resource if it has the form:

U i (x i , s i ) := s i q i (x i ).
For example, consider transmission between a mobile source and a base station, and assume (i) that the base station is in the origin (x = 0) but at a height of one unit, whereas all mobiles are on the ground and have height 0. Thus, the distance between the base station and a mobile located on the ground at point x is 1 + ||x|| 2 .

(ii) that the Shannon capacity can be used to describe the utility. If the resource that is shared is the frequency then the utility has the linear form:

U (C, x) := Cq(x)
where q(x) = log 1 + P (x 2 + 1) -β/2 σ 2

Note: if the power and not the frequency, were taken to be the resource then we would not obtain the linear form of the resource.

In the linear case, we write Z i as:

Z i (s, x, α) := s 1-α i v i (x), v i := (q i (x i )) 1-α 1 -α 2.
1 Fairness over time: Instantaneous Versus Long term α-fairness

Next we consider the case where x i (t), i = 1, ..., n, may change in time. Denition 2.5 We dene an assignment to be instantaneous α-fair if at each time t each mobile is assigned a resource so as to be α-fair at that instant.

Consider the instantaneous α-fair allocation and assume that time is discrete. We thus compute the instantaneous α-fair fair assignment over a period of T slot as the assignment that maximizes (for α = 1)

n i=1 (U i (x i (t), s i (t))) 1-α 1 -α .
for every t = 1, ..., T . This is equivalent to maximizing

T t=1 n i=1 (U i (x i (t), s i (t))) 1-α 1 -α . (2)
For α = 1 the same is true but where we replace

(U i (x i (t), s i (t))) 1-α 1 -α by log[U i (x i (t), s i (t))]
We make the following surprising observation: The optimization problem (2) corresponds to the α-fair assignment problem in which there are nT players instead of n players, where the utility of player i = kn + j (k = 0, ..., T -1, j = 1, ..., n) is dened as

U i (x i , s i ) = U j (x j (k + 1), s j (k + 1))
. Thus the expected instantaneous fairness criterion in the stationary and ergodic case regards assignments at dierent time slots of the same player as if it were a dierent player at each time slot! Note that when considering the proportional fair assignment, then the resulting assignment is the one that maximizes

n i=1 T t=1 U i (x i (t), s i (t))
Denition 2.6 Assume that the state process X(t) is stationary ergodic. Let λ i be the stationary probability measure of X(0). The long term α-fairness index of an assignment INRIA s ∈ S of a stationary process X(t) is dened as

Z λ (s) := n i=1 Z i λ (s)
where

Z i λ (s) = E λ [U i (X i (0), s i (X(0)))] 1-α 1 -α An assignment s is long-term α-fair if it maximizes Z λ (s) over s ∈ S.
As we see, instead of attempting to have a fair assignment of the resources at every t, it is the expected utility in the stationary regime that one assigns fairly according to the the long-term fairness. Under stationarity and ergodicity conditions on the process X(t) this amounts in an instantaneous assignment of the resources in a way that the time average amount allocated to the users are α-fair.

Fairness over time: T -scale α-fairness

Next we dene fairness concepts that are in between the instantaneous and the expected fairness. They are related to fairness over a time interval T . Either continuous time is considered or discrete time where time is slotted and each slot is considered to be of one time unit. Below, we shall understand the integral to mean summation when ever time is discrete.

Denition 2.7

The T -scale α-fairness index of an assignment s ∈ S is dened as

Z T (s) := n i=1 Z i T (s)
where

Z i T = 1 T T 0 U i (X i (t), s i (X(t)))dt 1-α 1 -α The expected T -scale α-fairness index is its expectation. An assignment s is T -scale α-fair if it maximizes Z T (s) over s ∈ S.

Denition 2.8

The T -scale expected α-fairness index of an assignment s ∈ S is dened as

Z T (s) := n i=1 Z i T (s)
where

Z i T = 1 T T 0 E[U i (X i (t), s i (X(t)))]dt 1-α 1 -α
We shall consider the following simple example of 2-scale fairness

Example 1 Consider two time slots and two mobile stations. To whoever the rst time slot will be allocated, that mobile would send or receive 25 units. At the second slot, a rate of 5 (resp. 10) units will be used if the slot is assigned to mobile 1 (resp. 2). We make the following observations. By [i,j] we shall denote the allocation that assigns slot 1 to mobile i and slot 2 to mobile j. The allocation [START_REF] Altman | Fairness in MIMD Congestion Control Algorithms[END_REF][START_REF] Altman | Generalized Alpha-Fair Resource Allocation in Wireless Networks[END_REF] maximizes the global utility and moreover, the α-fair 2-scale utility for any α.

Thus, we observe that the α-assignment is not monotone: The player with larger utilities received less at the α-fair utility, for all values of α! Example 2 (Example 1 continued) We now change a single utility in the last example: assume that if mobile 2 receives the rst slot then it earns 10 2 units.

(i) Now the global optimal solution is the assignment [START_REF] Altman | Generalized Alpha-Fair Resource Allocation in Wireless Networks[END_REF][START_REF] Altman | Generalized Alpha-Fair Resource Allocation in Wireless Networks[END_REF].

(ii) The proportional fair solution (α = 1) is [2,1].
(iii) The maxmin fair assignment is [START_REF] Altman | Fairness in MIMD Congestion Control Algorithms[END_REF][START_REF] Altman | Generalized Alpha-Fair Resource Allocation in Wireless Networks[END_REF].

We depict in Figure 1 the performance index of the assignments [START_REF] Altman | Fairness in MIMD Congestion Control Algorithms[END_REF][START_REF] Altman | Generalized Alpha-Fair Resource Allocation in Wireless Networks[END_REF] and [START_REF] Altman | Generalized Alpha-Fair Resource Allocation in Wireless Networks[END_REF][START_REF] Altman | Fairness in MIMD Congestion Control Algorithms[END_REF]. We see that the max-min fair assignment [2,1] is 2-scale α-fair for all α larger than 1.36, whereas the assignment [START_REF] Altman | Fairness in MIMD Congestion Control Algorithms[END_REF][START_REF] Altman | Generalized Alpha-Fair Resource Allocation in Wireless Networks[END_REF]

is α fair for α ∈ [1, 1.36].
For α < 1 the two best assignments are [START_REF] Altman | Generalized Alpha-Fair Resource Allocation in Wireless Networks[END_REF][START_REF] Altman | Fairness in MIMD Congestion Control Algorithms[END_REF] and [START_REF] Altman | Generalized Alpha-Fair Resource Allocation in Wireless Networks[END_REF][START_REF] Altman | Generalized Alpha-Fair Resource Allocation in Wireless Networks[END_REF]. The former is optimal over α ∈ [0.17, 1] and the latter over α ∈ [0, 0.17]. This is seen from Figure 2.

Assume that the state processes is stationary ergodic. Then for any assignment s ∈ S we would have by the Strong Law of Large Numbers:

lim T →∞ 1 T T 0 U i (X i (t), s i (X(t)))dt = E λ [U i (X i (0), s i (X(0)))]
P-a.s. Hence, for every i and s, we have P-a.s.

lim T →∞ Z i T (s) = lim T →∞ 1 T T 0 U i (X i (t), s i (X(t)))dt 1-α 1 -α = (E λ [U i (X i (0), s i (X(0)))]) 1-α 1 -α = Z i T (s).
Assume that U i is bounded. Then Z i T is bounded uniformly in T . The bounded convergence then implies that lim For any > 0, s * is an -optimal assignment for the T -scale criterion for all T large enough.

T →∞ E[Z i T (s)] = Z i T (s). (3)
For any > 0, s * (T ) is an -optimal assignment for the long term fairness for all T large enough.

Proof. According to [START_REF] Tidball | Continuity of optimal values and solutions for control of Markov chains with constraints[END_REF], any accumulation point of s * (T ) as T → ∞ is an optimal solution to the problem of maximizing Z T over S. Due to the strict concavity of Z T in s it has a unique solution and it is coincides with any accumulation point of s * (T ). This implies the rst statement of the theorem. The other statements follow from Appendices A and B in [START_REF] Tidball | Continuity of optimal values and solutions for control of Markov chains with constraints[END_REF].

Fairness over dierent time scales: Multiscale fairness

We consider real time (RT) and non-real time (NRT) trac. Resource allocation policy for RT trac is instantaneous-fair, while for the NRT trac, it is expected-fair. The available resources are divided amongst the RT and NRT trac so as to guarantee a minimum quality of service (QoS) requirement for the RT trac and to keep service time as short as possible for the NRT trac.

The real time trac would like the allocation to be instantaneously α-fair. For α > 0, this guarantees that at any time it receives a strictly positive allocation.

The non-real time trac does not need to receive at each instant a positive amount of allocation. It may prefer the resources to be assigned according to the T -scale α-fair assignment where T may be of the order of the duration of the connection. Moreover, dierent non real time applications may have dierent fairness requirements. For instance, bulk FTP transfer can prefer fairness over time scale longer than a time scale for some streaming application.

In order to be fair, we may assign part (say half ) of the resource according to the instantaneous α-fairness and the rest of the resources according to the T -scale α-fairness.

We thus combine fairness over dierent time scales.

We may now ask how to choose what part of the resource would be split according to the instantaneous assignment and what part according to the T -scale assignment. We propose to determine this part using the same α-fair criterion.

Specically we dene the multiscale fairness as follows:

Denition 2.9 The multiscale α-fairness index of an assignment s ∈ S is dened as

Z T1,...,Tn (s) := n i=1 Z i Ti (s)
where

Z i Ti = 1 Ti Ti 0 U i (X i (t), s i (X(t)))dt 1-α 1 -α INRIA
The expected multiscale α-fairness index is its expectation. An assignment s is multiscale α-fair if it maximizes Z T1,...,Tn (s) over s ∈ S. We also say that multiscale α-fair assignment is (T 1 , ..., T n )-scale fair assignment.

Example 3 Let us consider an example of multiscale fairness. Say, we have in total N time slots. The allocation happens in a bundle of 6 slots, such that, either we allocate all of it to an outdoor user located at x 1 or fair share them amongst 3 indoor users located at (y 1 , y 2 , y 3 ) with y i ∈ (0, L), with any user getting two consecutive slots. Now the question is "Given that we fair-share among the indoor users, how do we fair share between the outdoor and the indoor users?".

In this example, we assume any user gets a throughput q ∈ [0, 1]. Let {U 1 , U 2 }, represent the utility of user 1 and sum utility of users 2-4 and let {T 1 , 1-T 1 } represent their respective assignment of resources. Now, utility of user 1,

U 1 (T 1 ) = 6T 1 q 1 (x 1 ).
Let s = {s 1 , s 2 , 1 -s 1 -s 2 } represent the assignment of resources for the indoor users. Then, utility of users 2 -4 is

u 2 (T 1 , s) = 6s 1 (1 -T 1 )q 2 (y 2 ), u 3 (T 1 , s) = 6s 2 (1 -T 1 )q 3 (y 3 ) and u 4 (T 1 , s) = 6(1 -s 1 -s 2 )(1 -T 1 )q 4 (y 4 ) Now the α-fair share s * = {s * 1 , s * 2 , 1 -(s * 1 -s *
2 )} is given by,

s * = arg max s 4 i=2 E[u i (T 1 , s)] 1-α1 1 -α 1
The sum utility of users 2 -4 is,

U 2 (T 1 ) = 4 i=2 6 si * (1 -T 1 )q i (y i )
The α-fair share between the outdoor and indoor users is,

T * 1 = arg max T1 E [U 1 (T 1 )] 1-α + E [U 2 (1 -T 1 )] 1-α 1 -α RR n°7382
3 Instantaneous α-fairness for linear resources

In the case of linear resources the instantaneous α-fairness has a nice explicit expression. Theorem 3.1 (i) The α-fair share is given by

s * i = v i (x i ) 1/α j v j (x j ) 1/α = q i (x i ) 1/α-1 j q j (x j ) 1/α-1
(ii) The utility for mobile i under the fair assignment is then

U i (s * , x) = v i (x i ) 1/α j v j (x j ) 1/α q i (x i ) = q i (x i ) 1/α j q j (x j ) 1/α-1
(iii) The optimal value Z is given by

Z = 1 1 -α i q i (x i ) 1+1/α j q j (x j ) 1/α 1-α
Proof. We relax the constraint and use KKT condition. s is optimal if and only if there is some λ > 0 such that s maximize L λ s.t. s i ≥ 0 for all i, where

L λ = i s 1-α i v i + λ(1 - i s i )
Equating the derivative w.r.t. s i to zero gives

s -α i v i (x i ) = λ 1 -α so that s i = 1 -α λ v i (x i ) 1/α
Since the sum of s i is 1, we conclude that

λ 1 -α =   j v j (x j ) 1/α   α
Substituting in the previous equation yields (i), which then implies the rest.

Example 4 Consider as an example a path loss β = 2 and let the base station be located one unit above the mobiles. We assume that q i (x) is proportional to the attenuation between the mobile and the base station: q i (x) = c i q(x) where q(x) = (1 + x 2 ) -1/2 . For β = α = 2 we have

s * i (x) = c -1/2 i (1 + x 2 i ) -1/2 j c -1/2 j (1 + x 2 j ) -1/2 . INRIA Furthermore, U i (s * , x) = s * i (x)q i (x i ) = c 1/2 i (1 + x 2 i ) j c -1/2 j 1 + x 2 j .
4 Application to spectrum allocation in random fading channels

We consider two users: fast-changing user and slowly-changing user. The users' channels are modeled by the Gilbert model. The users can be either in a good or in a bad state. The dynamics of the fast-changing user is described by a Markov chain {Y 1 (t)} t=0,1,... with the following transition matrix

P 1 = 1 -α 1 α 1 β 1 1 -β 1 .
Its stationary distribution is given by

π 1 = β1 α1+β1 α1 α1+β1
.

The slowly-changing user is described by a Markov chain {Y 2 (t)} t=0,1,... with the following transition matrix

P 2 = 1 -α 2 α 2 β 2 1 -β 2 .
Its stationary distribution is given by

π 2 = β2 α2+β2 α2 α2+β2
.

Note that the parameter does not have an eect on the stationary distribution but it inuences for how long the slowly-changing user stays in some state. The smaller , the more seldom the user changes the states. If we choose α 1 = α 2 and β 1 = β 2 , then the fast-changing user and the slowly-changing user have the same stationary distribution.

We assume that state 1 is a bad state and state 2 is a good state. When the fast-changing user is in the bad state, its channel gain coecient is h 11 and when the fast-changing user is in the good state, its channel gain coecient is h 12 . Of course, we have h 11 < h 12 . Thus, the achievable throughputs in dierent states are given by U 11 = s 11 q 11 = s 11 log 1 +

h 11 P 1 σ 2 , U 12 = s 12 q 12 = s 12 log 1 + h 12 P 1 σ 2
where P 1 is the power applied by the fast-changing user.

RR n°7382

Similarly, for the slowly-changing user we associate with the bad state (state where P 2 is the power applied by the slowly-changing user.

First, we would like to analyze T -scale fairness and to see the eect of the time scale on the resource allocation. Specically, we consider the following optimization criterion

2 i=1 1 1 -α 1 T T t=0 U i (t) 1-α → max s1,s2 (4)
with U i (t) = s i (t)q i,Yi(t) and s 1 (t) + s 2 (t) = 1.

Let us consider several options for the time horizon T : Instantaneous fairness. If we take T = 1 we obtain the instantaneous fairness. Namely, the criterion (4) takes the form

1 1 -α U 1-α 1 (0) + U 1-α 2 (0) → max s1,s2
The solution of the above optimization problem (follows from Theorem 1) is given by

s i (0) = q (1-α)/α i,Yi(0) q (1-α)/α 1,Y1(0) + q (1-α)/α 2,Y2 (0)
This allocation results in the following expected throughputs

θ 1 = i,j q 1/α 1,i q (1-α)/α 1,i + q (1-α)/α 2,j π 1,i π 2,j , θ 2 = i,j q 1/α 2,j q (1-α)/α 1,i + q (1-α)/α 2,j π 1,i π 2,j . (5)
Mid-term fairness. Let us take the time horizon as a function of the underlying dynamics time parameter , that is T = T ( ), satisfying the following conditions: (a) T ( ) → ∞ and (b) T ( ) → 0. The condition (a) ensures that 1 T ( )

T ( ) t=0 1{Y 1 (t) = i} → π 1,i , as → 0, INRIA and the condition (b) ensures that 1 T ( ) T ( ) t=0 1{Y 2 (t) = i} → δ Y2(0),i , as → 0.
This follows from the theory of Markov chains with multiple time scales (see e.g., [START_REF] Filar | Cesaro limits of analytically perturbed stochastic matrices[END_REF]). It turns out to be convenient to take the following notation for the resource allocation: We denote by s(t) the allocation for the fast-changing user and by 1-s(t) the resource allocation for the slowly-changing user. Thus, we have s 1 (t) = s(t) and s 2 (t) = 1 -s(t). We denote by si,

j = E[s(t)|Y 1 (t) = i, Y 2 (t) = j].
We note that since the fast-changing user achieves stationarity when T ( ) → ∞ we are able to solve (4) in stationary strategies. Then, the criterion (4) takes the form

1 1 -α (π 1,1 q 1,1 s1,Y2(0) + π 1,2 q 1,2 s2,Y2(0) ) 1-α + ((1 -π 1,1 s1,Y2(0) -π 1,2 s2,Y2(0) )q 2,Y2(0) ) 1-α → max s1,Y 2 (0) , s2,Y 2 (0)
The above nonlinear optimization problem can be solved numerically. The expected throughputs in the mid-term fairness case are given by

θ 1 = (π 1,1 q 1,1 s1,1 + π 1,2 q 1,2 s2,1 )π 2,1 + (π 1,1 q 1,1 s1,2 + π 1,2 q 1,2 s2,2 )π 2,2 θ 2 = (1 -π 1,1 s1,1 -π 1,2 s2,1 )q 2,1 π 2,1 + (1 -π 1,1 s1,2 -π 1,2 s2,2 )q 2,2 π 2,2 (6)
Long-term fairness. In the case of long-term fairness we set T = ∞ which results in the following criterion

1 1 -α E[U 1 ] 1-α + E[U 2 ] 1-α → max s1,s2
Due to stationarity, we can solve the above optimization problem over sequences in stationary strategies. Namely, we have the following optimization problem

1 1 -α ((π 1,1 π 2,1 s1,1 + π 1,1 π 2,2 s1,2 )q 1,1 + (π 1,2 π 2,1 s2,1 + π 1,2 π 2,2 s2,2 )q 1,2 ) 1-α + ((π 2,1 -π 1,1 π 2,1 s1,1 -π 1,2 π 2,1 s2,1 )q 2,1 + (π 2,2 -π 1,1 π 2,1 s1,1 -π 1,2 π 2,2 s2,2 )q 2,2 ) 1-α ] → max s1,1, s1,2, s2,1, s2,2
The expected throughputs in the long-term fairness case are given by

θ 1 = (π 1,1 π 2,1 s1,1 + π 1,1 π 2,2 s1,2 )q 1,1 + (π 1,2 π 2,1 s2,1 + π 1,2 π 2,2 s2,2 )q 1,2 θ 2 = (π 2,1 -π 1,1 π 2,1 s1,1 -π 1,2 π 2,1 s2,1 )q 2,1 + (π 2,2 -π 1,1 π 2,1 s1,1 -π 1,2 π 2,2 s2,2 )q 2,2 (7)
Let us also consider the expected instantaneous fairness which is given by the criterion

1 1 -α E[U 1-α 1 (t)] + E[U 1-α 2 (t)] → max s1,s2
which is equivalent to

1 1 -α   ij π 1,i π 2,j 1 0 (sq 1,i ) 1-α dF ij (s) + ij π 1,i π 2,j 1 0 ((1 -s)q 2,j ) 1-α dF ij (s)   → max Fij where F ij (s) is the distribution for s(t) conditioned on the event {Y 1 (t) = i, Y 2 (t) = j}.
The above criterion is maximized by

F ij (s) = 0, if s < q (1-α)/α 1,i /(q (1-α)/α 1,i + q (1-α)/α 2,j ), 1, if s ≥ q (1-α)/α 1,i /(q (1-α)/α 1,i + q (1-α)/α 2,j
).

Thus, we can see that the expected instantaneous fairness criterion is equivalent to instantaneous fairness. Let us consider a numerical example. The parameters are given in Table 1. We consider three typical cases. For these three cases, we plot the expected throughput of the mobiles for various fairness criteria (see Figures 345). The rst case corresponds to the symmetric scenario. Since in this scenario the users have the same stationary distributions and the same conditional Shannon capacities, the expected throughputs are the same when we use either instantaneous fairness criterion or long-term fairness criterion. Interesting, in the long-term fairness case, both users experience degradation in throughput when α increases.

In the case of mid-term fairness, the expected throughput of the fast-changing user is higher as in the mid-term fairness criterion the utility of the fast-changing user is the α-fairness function of the expected throughput. In the second case, the fast-changing user has in general better channel conditions. In this case, dierent fairness criteria provide dierent resource allocation. We observe that instantaneous and mid-term fairness allocations are more sensitive with respect to the parameter α than the long-term fairness allocation. In the third scenario the slowly-changing user (user 2) is more often in the good channel state INRIA

User-1 3/0.9 9/0.1

User-2 1/0.3 7/0.7 than the fast-changing user (user 1). Now, for all the criteria the slowly-changing user has better expected throughput.

Next, let us consider multiscale fairness over time. Specically, (T 1 , T 2 )-scale fairness is dened by the following criterion

1 1 -α   1 T 1 T1 t=0 U 1 (t) 1-α + 1 T 2 T2 t=0 U 2 (t) 1-α   → max s1,s2
In this particular example, there are 6 possible combinations of dierent time scales. It turns out that in this example only the (1, ∞)-scale fairness gives a new resource allocation. The other combinations of time scales reduce to some T -scale fairness. Thus, let us rst consider the multiscale fairness when we apply instantaneous fairness to the fast-changing user and long-term fairness to the slowly-changing user. The (1, ∞)-scale fairness corresponds to the following optimization criterion

1 1 -α U 1 (0) 1-α + E[U 2 (t)] 1-α → max s1,s2
which is equivalent to The expected throughputs in the (1, ∞)-scale fairness case are given by

1 1 -α (q 1,Y1(0) (s Y1(0),1 π 2,1 + sY1(0),2 π 2,2 )) 1-α +(q 2,1 (1 -sY1(0),1 )π 2,1 + q 22 (1 -sY1(0),2 )π 2,2 ) 1-α → max sY 1 (0),1 , sY 1 (0),2 0.5 1
θ 1 = q 1,1 (s 1,1 π 1,1 π 2,1 + s1,2 π 1,1 π 2,2 ) + q 1,2 (s 2,1 π 1,2 π 2,1 + s2,2 π 1,2 π 2,2 ) θ 2 = (q 2,1 (1 -s1,1 )π 2,1 + q 22 (1 -s1,2 )π 22 )π 1,1 + (q 2,1 (1 -s2,1 )π 2,1 + q 22 (1 -s2,2 )π 22 )π 1,2 .
As we have mentioned above, the other combinations of time scales reduce to some T -scale fairness. In particular, (1, T ( ))-fairness reduces to the instantaneous fairness, (T ( ), ∞)fairness reduces to long-term fairness, and (T ( ), 1)-, (∞, 1)and (∞, T ( ))-fairness all reduce to mid-term fairness.

We also plot the expected throughputs for (1, ∞)-scale fair allocation for the numerical example with three cases (see Figures 345). We observe that in the symmetric case (1, ∞)scale fairness criterion provides an allocation which is opposite to the allocation provided by the mid-term fairness criterion. This indicates that the T -scale fairness and multiscale fairness concepts provide a versatile framework for resource allocation which takes into account the dynamics of the users. From Figures 4 and5 we conclude that multiscale fairness provide good sensitivity to the variation of the fairness parameter and good performance in expected throughput.

Coecient of variation: We compute the coecient of variation for short-term, midterm, long-term and multiscale fairness. For this, we rst compute the second moment of the throughput and then nd the ratio of the standard deviation to its mean. For any user i, the coecient of variation is

Γ i = E[θ 2 i ] E[θ i ]
In Figure 6, we plot the coecient of variation in throughput for the considered above various fairness criteria. It is very interesting to observe that except the (1, ∞)-scale fairness criterion all the other fairness criteria behave similarly with respect to the coecient of variation. Only in the case of (1, ∞)-scale fairness the coecient of variation decreases for sort-term fairness oriented user. This is a very desirable property of the multiscale fairness as a short-term fairness oriented user is typically a user with a delay sensitive application.

Application to indoor-outdoor scenario

Let Ω be the line segment [-L, L], and let there be a wall at x = 0. Assume that the base station is located just to the left the wall. Mobile 1 is at some point x ≤ 0 outdoor and user 2 remains always indoor and is located at some Y t which is uniformly distributed over [0, L]. We let q i (x) = c i q(x) with c 1 = 1 and c 2 is equal to some large xed number. Thus the presence of the wall between the base station and mobile 2 is modeled by a multiplicative attenuation by some constant c 2 . Assume that the mobility pattern of mobile 2 is uniform over the indoor part [0, L].

INRIA

We consider allocation of the fraction of time between the two mobiles.

Instantaneous Fairness

Example 4 (continued). We compute the expected utility for each user when assigning the channel so as to achieve instantaneous fairness. The expected utility for mobile 1 under the instantaneous optimal fairness s is given by

U 1 (s * , x) = s * (x)q 1 (x), where s * (x) := a a + b a := c -1/2 1 log 1 + 1 x 2 -1/2 b := c -1/2 2 log(1 + 1 L 2 ) + 2 L tan -1 (L) -1/2
Note that mobile 2 has a mobility pattern which is uniform over the indoor part [0,L] and hence its utility is given by

1 L L 0 log(1 + 1 x 2 )dx = log(1 + 1 L 2 ) + 2 L tan -1 (L), which is
the second term in the denominator.

In gure ( 7) and ( 8), we plot the scheduler and the instantaneous throughput for the indoor and outdoor user, as a function of α. We x the location of the outdoor user at x = -3, path-loss β = 3. We set L = 3 for this example. The indoor user is located at some point which is uniformly distributed over [0, L]. When the fairness index α is small, we observe that the instantaneous throughput achieved is higher as the outdoor user is located at the boundary (-L). But, as the fairness index increases, the throughput of the indoor and the outdoor user starts to converge. Notice that the scheduler starts to schedule the outdoor user more as α increases, which results in an increase in the outdoor users throughput.

Long term Fairness

Next we consider the long-term fairness. The long term allocation s ∈ S (which is a function of x and Y t ) is given by maximizing

Z(s) := 1 L L 0 dys 1 (x, y)q(x) 1-α + 1 L L 0 dyc 2 s 2 (x, y)q(y) 1-α 1 -α
Theorem 5.1 The long term α-fair policy is given by s 2 (x 2 ) = 1 for x 2 ≤ l(α) and is otherwise zero, where l(α) is the solution of the xed point equation where q(x) is a monotone decreasing function of the form x -β

l(α) = c 1-1 α 2 q(l(α)) q(x) -β(1-1 α ) 0
Proof. It is easy to see that α-fair policy has to have the form mentioned in the theorem statement. If not, for example say there exists an optimal policy which allocates mobile 2 in two disjoint intervals. Then, one can construct a better policy by shifting the right most interval to the end of the left interval and this contradicts the optimality. The optimal l(α) is obtained by dierentiating the above equation w.r.t l and equating to zero, which results in the xed point equation (L -l(α))q(x) -α q(x) -c 2 l(α) 0 q(y)dy -α q(l(α)) = 0.

Specially when q(x) = x -β then the xed point equation simplies to

l(α) = c 1-1 α 2
q(l(α)) q(x) We plot in gure (9) a numerical example to observe how l(α) varies with α for α > 1.

In this example, we consider path loss β = 2, location of outdoor user x = -2 and wall attenuation of 6 dB. We observe that as α increases, the value of l(α) monotonically decreases and starts to saturate. It is interesting to note that the indoor user is scheduled when its mobility and the fairness of resource allocation, (l(α), α), lie within the dashed region below the curve. Also, when the user exhibits higher mobility, the range of fairness applicable reduces.

Conclusion and Future Research

We have introduced T -scale fairness and multiscale fairness. The notion of T -scale fairness allows one to address in a exible manner requirements of emerging applications (like YouTube) which demand quality of service requirement between strict real time trac and best eort trac. The notion of multiscale fairness allows one to use a single optimization criterion for resource allocation when dierent applications are present in the network. We have compared the new fairness notions with previously known criteria of instantaneous and long-term fairness criteria. We have illustrated the new notions by their application in wireless networks. Specically, we have considered spectrum allocation when users with dierent dynamics are present in the system. We have demonstrated that the multiscale fairness provides a versatile framework for resource allocation. We have also considered the resource allocation in indoor-outdoor scenario and have observed how the spacial component inuences the resource scheduling under dierent fairness criteria. In the near future we plan to investigate in detail how multiscale fairness criterion allocates resources when a number of applications with dierent QoS requirements are present in the network. It is also interesting to investigate T -scale fairness in the non-stationary regime.

Figure 1 :

 1 Figure 1: Performance index of [2,1] (dashed line) and [1,2] (solid line) assignments as a function of α (horizontal axis)

Figure 2 :

 2 Figure 2: Performance index of [2,1] (dashed line) and [2,2] (solid line) assignments as a function of α (horizontal axis)

Figure 3 :

 3 Figure 3: Throughput(θ) as a function of α for instantaneous, mid-term, long-term and (1,∞)-scale fairness criteria (Case 1).

Figure 4 :

 4 Figure 4: Throughput(θ) as a function of α for instantaneous, mid-term, long-term and (1,∞)-scale fairness criteria (Case 2).

Figure 5 :

 5 Figure 5: Throughput(θ) as a function of α for instantaneous, mid-term, long-term and (1,∞)-scale fairness criteria (Case 3).

Figure 6 :

 6 Figure 6: Coecient of variation in expected throughput as a function of α for instantaneous, mid-term, long-term and (1,∞)-scale fairness criteria (Case 3).

Figure 7 :Figure 8 :

 78 Figure 7: Scheduler s * for the indoor and outdoor user with instantaneous fairness as a function of α for α > 1. Wall attenuation 6 dB, path-loss β = 3, position of outdoor user x = -3.

  l ) where s l 2 (x) = 1 for {x ≤ l}.

Figure 9 :

 9 Figure 9: l(α) for long-term fairness as a function of α (α > 1) and wall attenuation of 6 dB ,path-loss β = 2, position of outdoor user = -2.

  1) the channel gain h 21 and with the good state (state 2) the channel gain h 22 . Again we have h 21 < h 22 , and the achievable throughputs in dierent states are given by U 21 = s 21 q 21 = s 21 log 1 + h 21 P 2 σ 2 , U 12 = s 22 q 22 = s 22 log 1 + h 22 P 2 σ 2

Table 1 :

 1 Case 1,2 & 3: Shannon capacity (q)/probability(π)

	Case-1 state-1 state-2
		(bad)	(good)
	User-1	2/0.2	8/0.8
	User-2	2/0.2	8/0.8
	Case-2 state-1 state-2
		(bad)	(good)
	User-1	3/0.1	9/0.9
	User-2	1/0.3	7/0.7
	Case-3 state-1 state-2
		(bad)

RR n°7382

http://www.inria.fr ISSN 0249-6399