MCMC

Searching for Maxima

Let

be a nonnegative objective function on the interval

. First we consider the following algorithm searching for maxima:

Choose the initial state at time .
Suppose that at time . Then pick the next move $\Delta x$ randomly and set $y = x + \Delta x$ .
If $a\le y \le b$ and then set $X_{t+1} = y$ .
Otherwise, stay $X_{t+1} = x$ at time .

Explore it. Download nm.r and search.r into your own machine. Use the normal mixture density function on the interval as the objective function of choice, and see if the algorithm achieves the global maximum.

> source("nm.r")
> source("search.r")
> search(ff=nm)

Random ascending rule. Next we consider the following algorithm searching for maxima:

Choose the initial state at time .
Suppose that at time . Then pick the next move $\Delta x$ randomly and set $y = x + \Delta x$ .
Generate a uniform random variable on
If $0\le y \le 1$ and then set $X_{t+1} = y$ .
Otherwise, stay $X_{t+1} = x$ at time .

Explore it. See how differently the algorithm behaves.

Save the trajectory data from , and graph the trajectory of moves in series.
Look the whole trajectory as data, and obtain the histogram.
Save the trajectory data from to , and obtain the histogram.

> par(mfrow=c(2,1))
> xx = search(ff=nm, random=T, save.time=0,run.time=1000)
> plot(0:1000, xx, type="l", main="Trajectory Data", xlab="time", ylab="state")
> xx = search(ff=nm, random=T, save.time=0,run.time=1000)
> hist(xx, freq=F, breaks=seq(0,1,by=0.05), col="blue", main="Trajectory Data", xlab="state")
> xx = search(ff=nm, random=T, save.time=4000,run.time=5000)
> hist(xx, freq=F, breaks=seq(0,1,by=0.05), col="blue", main="Trajectory Data", xlab="state")

Programming note. The set-parameter function par(mfrow=c(2,1)) set mfrow=c(2,1), and splits the multiple graphics to assign 2 figures horizontally and one vertically. hist() is used to create the histogram of the data, and the optional arguments ``freq=F'' and ``breaks=seq(0,1,by=0.05)'' are specified. Here these options request ``relative frequency histogram'' with given class intervals , , $\ldots$ , .