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

We estimate E [ μ n ] using ideas from [ 11 ]. Let F be the distribution function of

X v , v ∈ V . For any real number t ,wehavethat

+ v ( X v − t ) + , μ n ≤ t

n t which gives that E [ μ n ] ≤ h ( t ) : = t + [ 1 − F ( x )] dx ,forany t ∈ R . Differentiating

n t n

1
n )

F − 1

h ( · ) one finds that its minimum is at t n : = ( 1 − and so E [ μ n ] ≤ t n + [ 1 −

e − λ x it follows that E

1

F ( x )] dx .Since1 − F ( x )= [ μ n ] ≤

λ (

1 + log n ) . Hence

2
λ (

E [ τ ] ≤ 2 · E [ μ n ] ≤ 1 + log n ) .

We summarize the preceding results into a Theorem which is an improvement of
the Main Theorem from [ 2 ].

Theorem 3. Let G be a graph on n vertices and maximum degree Δ . If the number

of available colors is at least 2 and if all players adopt the simple strategy, then

for any starting assignment of colors, the network coloring game reaches a proper
coloring at time

Δ +

τ that is stochastically smaller than a random variable T , such that

2

,where 2

[ ] ≤

λ (

+ )

λ ≈

,

E T 1 log n 1 023 .

4.5 Proof of Theorem 2

This section is devoted to the proof of Theorem 2 . We want to show that the median
of X d is

3 d + 2

4 ,where X d is the number of different colors after a toss of d coins
that are colored using d colors. Before proving this theorem we need some notation
and remarks.
Suppose that we have d coins that are colored with d colors. Let G be the depen-
dency graph corresponding to this set of coins. We are going to orient G as follows.
Toss all the coins and orient each edge towards the vertex (color) that came up in
the toss. Thus a toss of the coins gives rise to an orientation on the edges of G .Asa
consequence, X d =

≤

j corresponds to the fact that j vertices have positive in-degree,

which means that d j vertices must have in-degree 0. Also note that none of the

vertices of zero in-degree can be adjacent.
We denote the in-degree of a vertex v by deg − (

−

v ) and by Z d the number of ver-

tices of zero in-degree. Thus X d = Z d .

It turns out that the median of X d can be estimated through the median of E d ,
the number of even in-degree vertices, whose distribution is easier to determine. We
will need the following two graph-theoretic results.

d −

Lemma 6. Suppose that G is a (possibly disconnected) graph on d vertices and m
edges. Fix some orientation on the edges and let O d , m , E d , m be the number of odd

and even in-degree vertices respectively. Then the parity of E d , m equals the parity of
m

− d.