Page 91 -

78 Exercises

x ← ran (−1, 1) (Section 1.3)
y ← ran (−1, 1)
2
Υ ← x + y 2 (1.18) Implement Alg. 1.25 (binomial-convolution).
output Υ Compare the probability distribution π(N hits)for
N = 1000, with histograms generated from many
Compute the distribution function π(Υ) using ele- runs of Alg. 1.1 (direct-pi). Plot the probability
mentary geometric considerations. Is it true that Υ distributions for the rescaled variables x = N hits/N
is uniformly distributed in the interval Υ ∈ [0, 1]? and ˜x =(x − /4)/σ,where σ =( /4)(1 − /4).
2
Implement the algorithm and generate a histogram
to check your answers. (1.19) Modify Alg. 1.26 (ran01-convolution) to allow you
to handle more general probability distributions,
(1.12) Implement both the naive Alg. 1.17 (naive-gauss)
which are nonzero on an arbitrary interval x ∈ [a, b].
with arbitrary K and the Box–Muller algorithm,
Follow the convergence of various distributions with
Alg. 1.18 (gauss). For which value of K can you
zero mean their convergence towards a Gaussian.
still detect statistically significant differences be-
tween the two programs? (1.20) Implement Alg. 1.28 (data-bunch). Test it for
a single, very long, simulation of Alg. 1.2
(1.13) Generate uniformly distributed vectors {x 1,...,x d}
(markov-pi) with throwing ranges δ ∈
inside a d-dimensional unit sphere. Next, incorpo-
{0.03, 0.1, 0.3}. Test it also for output of Alg. 1.6
rate the following code fragment:
(markov-discrete-pebble) (compute the proba-
... bility to be at site 1). If possible, compare with
x d+1 ← ran (−1, 1) the correlation times for the n × n pebble game
2
if ( P d+1 x k > 1)then
k=1 obtained from the second largest eigenvalue of the
˘
output “reject”
transfer matrix (see Exerc. 1.8).
...
Show that the acceptance rate of the modified pro-
gram yields the ratio of unit-sphere volumes in (d+ (Section 1.4)
1) and in d dimensions. Determine V 252(1)/V 250(1), γ−ζ
(1.21) Determine the mean value of O = x in a sim-
and compare with eqn (1.39).
ple implementation of Alg. 1.31 (markov-zeta)for
(1.14) Sample random vectors {x 1,...,x d} on the surface ζ> − . Monitor the rejection rate of the algo-
1
2
of the d-dimensional unit sphere, using Alg. 1.22 rithm as a function of the step size δ, and compute
(direct-surface). Compute histograms of the vari- the mean square deviation of O. Is the most precise
2
2
able I 12 = x 1 + x 2 . Discuss the special case of value of O obtained with a step size satisfying the
four dimensions (d = 4). Determine the distribu- one-half rule?
tion π(I 12) analytically.
(1.22) Implement Alg. 1.29 (direct-gamma), subtract the
(1.15) Generate three-dimensional orthonormal coordi- mean value 1/(γ + 1) for each sample, and generate
nate systems with axes {ˆ e x, ˆ e y, ˆ e z} randomly ori- histograms of the average of N samples, and also of
ented in space, using Alg. 1.22 (direct-surface). the rescaled averages, as in Fig. 1.46.
Test your program by computing the average scalar (1.23) Implement a variant of Alg. 1.29 (direct-gamma),

¸
˙
products (ˆ e x · · · ˆ e x ) , (ˆ e y · · · ˆ e y ) ,and (ˆ e z · · · ˆ e z ) for
in order to sample the distribution
pairs of random coordinate systems.
(
(1.16) Implement Alg. 1.13 (reject-finite)for K = (x − a) γ if x>a
α
10 000 and probabilities π k =1/k ,where 1 < π(x) ∝ γ .
−c|x − a| if x<a
α< 2. Implement Alg. 1.14 (tower-sample)for the
same problem. Compare the sampling efficiencies. For concreteness, determine the mean of the dis-
NB: Do not recompute π max for each sample in the tribution analytically as a function of {a, c, γ},
rejection method; avoid recomputing {Π 0,.. ., Π K} and subtract it for each sample. Compute the his-
for each sample in the tower-sampling algorithm. tograms of the distribution function for the rescaled
(1.17) Use a sample transformation to derive how to gener- sum of random variables distributed as π(x). Com-
ate random numbers φ distributed as π(φ)= 1 sin φ pute the parameters {A ±,c 1,2} of the L´evy distri-
2
for φ ∈ [0, ]. Likewise, determine the distribution bution as a function of {a, c, γ}, and compare the
function π(x)for x =cos [ran (0, /2)]. Test your histograms of rescaled averages to the analytic limit
answers with histograms. distribution of eqn (1.86).