Information Technology Reference
In-Depth Information
More explicitly, for each color put a vertex in the graph and join two vertices if and
only if they are sides of the same coin. Note that the graph is loop-less and that it
might have parallel edges, because the same coin may occur more than one time.
In addition, note that the graph may not be connected and that there is a one-to-one
correspondence between array of coins and graphs and so one can choose not to
distinguish between vertices and colors as well as between coins and edges. We call
this graph the
dependency
graph of the set of coins.
Notice that in case
m
}
corresponds to the cycle-graph on
d
vertices. The proof of Theorem
1
actually says
that if the searchers want to maximize the mean of
X
d
, the number of different colors
after a toss, then they have to choose coins in such a way that the corresponding
graph is a cycle or a union of cycles. But what if the searchers want to maximize
the
median
of
X
d
? By median of a random variable,
X
, we mean any number
=
{
,
}{
,
}...{
−
,
}{
,
d
, the searchers strategy
1
2
2
3
d
1
d
d
1
μ
satisfying
P
[
X
≥
μ
]
≥
1
/
2and
P
[
X
≤
μ
]
≥
1
/
2. Notice that this
μ
might not be
unique. It turns out that the following theorem is true.
3
d
+
2
Theorem 2.
The median of X
d
is
≤
.
4
The proof of this Theorem is involved and builds on ideas from combinatorial
probability. We prove this theorem in the final section. Having this result, we are
then able to improve on the constant of the Key Lemma. This is the content of the
following section.
4.4 Back to Network Coloring
4.4.1 Probability of Individual Happiness
The lemma below improves on Lemma
4
, from [
2
].
Lemma 4.
Consider a single player, i.e., a vertex v in the network game at a given
round, t, and suppose that v is unhappy. Let Y be the set of available colors to v in
the next round, t
+
1
, and let f be the number of happy neighbors of v in the next
round, t
+
1
.Then
P
k
−
f
−
2
1
2
.
|
Y
|≥
≥
4
Proof.
Let
h
be the number of happy neighbors of
v
at the start of round
t
+
1. Let
θ
be the degree of
v
. Then only
h
unhappy neighbors are active in the game. Let
I
be the set of colors that are not used by the happy neighbors. Then
I
contains
k
θ
−
−
h
elements. In the worst case there are
h
unhappy neighbors all choosing a
color from
I
. That is, the neighbors are searchers in a game as the one of the previous
section. We may even add more searchers and suppose that the number of unhappy
neighbors in
k
Δ
−
h
≤
k
−
−
h
.If
Z
is the set of colors chosen by the searchers, then we have
Search WWH ::
Custom Search