UNIFORM RANDOM VARIABLES 21
creating a chain that can move under repulsion is simple: choose two components
uniformly and then swap the labels in those components. In permutations, this is
called a transpositio n.
This is a special case of the far more general random walk on a group Markov
chain, but this particular move will suffice for the examples used here.
Such shifts of one value from one dimension to another can be useful for all
repulsive processes, not just permutations. Consider the h ard-core gas model (Defi-
nition 1.20) where each node is either occupied (x(v)=1) or unoccupied (x(v)=0)
but no two adjacent nodes can both be occupied. Each occupied node contributes a
factor of
λ
to the density. Then constructing a Gibbs step is straightforward.
HCGM Gibbs Input: old state x Output: new state x
1) Draw v ←Unif(V ), U ← Unif([0, 1])
2) Let n
1
be the number of neighbors of v labeled 1 in x
3) If U <
λ
/(
λ
+ 1) and n
1
= 0
4) x(v) ← 1
As soon as even a single neighbor of v is 1, the chain cannot alter the value of v.
A shift move allows that if a single neighbor of v has label 1, then with some chance,
remove the neighbor and label v with a 1. That is, take the 1 at the neighbor, and shift
it over to node v. The resulting update takes parameter
λ
and probability of shifting
p
shift
and works as follows. [32]
HCGM shift Input: old state x Output: new state x
1) Draw v ← Unif(V ), U ← Unif([0,1]), S ← Bern(p
shift
)
2) Let n
1
be the number of neighbors of v labeled 1 in x
3) If U ≤
λ
/(
λ
+ 1) and n
1
= 0
4) x(v) ← 1
5) Else if U ≤
λ
/(
λ
+ 1) and n
1
= 1andS = 1
6) Let w be the unique neighbor of v with x(w)=1
7) x(v) ← 1, x(w) ← 0
When two or more neighbors are occupied, shifting does not happen and the node
remains unoccupied.
1.9 Uniform random var iables
Note that in Sections 1.8.1 and 1.8.2, all of the random choices were made in the very
first line. Once these random choices had been made, the rest of the update proceeded
deterministically.
As noted earlier, the random choices made by a computer are of course never
truly random. Instead, pseudorandom numbers are generated that approximate an iid
sequence of random {0, 1} bits. Consider the Ising
Gibbs step from Section 1.8.1.
It first drew v ← Unif(V ). This requires log
2
(V ) random bits. Next it says to draw
U ←Unif([0,1]). Of course no real-world digital computer can do this, as U consists
of an infinite number of bits! See Figure 1 .1.
The good news is that the full value of U was never used. In fact, the only use of
22 INTRODUCTION
U = 0.11111110000000011110000110...
Figure 1.1 Written in binary, an actual uniform over [0,1] contains an infinite sequence of
bits, each of which is uniform over {0,1}. Any computer-generated randomness only contains
a finite number of such bits.
U was in line 4, where U was compared to a number. On average, only two bits will
be needed to make such a comparison.
To see why, consider a concrete example. Suppose it is necessary to determine if
U ≤ 2/3. In binary, 2/3 is written 0.101010101010.... Suppose the first bit of U is
0. Then U = 0.0 ... and no matter how the rest of th e digits are filled out, U ≤ 2/3.
So only if the first bit is 1 will more bits of U be needed. Suppose the first and second
bits are 1. Then U = 0.11...and now no ma tter how the rest of the bits are filled out,
U > 2/3.
After k bits are chosen, the only way to need the k + 1st bit is if the first k bits
match the number to be compared against exactly. Each bit has a 1/2 chance of
failing to match the bit of the number, and so a geometric number of bits with mean
1/(1/2)=2 are needed before being able to determine if U < a.
So it is possible to treat the uniform U as
∑
∞
i=1
B
i
/2
i
,whereB
i
is the ith bit in
the binary expansion of U .ThenB
1
,B
2
,... are an iid sequence of Bernoulli random
variables with mean 1/2.
Of course, since there are an infinite number of bits, it is possible to take this sin-
gle uniform, and break it up into two uniforms. The first uniform uses the odd bits in
U, and the second uses the even. So U
1
=
∑
∞
i=1
B
2i−1
/2
i
and U
2
=
∑
∞
i=1
B
2i
/2
i
.Since
U
1
and U
2
are u sing independent Bernoulli random variables, they are independent
of each other.
This can be taken further. Along the idea of Cantor diagonalization, this sequence
of bits can be turned into an iid sequence of uniforms.
Here is how this works. Let B
1
be the first binary digit of U
1
.ThenB
2
is the
second binary digit of U
1
and B
3
is the first binary digit of U
2
.ThenB
4
is the third
binary digit of U
1
, B
5
is the second binary digit of U
2
,andB
6
is the first binary digit of
U
3
. Continuing in this fashion, the {B
i
} sequence of random bits allows construction
of U
1
,U
2
,U
3
,..., each of which is independent and has Unif([0,1]) distribution.
Therefore a single U ∼ Unif([0,1]) can be viewed as an in finite sequence of iid
Unif([0,1]) random variables! The point is not to do this in practice, but by realiz-
ing this equivalence, all the randomness used by any randomized algorithm can be
summarized by a single uniform, which simplifies th e notation considerably.
In other words, any randomized algorithm can be written as a deterministic func-
tion
φ
(x,U),wherex is the deterministic input to the problem, and U ∼ Unif([0 , 1])
represents all the randomness used by the algorithm.
When a randomized algorithm that takes one step in a Markov chain is written in
this fashion, call the algorithm an update function. Update functions are the building
blocks of many perfect simulation algorithms (see Chapter 3).
COMPUTATIONAL COMPLEXITY 23
1.10 Computational complexity
An important facet of evaluating algorithms is determining their running time as a
function of input size. For example, suppose to generate a particular permutation on
n elements, n
3
+ n
2
random uniform numbers need to be generated. As n gets large,
the n
3
term dominates the number o f uniforms, and the n
2
term is insignificant.
If 2n
3
terms were needed, then the constant has changed, but the way the running
time scales with the problem input remains the same. Therefore, it is common to use
an asymptotic notation that does not depend either on the constants in front of the
largest term, or on the insignificant terms.
This asymptotic notation consists of sets of functions that behave the same way in
a large limit. Ther e are three types of sets. The first type, called Big-O, gives an upper
limit on the rate of growth of the function. The second type, called Big-Omega, gives
a lower limit on the rate of growth o f the function. The third type, called Big-Theta,
gives both upper and lower limits on the rate of growth.
For instance, say that n
3
,2n
3
,andn
3
+ n
2
are all in the set of functions denoted
O(n
3
). Using proper set notation, this would be written n
3
+ n
2
∈O(n
3
).However,it
is customary in this setting to abuse notation and use an equality sign = rather than
a set inclusion sign ∈. Formally, these notations can be defined for our purposes as
follows. (Note that while m ore general definitions are possible, the definition here is
best suited to analyzing running times of algorithms.)
Definition 1.35. Given functions f (x) and g(x) with common domain that is a subset
of [0,∞), say that
f (x)=O(g(x)) ⇔ (∃n)(∃c)(∀x > n)( f (x) ≤ c ·g(x))
f (x)=Ω(g (x)) ⇔(∃n)(∃c)(∀x > n )(c ·g(x) ≤ f (
x))
f (x)=Θ(g(x)) ⇔ (∃n)(∃c
1
)(∃c
2
)(∀x > n)(c
1
·g(x) ≤ f (x) ≤c
2
·g(x)).
Of course the smaller the running time of an algorithm, the better! Running time
functions in the sets O(n), Ω(n),andΘ(n) are referred to as linear time. Similarly,
running time functions in the sets O(1), Ω(1),andΘ(1) are called constant time.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.