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

1
2 9 improves on the lower bound of

1

050 e 9 that is derived
in [ 2 ]. In the next subsection we use this lower bound to estimate the expected time
to global happiness.

Our lower bound of

1 .

4.4.2 Time to Global Happiness

So far, we have obtained a bound on the time v of an individual player. Now we

want to obtain a bound on the global time to happiness

τ

max v τ v . Unfortunately,
we know nothing about the dependence structure between the

τ =

τ v , so the estimate on
max v τ v has to be a worst case estimate. It turns out that this worst case estimate is
covered by the case of maximally dependent random variables. This is a notion that
comes up in the study of stochastic order relations.
Recall that a random variable, X , is said to be stochastically smaller than another
random variable, Y ,if P [ X > t ] ≤ P [ Y > t ] ,forall t . Denote this as X ≤ st Y .Itis

known (see [ 15 ], Theorem 1 . A . 1) that X ≤ st Y if and only if there exist two random

X Y such that X

X , Y

X Y with probability 1. This will

variables , ∼ ∼ Y and ≤

apply in our case because we will show that τ v is stochastically smaller than S v ,

1
2 9

S v with

. In that case max v ˆ where S v ∼ 2 · Exp ( λ ) and λ : = − log ( 1 − ) τ v ≤ max v

max v ˆ probability 1 and τ ∼ τ v .

To see th at τ v ≤ st S v , note that the estimate of the previous subsection shows that

1
2 9 . Notice also that, for every player v ,

P [ τ v > t + 2 | τ v > t ] ≤ 1 −

1
k )

1
k )

1
e ≤

1
2 9 .

deg ( v ) k − 1

P [ τ > 1 | τ > 0 ]= 1 − ( 1 − ≤ 1 − ( 1 − ≤ 1 − 1 −

v v

Hence, if t is odd,

P [ τ v > t ]= P [ τ v > 1 | τ v > 0 ] · P [ τ v > 3 | τ v > 1 ] ··· P [ τ v > t | τ v > t − 2 ]

1

2 9 t / 2

1

≤ −

t
2 ]

= P [ Exp ( λ ) >

= P [ 2 · Exp ( λ ) > t ] ,

and similarly if t is even.
Thus

S v with probability 1. Define M n :

τ v ≤ st S v and thus max v ˆ τ v ≤ max v =

S v =

max v 2max v X v ,where X v ∼ Exp ( λ ) .Since τ ∼ max v ˆ τ v and max v ˆ τ v ≤ M n

with probability 1, we have that E [ τ ] ≤ E [ M n ] .

Thus, in order to estimate E [ τ ] , it is enough to estimate the maximum possible

value of E ran-

dom variables. Such ensemble maxima occur often in practical problems and have
been well studied both in the independent and the dependent case (see [ 4 , 11 , 12 ]).

[ M n ]= 2 E [ μ n ] ,where μ n is the maximum of n (dependent) Exp ( λ )