Next: Choosing Up: Stochastic Models Previous: Stochastic Models

## Using to control the convergence rate

Decreasing the parameter causes the noise influence to decrease, but on the other hand the convergence is slower. Usually we will use -values such that: .

Let us look at one Typical Example:

• Let V be a random variable dependent of the parameter r.
• There exists a probability function : P(V|r)
• A function g(r,V)
We would like to solve : EV[g(r,V)]=r, where the expectation regards p(V|r).

We can write iterations of the form :

Computing the expected value can be complicated, but if
P(V|r) is known and can be simulated or sampled, we can get samples and use them to evaluate EV[g(r,V)]. For example we can sample and compute as the observed average.

If
K is large, then the average will be close to its expected value EV[g(r,V)] and in such a case we should expect a similar behaviour. The other extrem is the case of k=1 (one sample), .

where is distributed by p(v|r).

This algorithm is called the Robbins-Morro algorithm . The iterations can be written as:

where we can define :
Hrn = E[g(rn,V)],
. (and E[Wn] = 0 by definition of )
This implies that for each
we have,

.

Next: Choosing Up: Stochastic Models Previous: Stochastic Models
Yishay Mansour
1999-12-16