next up previous
Next: Using to control the Up: No Title Previous: Weighted average

Stochastic Models

Generally, we would like to solve systems of the form $H\vec{r}=\vec{r}$by finding a fix point of the operator H where $H:R^{n}\rightarrow R^{n}$.
One way of solving is to perform iterations of the form $r_{n+1}\leftarrow Hr_{n}$.
Note that if {rn} has a limit such that $r_{n}\longrightarrow r^{*}$and H is continuous around r* then Hr*=r*.

Remark : if H is a contracting operator then we showed that such a limit always exists.

An equivalent way for iteration is :

$r_{n+1} \leftarrow (1-\alpha)r_{n}+\alpha Hr_{n}$

which has the same convergence property.

Let us assume that H is not known, or hard to compute. We can replace H by a sample of the form S=Hr+W, where W is the sample's "noise" and E(W)=0.

Such an S can be given by simulation of the system or by a random experiment. We can use S instead of Hr and get the following iterative algorithm :

$r_{n+1} \leftarrow (1-\alpha)r_{n}+\alpha(Hr_{n}+W_{n})$

Such an algorithm is called Stochastic Approximation.


Yishay Mansour