Part IV
Games and design of randomized algorithms
Chapter 4. BASIC TECHNIQUES for DESIGN and ANALYSIS
In this chapter we present a new way how to see
randomized algorithms and several basic techniques how to
design and analyse randomized algorithms:
Especially we deal with:
Application of linearity of expectations
Game theory based lower bounds methods for
randomized algorithms.
prof. Jozef Gruska IV054 4. Games and design of randomized algorithms 2/1
PROLOGUE
A way to see basics of deterministic, randomized
and quantum computations and their differences.
prof. Jozef Gruska IV054 4. Games and design of randomized algorithms 3/1
MATHEMATICAL VIEWS of COMPUTATION 1/3
Let us consider an n bits strings set S ⊂ {0, 1}n
.
To describe a deterministic computation on S we need to specify
an initial state - by an n-bit string - say s0
and an evolution (computation mapping) , E : S → S which can be described by a
vector of the length 2n
, the elements and indices of which are n-bit strings.
A computation step is then an application of the evolution mapping E to the current
state represented by an n-bit string s.
However, for any a bit significant task, the number of bits needed to describe such an
evolution mapping, n2n
, is much too big. The task of programming is then/therefore
to replace an application of such an enormously huge mapping by an application of a
much shorter circuit/program.
prof. Jozef Gruska IV054 4. Games and design of randomized algorithms 4/1
MATHEMATICAL VIEWS of COMPUTATION 2/3
To describe a randomized computation we need;
1:) to specify an initial probability distribution on all n-bit strings, what can be done by
a vector of length 2n
, indexed by n-bit strings, the elements of which are non-negative
numbers that sum up to 1
2:) to specify a randomized evolution, which has to be done, in case of a homogeneous
evolution, by a 2n
× 2n
matrix A of conditional probabilities for obtaining a new
state/string from an old state/string.
The matrix A has to be stochastic - all columns have to sum up to one and A[i, j] is a
probability of going from a string representing j to a string representing i.
To perform a computation step, one then needs to multiply by A the 2n
-elements
vector specifying the current probability distribution on 2n
states.
However, for any nontrivial problem the number 2n
is larger than the number of particles
in the universe. Therefore, the task of programming is to design a small
circuit/program that can implement such a multiplication by a matrix of an enormous
size.
prof. Jozef Gruska IV054 4. Games and design of randomized algorithms 5/1
MATHEMATICAL VIEWS of COMPUTATION 3/3
In case of quantum computation on n quantum bits:
1:) Initial state has to be given by an 2n
vector of complex numbers (probability
amplitudes) the sum of the squares of which is one.
2:) Homogeneous quantum evolution has to be described by an 2n
× 2n
unitary matrix
of complex numbers - at which inner products of any two different columns and any two
different rows are 0.1
Concerning a computation step, this has to be again a multiplication of a vector of the
probability amplitudes, representing the current state, by a very huge 2n
× 2n
unitary
matrix which has to be realized by a ”small” quantum circuit (program).
1
A matrix A is usually called unitary if its inverse matrix can be obtained from A by transposition around
the main diagonal and replacement of each element by its complex conjugate.
prof. Jozef Gruska IV054 4. Games and design of randomized algorithms 6/1
LINEARITY OF EXPECTATIONS
A very simple, but very often very useful, fact is that for any random variables X1, X2, . . .
it holds
E[
i
Xi ] =
i
E[Xi ].
even if Xi are dependent and dependencies among Xi ’s are very complex.
Example: A ship arrives at a port, and all 40 sailors on board go ashore to have fun. At
night, all sailors return to the ship and, being drunk, each chooses randomly a cabin to
sleep in. Now comes the question: What is the expected number of sailors sleeping in
their own cabins?
Solution Let Xi be a random variable, so called (indicator variable), which has value 1 if
the i-th sailor chooses his own cabin, and 0 otherwise.
Expected number of sailors who get to their own cabin is
E[
40
i=1
Xi ] =
40
i=1
E[Xi ]
Since cabins are chosen randomly E[Xi ] = 1
40
and therefore,E[ 40
i=1 Xi ] = 40. 1
40
= 1.
prof. Jozef Gruska IV054 4. Games and design of randomized algorithms 7/1
EXAMPLE - BINARY PARTITION of a SET of LINE SEGMENTS
1/3
Problem Given a set S = {s1, . . . , sn} of non-intersecting line segments, find a partition
of the plane such that every region will contain at most one line segment (or at most a
part of a line segment).
s1
s3
s3 s3
L1
s1 s2
L2 L3
L1
s1
s2
s3
L2
L3
s2
A (binary) partition will be described by a binary tree + additional information (about
nodes). With each node v a region rv of the plane will be associated (the whole plane
will be represented by the root) and also a line Lv intersecting rv .
Each line Lv will partition the region rv into two regions rl,v and rr,v which correspond to
two children of v - to the left and right one.
prof. Jozef Gruska IV054 4. Games and design of randomized algorithms 8/1
EXAMPLE - BINARY PARTITION of a SET of LINE SEGMENTS
2/3
Notation: l(si ) will denote a line-extension of the segment si .
autopartitions will use only line-extensions of given segments.Algorithm RandAuto:
Input: A set S = {s1, . . . , sn} of non-intersecting line segments.
Output: A binary autopartition PΠ of S.
1: Pick a permutation Π of {1, . . . , n} uniformly and randomly.
2:While there is a region R that contains more than one segment, choose one of
them randomly and cut it with l(si ) where i is the first element in the ordering induced
by Π such that l(si ) cuts the region R.Theorem: The expected size of the autopartition
PΠ of S, produced by the above RandAuto algorithm is θ(n ln n).
Proof: Notation (for line segments u, v).
index(u, v) =
i if l(u) intersects i − 1 segments before hitting v;
∞ if l(u) does not hit v.
u v will be an event that l(u) cuts v in the constructed (autopartition) tree.
prof. Jozef Gruska IV054 4. Games and design of randomized algorithms 9/1
EXAMPLE - BINARY PARTITION of a SET of LINE SEGMENTS
3/3
Probability: Let u and v be segments, index(u, v) = i and let u1, . . . , ui−1 be segments
the line l(u) intersects before hitting v.
The event u v happens, during an execution of RandPart, only if u occurs before any
of {u1, . . . , ui−1, v} in the permutation Π.Therefore the probability that event u v
happens is 1
i+1
= 1
index(u,v)+1
.
Notation: Let Cu,v be the indicator variable that has value 1 if u v and 0 otherwise.
E[Cu,v ] = Pr[u v] =
1
index(u, v) + 1
.
Clearly, the size of the created partition PΠ equals n plus the number of intersections due
to cuts. Its expectation value is therefore
n + E[
u v=u
Cu,v ] = n +
u v=u
Pr[u v] = n +
u v=u
1
index(u, v) + 1
.
For any line segment u and integer i there are at most two v, w such that
index(u, v) = index(u, w) = i.Hence v=u
1
index(u,v)+1
≤ n−1
i=1
2
i+1
and therefore
n + E[ u v=u Cu,v ] ≤ n + u
n−1
i=1
2
i+1
≤ n + 2nHn.
prof. Jozef Gruska IV054 4. Games and design of randomized algorithms 10/1
GAME TREE EVALUATION - I.
Game trees
x3x1 x2 x4 x5 x6 x7 x8 1 y2 y3 y4 y5 6 y7 y8y y
min min
min
min min
max max
Game trees are trees with operations max and min alternating in internal nodes and
values assigned to their leaves. In case all such values are Boolean - 0 or 1 Boolean
operation OR and AND are considered instead of max and min.
Tk – binary game tree of depth 2k.
T
1
Goal is to evaluate the tree - the root.
prof. Jozef Gruska IV054 4. Games and design of randomized algorithms 11/1
GAME TREE EVALUATION - II.
x3x1 x2 x4 x5 x6 x7 x8 1 y2 y3 y4 y5 6 y7 y8y y
min min
min
min min
max max
Evaluation of game trees plays a crucial role in AI, in various game playing programs.
Assumption: An evaluation algorithm chooses at each step (somehow) a leaf, reads
its value and performs all evaluations of internal nodes it can perform. Cost of an
evaluation algorithm is the number of leaves inspected. Determine the total number
of such steps needed.
prof. Jozef Gruska IV054 4. Games and design of randomized algorithms 12/1
WORST CASE COMPLEXITY
Tk – will denote the binary game tree of depth 2k.
T
1
Every deterministic algorithm can be forced to inspect all leaves. The worst-case
complexity of a deterministic algorithm is therefore:
n = 4k
= 22k
.
prof. Jozef Gruska IV054 4. Games and design of randomized algorithms 13/1
A RANDOMIZED ALGORITHM - BASIC IDEA:
To evaluate an AND-node v, the algorithm chooses randomly one of its
children and evaluates it.
If 1 is returned, algorithm proceeds to evaluate other children subtree and
returns as the value of v the value of that subtree. If 0 is returned,
algorithm returns immediately 0 for v (without evaluating other subtree).
To evaluate an OR-node v, algorithm chooses randomly one of its children
and evaluates it.
If 0 is returned, algorithm proceeds to evaluate other subtree and returns as
the value of v the value of the subtree. If 1 is returned, the algorithm
returns 1 for v.
prof. Jozef Gruska IV054 4. Games and design of randomized algorithms 14/1
RANDOMIZED ALGORITHMS - SUMMARY of THE BASIC IDEA
Start at the root and in order to evaluate a node evaluate
(recursively) a random child of the current node.
If this does not determine the value of the current node,
evaluate the node of other child.
prof. Jozef Gruska IV054 4. Games and design of randomized algorithms 15/1
Theorem: Given any instance of Tk , the expected number of steps for the above
randomized algorithm is at most 3k
.
Proof by induction:
Base step: Case k = 1 easy - verify by computations for all cases.
Inductive step: Assume that the expected cost of the evaluation of any instance of Tk−1
is at most 3k−1
.
Consider an OR-node tree T with both children being Tk−1-trees.
If the root of T were to return 1, at least one of its Tk−1-subtrees has to return 1.
With probability 1
2
this child is chosen first, given in average at most 3k−1
leaf-evaluations. With probability 1
2
both subtrees are to be evaluated.
The expected cost of determining the value of T is therefore:
1
2
× 3k−1
+
1
2
× 2 × 3k−1
=
1
2
× 3k
=
3
2
× 3k−1
.
prof. Jozef Gruska IV054 4. Games and design of randomized algorithms 16/1
If the root of T were to return 0 both subtrees have to be evaluated, giving the cost
2 × 3k−1
.
Consider now the root of Tk .
If the root evaluates to 1, both of its OR-subtrees have to evaluate to 1. The expected
cost is therefore
2 ×
3
2
× 3k−1
= 3k
.
If the root evaluates to 0, at least one of the subtrees evaluates to 0. The expected cost
is therefore
1
2
× 2 × 2 × 3k−1
+
1
2
×
3
2
× 3k−1
≤ 3k
= nlg4 3
= n0.793
.
Our algorithm is therefore a Las Vegas algorithm. Its running time (number of leaves
evaluations) is: n0.793
.
prof. Jozef Gruska IV054 4. Games and design of randomized algorithms 17/1
CLASSICAL GAMES THEORY
CLASSICAL GAMES THEORY
BRIEFLY
prof. Jozef Gruska IV054 4. Games and design of randomized algorithms 18/1
BASIC CONCEPTS of CLASSICAL GAME THEORY
We will consider games with two players, Alice and Bob.X and Y will be
nonempty sets of their game (pure) strategies -X of Alice, Y of Bob. Mappings
pX : X × Y → R and pY : X × Y → R will be called payoff functions of Alice
and Bob. The quadruple (X, Y , pX , pY ) will be called a (mathematical) game.
A mixed strategy will be a probability distribution on pure strategies.
An element (x, y) ∈ X × Y is said to be a Nash equilibrium of the game
(X, Y , pX , pY ) iff pX (x , y) ≤ pX (x, y) for any x ∈ X, and pY (x, y ) ≤ pY (x, y)
for all y ∈ Y .
Informally, Nash equilibrium is such a pair of strategies that none of the players
gains by changing his/her strategy.
A game is called zero-sum game if pX (x, y) + pY (x, y) = 0 for all x ∈ X and
y ∈ Y .
prof. Jozef Gruska IV054 4. Games and design of randomized algorithms 19/1
ONE of THE BASIC RESULTS
One of the basic result of the classical game theory is that
not every two-players zero-sum game has a Nash
equilibrium in the set of pure strategies, but there is always
a Nash equilibrium if players follow mixed strategies.
prof. Jozef Gruska IV054 4. Games and design of randomized algorithms 20/1
POWER Of QUANTUM PHENOMENA
It has been shown, for several zero-sum games, that if one of the
players can use quantum tools and thereby quantum strategies, then
he/she can increase his/her chance to win the game.
This way, from a fair game, in which both players have the same
chance to win if only classical computation and communication tools
are used, an unfair game can arise, or from an unfair game a fair one.
prof. Jozef Gruska IV054 4. Games and design of randomized algorithms 21/1
EXAMPLE - PENNY FLIP GAME
Alice and Bob play with a box and a penny as follows:
Alice places a penny head up in a box.
Bob flips or does not flip the coin
Alice flips or does not flip the coin
Bob flips or does not flip the coin
After the “game” is over, they open the box and Bob wins if the penny is head up.
It is easy to check that using pure strategies chances to win are 1
2
for each player and
there is no (Nash) equilibrium in the case of pure classical strategies.
However, there is equilibrium if Alice chooses its strategy with probability 1
2
and Bob
chooses each of the four possible strategies with probability 1
4
.
prof. Jozef Gruska IV054 4. Games and design of randomized algorithms 22/1
VERSION of PRISONERS’ DILEMMA from 1992
Two members of a gang are imprisoned, each in a separate cell, without possibility to
communicate. However, police has not enough evidence to convict them on the principal
charge and therefore police intends to put both of them for one year to jail on a lesser
charge.
Simultaneously police offer both of them so called Faustian bargain. Each prisoner gets a
chance either to betray the other one by testifying that he committed the crime, or to
cooperate with the other one by remaining silent. pause Here are payoffs they are offered:.
If both betray, they will get into jail for 2 years.
If one betrays and second decides to cooperate, then first will get free and second
will go to jail for 3 years.
If both cooperate they will go to jail for 1 year.
What is the best way for them to behave? This game is a model for a variety of real-life
situations involving cooperative behaviour. Game was originally framed in 1950 by M.
Flood and M. Dresher
prof. Jozef Gruska IV054 4. Games and design of randomized algorithms 23/1
PRISONERS’ DILEMMA - I.
Two prisoners, Alice and Bob, can use, independently, any of the following
two strategies: to cooperate or to defect (not to cooperate).
The problem is that the payoff function (pA, pB), in millions, is a very
special one (first (second) value is payoff of Alice (of Bob):
Alice
Bob
CA DA
CB (3, 3) (5, 0)
DB (0, 5) (1, 1)
What is the best way for Alice and Bob to proceed in order to maximize
their payoffs?
prof. Jozef Gruska IV054 4. Games and design of randomized algorithms 24/1
PRISONERS’ DILEMMA - II.
A strategy sA is called dominant for Alice if for any other strategy sA of
Alice and sB of Bob, it holds
PA(sA, sB) ≥ PA(sA, sB).
Clearly, defection is the dominant strategy of Alice (and also of Bob) in the
case of Prisoners Dilemma game.
Prisoners Dilemma game has therefore dominant-strategy equilibrium
Alice
Bob
CA DA
CB (3, 3) (5, 0)
DB (0, 5) (1, 1)
prof. Jozef Gruska IV054 4. Games and design of randomized algorithms 25/1
BATTLE of SEX GAME
Alice and Bob have to decide, independently of each other, where to spent the evening.
Alice prefers to go to opera (O), Bob wants to watch TV (T) - tennis.
However, at the same time both of them prefer to be together than to be apart.
Pay-off function is given by the matrix (columns are for Alice) (columns are for Bob)
O T
O (α, β) (γ, γ)
T (γ, γ) (β, α)
where α > β > γ.
What kind of strategy they should choose?
The two Nash equilibria are (O, O) and (T, T), but players are faced with tactics
dilemma, because these equilibria bring them different payoffs.
prof. Jozef Gruska IV054 4. Games and design of randomized algorithms 26/1
COIN GAME
There are three coins: one fair, with both sides different, and two unfair, one with two
heads and one with two tails.
The game proceeds as follows.
Alice puts coins into a black box and shakes the box.
Bob picks up one coin.
Alice wins if coin is unfair, otherwise Bob wins
Clearly, in the classical case, the probability that Alice wins is 2
3
.
prof. Jozef Gruska IV054 4. Games and design of randomized algorithms 27/1
FROM GAMES to LOWER BOUNDS for RANDOMIZED
ALGORITHMS
Next goal is to present, using zero-sum games theory, a method how
to prove lower bounds for the average running time of randomized
algorithms.
This techniques can be applied to algorithms that terminate for all
inputs and all random choices.
prof. Jozef Gruska IV054 4. Games and design of randomized algorithms 28/1
TWO–PERSON ZERO–SUM GAMES – EXAMPLE
A two players zero–sum game is represented by an n × m payoff–matrix M with all rows
and columns summing up to 0.
Payoffs for n possible strategies of Alice are given in rows of M.
Payoffs for m possible strategies of Bob are given in columns of M.
Mi,j
is the amount paid by Bob to Alice if Alice chooses strategy i and Bob’s choice is
strategy j.
The goal of Alice (Bob) is to maximize (minimize) her payoff.
Example - stone-scissors-paper game
PAYOFF–MATRIX
Alice
Bob
Scissors Paper Stone
Scissors 0 1 -1
Paper -1 0 1
Stone 1 -1 0
→ Table shows how
much Bob has to pay
to Alice
prof. Jozef Gruska IV054 4. Games and design of randomized algorithms 29/1
STRATEGIES for ZERO-INFORMATION and ZERO-SUM GAMES
(Games with players having no information about their opponents’ strategies.)
Observe that if Alice chooses a strategy i, then she is guaranteed a payoff of minj Mij
regardless of Bob’s strategy.
An optimal strategy OA for Alice is such an i that maximises minj Mij .
OA = max
i
min
j
Mij
denotes therefore the lower bound on the value of the payoff Alice gains (from Bob)
when she uses an optimal strategy.
An optimal strategy OB for Bob is such a j that minimizes maxi Mij . Bob’s optimal
strategy ensures therefore that his payoff is at least
OB = min
j
max
i
Mij
prof. Jozef Gruska IV054 4. Games and design of randomized algorithms 30/1
Theorem
OA = max
i
min
j
Mij ≤ min
j
max
i
Mij = OB
Often OA < OB . In our last (scissors-...) example, −1 = OA < OB = +1.
If OB = OA we say that the game has a solution – a specific choice of strategies that
leads to this solution.
and γ are so called optional strategies for Alice and Bob if
OA = OB = M γ
prof. Jozef Gruska IV054 4. Games and design of randomized algorithms 31/1
Example of the game which has a solution
(OA = OB = 0)
0 1 2
-1 0 1
-2 -1 0
What happens if a game has no solution ?
There is no clear–cut strategy for any player.
Way out: to use randomized strategies.
Alice chooses strategies according to a probability vector p = (p1, . . . , pn); pi is
probability that Alice chooses strategy sA,i
Bob chooses strategies according to a probability vector q = (q1, . . . , qn); qj is a
probability that Bob chooses strategy sB,j .
Payoff is now a random variable – if p, q are taken as column vectors then
E[payoff] = pT
Mq =
n
i=1
m
j=1
pi Mij qj
prof. Jozef Gruska IV054 4. Games and design of randomized algorithms 32/1
Let OA (OB) denote the best possible (optimal) lower
(upper) bound on the expected payoff of Alice (Bob).
Then it holds:
OA = max
p
min
q
pT
Mq OB = min
q
max
p
pT
Mq
prof. Jozef Gruska IV054 4. Games and design of randomized algorithms 33/1
Theorem (von Neumann Minimax theorem) For any
two–person zero–sum game specified by a payoff matrix M it holds
max
p
min
q
pT
Mq = min
q
max
p
pT
Mq
Observe that once p is fixed, maxp minq pT
Mq = minq maxp pT
Mq is a linear function and
is minimized by setting to 1 the qj with the smallest coefficient in this linear function.
This has interesting/important implications:
If Bob knows the distribution p used by Alice, then his optimal strategy is a pure
strategy.
A similar comment applies in the opposite direction. This leads to a simplified version of
the minimax theorem, where ek denotes a unit vector with 1 at the k-th position and 0
elsewhere.
Theorem (Loomis’ Theorem) For any two–persons zero–sum game
max
p
min
j
pT
Mej = min
q
max
i
eT
i Mq
prof. Jozef Gruska IV054 4. Games and design of randomized algorithms 34/1
YAO’S TECHNIQUE 1/3
Yao’s technique provides an application of the game-theoretic results to the
establishment of lower bounds for randomized algorithms.
For a given algorithmic problem P let us consider the following payoff matrix.
I
N
P
U
T
S
c1
c2
c3
c4
deterministic algorithms
A1 A2 A3
entries
=
resources
(i.e. used computation time)
Bob – a designer
choosing good algorithms
Alice – an adversary
choosing bad inputs
Pure strategy for Bob corresponds to the choice of a deterministic algorithm.
Optimal pure strategy for Bob corresponds to a choice of an optimal deterministic
algorithm.
prof. Jozef Gruska IV054 4. Games and design of randomized algorithms 35/1
YAO’S TECHNIQUE 2/3
VB is the worst-case running time of any deterministic algorithm
Problem: How to interpret mixed strategies ?
A mixed strategy for Bob is a probability distribution over (always correct) deterministic
algorithms—so it is a Las Vegas randomized algorithm.
An optimal mixed strategy for Bob is an optimal Las Vegas algorithm. Distributional
complexity of a problem is an expected running time of the best deterministic algorithm
for the worst distribution on the inputs.
Loomis theorem implies that distributional complexity equals to the least possible time
achievable by any randomized algorithm
Reformulation of von Neumann+Loomis’ theorem in the language of algorithms
Corollary Let Π be a problem with a finite set I of input instances and A be a finite set
od deterministic algorithms for Π.For any input i ∈ I and any algorithm A ∈ A, let
T(i, A) denote computation time of A on input i. For probability distributions p over I
and q over A, let ip denote random input chosen according to p and Aq a random
algorithm chosen according to q. Then
max
p
min
q
E [T(ip, Aq)] = min
q
max
p
E [T(ip, Aq)]
max
p
min
A∈A
E [T(ip, A)] = min
q
max
i∈I
E [T(i, Aq)]
prof. Jozef Gruska IV054 4. Games and design of randomized algorithms 36/1
YAO’S TECHNIQUE 3/3
Consequence:
Theorem(Yao’s Minimax Principle) For all distributions p over I and q over A.
min
A∈A
E[T(ip, A)] ≤ max
i∈I
E[T(i, Aq)]
Interpretation: Expected running time of the optimal deterministic algorithm for an
arbitrarily chosen input distribution p for a problem Π is a lower bound on the expected
running time of the optimal (Las Vegas) randomized algorithm for Π.
In other words, to determine a lower bound on the performance of all randomized
algorithms for a problem P, derive instead a lower bound for any deterministic
algorithm for P when its inputs are drawn from a specific probability distribution (of
your choice).
prof. Jozef Gruska IV054 4. Games and design of randomized algorithms 37/1
IMPLICATIONS OF YAO’S MINIMAX PRINCIPLE
Interpretation again Expected running time of the optimal deterministic algorithm for an
arbitrarily chosen input distribution p for a problem Π is a lower bound on the expected
running time of the optimal (Las Vegas) randomized algorithm for Π.
Consequence:
In order to prove a lower bound on the randomized complexity of an algorithmic problem,
it suffices to choose any probability distribution p on the input and prove a lower bound
on the expected running time of deterministic algorithms for that distribution.
The power of this technique lies in
1 the flexibility at the choice of p
2 the reduction of the task to determine lower bounds for randomized algorithms to
the task to determine lower bounds for deterministic algorithms.
(It is important to remember that we can expect that the deterministic algorithm
”knows” the chosen distribution p.)
The above discussion holds for Las Vegas algorithms only!
prof. Jozef Gruska IV054 4. Games and design of randomized algorithms 38/1
THE CASE OF MONTE CARLO ALGORITHMS
Let us consider Monte Carlo algorithms with error probability 0 < ε < 1
2
.
Let us define the distributional complexity with error ε, notation
min
A∈A
E [Tε(Ip, A)],
to be the minimum expected time of any deterministic algorithm that errs with
probability at most ε under the input Ip with distribution p.
Let us denote by
max
i∈I
E [(Tε(i, Aq)]
the expected time (under the worst input) of any randomized algorithm Aq that errs with
probability at most ε.
Theorem For all distributions p over inputs and q over Algorithms, and any ε ∈ [0, 1/2],
it holds
1
2
(min
A∈A
E [T2ε(ip, A)]) ≤ max
i∈I
E [Tε(i, Aq)]
prof. Jozef Gruska IV054 4. Games and design of randomized algorithms 39/1
GAMES TREES REVISITED
A randomized algorithm for a game-tree T evaluations can be viewed as a probability
distribution over deterministic algorithms for T, because the length of computation and
the number of choices at each step are finite.
Instead of AND–OR trees of depth 2k we can consider NOR–trees of depth 2k.
Indeed, it holds:
(a ∨ b) ∧ (c ∨ d) ≡ (a NOR b)NOR(c NOR d)
NOR NOR
NOR
NOR NOR NOR NOR
prof. Jozef Gruska IV054 4. Games and design of randomized algorithms 40/1
Note: It’s important to distinguish between:
the expected running time of the randomized algorithm with a fixed input
(where probability is considered over all random choices made by the algorithm)
and
the expected running time of the deterministic algorithm when proving the lower
bound (the average time is taken over all random input instances).
prof. Jozef Gruska IV054 4. Games and design of randomized algorithms 41/1
LOWER BOUND FOR GAME TREE EVALUATION - I
Assume now that each leaf of a NOR-tree is set up to have value 1 with probability
p = 3−
√
5
2
(observe that (1 − p)2
= p for such a p).
Observe that if inputs of a NOR-gate have value 1 with probability p then its output
value is also 1 with probability (1 − p)(1 − p) = p.
Consider now only depth–first pruning algorithms for tree evaluation.
(They are such depth–first algorithms that make use of the knowledge that subtrees that
provide no additional useful information can be ”pruned away”.)
Of importance for the overall analysis is the following technical lemma:
Lemma Let T be a NOR–tree each leaf of which is set to 1 with a fixed probability. Let
W (T) denote the minimum, over all deterministic algorithms, of the expected number of
steps to evaluate T. Then there is a depth–first pruning algorithm whose expected
number of steps to evaluate T is W (T).
The last lemma tells us that for the purposes of our lower bound, we may restrict our
attention to the depth–first pruning algorithms.
prof. Jozef Gruska IV054 4. Games and design of randomized algorithms 42/1
LOWER BOUND FOR GAME TREE EVALUATION - II
For a depth–first pruning algorithm evaluating a NOR–tree, let W (h) be the expected
number of leaves the algorithm inspects in determining the value of a node at distance h
from the leaves.
It holds
W (h) = pW (h − 1) + (1 − p)2W (h − 1) = (2 − p)W (h − 1)
because with the probability 1 − p the first subtree produces 0 and therefore also the
second tree has to be evaluated. If h = lg2 n, then the above recursion has a solution
W (h) ≥ n0.694
.
This implies:
Theorem The expected running time of any randomized algorithm that always evaluates
an instance of Tk correctly is at least n0.694
, where n = 22k
is the number of leaves.
prof. Jozef Gruska IV054 4. Games and design of randomized algorithms 43/1
The upper bound for randomized game tree evaluation algorithms already shown, at the
beginning of this chapter was n0.79
, what is more than the lower bound n694
just shown.
It was therefore natural to ask what does the previous theorem really says?
For example, is our lower bound technique weak? ?
No, the above result just says that in order to get a better lower bound another
probability distribution on inputs may be needed.
prof. Jozef Gruska IV054 4. Games and design of randomized algorithms 44/1
RECENT RESULTS
Two recent results put more light on the Game tree evaluation
problem.
It has been shown that for our game tree evaluation problem the
upper bound presented at the beginning is the best possible and
therefore that θ(n0.79
) is indeed the classical (query) complexity of
the problem.
It has also been shown, by Farhi et al. (2009), that the upper
bound for the case quantum computation tools can be used is
O(n0.5
).
prof. Jozef Gruska IV054 4. Games and design of randomized algorithms 45/1
APPENDIX
The concept of the number of wisdom introduced in the following and
related results helped to show that randomness is deeply rooted even
in arithmetic.
In order to define numbers of wisdom the concept of self-delimiting
programs is needed.
A program represented by a binary word p, is self-delimiting for a
computer C, if for any input pw the computer C can recognize where
p ends after reading p only..
prof. Jozef Gruska IV054 4. Games and design of randomized algorithms 46/1
Another way to see self-delimiting programs is to consider only such
programming languages L that no program in L is a prefix of another
program in L.
prof. Jozef Gruska IV054 4. Games and design of randomized algorithms 47/1
Ω - numbers of wisdom
For a universal computer C with only self-delimiting programs, the number
of wisdom ΩC is the probability that randomly constructed program for C
halts.More formally
ΩC =
p halts
2−|p|
where p are (self-delimiting) halting programs for C.
ΩC is therefore the probability that a self-delimiting computer program for
C generated at random, by choosing each of its bits using an independent
toss of a fair coin, will eventually halt.
prof. Jozef Gruska IV054 4. Games and design of randomized algorithms 48/1
Properties of numbers of wisdom
0 ≤ ΩC ≤ 1
ΩC is an uncomputable and random real number.
At least n-bits long theory is needed to determine n bits of ΩC .
At least n bits long program is needed to determine n bits of ΩC
Bits of Ω can be seen as mathematical facts that are true for no reason.
prof. Jozef Gruska IV054 4. Games and design of randomized algorithms 49/1
Greg Chaitin, who introduced numbers of wisdom, designed a specific
universal computer C and a two hundred pages long Diophantine
equation E, with 17,000 variables and with one parameter k, such that
for a given k the equation E has a finite (infinite) number of solutions
if and only if the k-th bit of ΩC is 0 (is 1).{ As a consequence, we have
that randomness, unpredictability and uncertainty occur even in the
theory of Diophantine equations of elementary arithmetic.}
Knowing the value of ΩC with n bits of precision allows to decide
which programs for C with at most n bits halt.
prof. Jozef Gruska IV054 4. Games and design of randomized algorithms 50/1