Network Coloring and Colored Coin Games - Search Theory: A Game Theoretic Perspective - page 69

1
2 )

r + a + z r + a + z r + 2 a + 3 z

But a median of Bin ( r + a + z , is , it's mean. Since ≤ when

2 2 4

z ≥ r , the result follows.

Suppose now that z < r . We consider two case.

d − 1

(a) Assume that r − z is even. In that case we prove again that Med ( Ξ ) ≥ .

2

1 1 3 r − z

2

d − 1
2

Define Φ 1 : = Bin ( r ,

4 )+

Bin ( a ,

2 )+

Bin ( z ,

4 )+

.ThenMed ( Ξ ) ≥

3 r + 2 a + z
4

if and only if Med ( Φ 1 ) ≥ . By the result of Hoeffding we have that

1
r + a + z +

r
4

a
2

3 z
4

r − z 1

2 and

Med ( Φ 1 ) ≥ Med ( Bin ( n , p )) ,where p = ( + + + )=

r − z
2

2

r − z

n = r + a + z + .Since p = 1 / 2, we get that a median of Bin ( n , p ) is its mean

2

3 r + 2 a + z
4

which in turn equals n · p = .

d − 2

(b) Assume that r − z is odd. In a similar way as above we show that Med ( Ξ ) ≥ .

2

1 1 3 r − z − 1

2

d − 2
2

Define Φ 2 : = Bin ( r ,

4 )+

Bin ( a ,

2 )+

Bin ( z ,

4 )+

.ThenMed ( Ξ ) ≥ if

3 r + 2 a + z − 2 2

and only if Med ( Φ 2 ) ≥ −

4 . Again, by Hoeffding, we conclude that 4

1 r

4 +

a
2 +

3 z
4 +

r − z − 1

Med ( Φ 2 ) ≥ Med ( Bin ( n , p )) ,where p = ( ) and

r − z − 1

2

r + a + z +

2

r − z − 1
2

3 r + 2 a + z − 2

n

4 .It
is known (see [ 7 ]) that the smallest uniform (with respect to both parameters)
distance of the mean and a median of a Binomial distribution is

= r + a + z + . Now the mean of Bin ( n , p ) equals n · p =

≤ ln 2 ≈ 0 . 69 <

3 1

4 . This means that if n

· p equals μ +

4 , for some integer

μ ,then μ is a median

3

of Bin ( n , p ) .If n · p equals μ +

4 , for some integer

μ ,then μ + 1 is a median of

1
2 , then a median of Bin

Bin ( n , p ) and if n · p = μ + ( n , p ) is ≥ μ . If the mean,

·

n p is an integer, then it is well known (see [ 9 ]) that mean and median coincide.

In all cases a median is

1
2

≥ · −

n p and the result follows.

4.6 Final Comment

We have improved the previous estimates on the time to global equilibrium in the
network coloring game by combining search games and combinatorial probability.
The colored coin tossing problem which we considered is interesting in its own
right. One open problem that deserves further study is the following: suppose you
can color n biassed coins with n colors, all coins having the same bias. It is forbidden
to color both sides of a coin with the same color, but all other colors are allowed.
Let X be the number of different colors after a toss of the coins. In what way should
you color the coins such that you maximize the median of X ?

References

1. S. Alpern, D.J. Reyniers: Spatial Dispersion as a Dynamic Coordination Problem, Theory and

Decision , 53 , p. 29-59, (2002).

2. K. Chaudhuri, F. Chung Graham , M. Shoaib Jamall: A Network Coloring Game, WINE '08,

p. 522-530, (2008).