Dr. Mark Humphrys School of Computing. Dublin City University. Free course: Online AI programming exercises Search:

```

```

# A Incremental sampling of random variables

Most of the results in these appendices are either well-known or trivial, but they are included here for completeness, and so they can be referred to from the main body of the text.

# A.1 Single variable (average)

Let be samples of a stationary random variable d with expected value E(d). Then the following update algorithm provides an elegant way of sampling them. Repeat:  Proof: D's updates go: i.e. D is simply the average of all samples so far.

As , .  Proof: D's updates go: As : that is, . One way of looking at this is to consider as the average of all samples before time t, samples which are now irrelevant for some reason. We can consider them as samples from a different distribution f: Hence: as .

```
``` I could have made this clearer:
1/n ( dt + ... + dn ) = (n-t+1)/n   1/(n-t+1) ( dt + ... + dn )
->   1 . E(d)

```
```

# A.2 Single variable (time-weighted)

An alternative approach (e.g. see [Grefenstette, 1992]) is to build up not the average of all samples, but a time-weighted sum of them, giving more weight to the most recent ones. This is accomplished by setting to be constant, in which case D's updates go: Since as , this weights more recent samples higher. Grefenstette uses typically .

# A.3 Multiple variables

Consider sampling alternately from two stationary random variables d and f:  Proof: From Theorem A.1, after 2t samples: as . More generally, consider where we have multiple stationary distributions , where each distribution has expected value . At each time t, we take a sample from one of the distributions. Each distribution has probability p(i) of being picked. Repeat:  Proof: For a large number of samples t we expect to take p(1) t samples from , p(2) t samples from , and so on. From Theorem A.1, we expect: as . ### Appendix B

Return to Contents page.

```
```
```
```
ancientbrain.com      w2mind.org      humphrysfamilytree.com

On the Internet since 1987.

Wikipedia: Sometimes I link to Wikipedia. I have written something In defence of Wikipedia. It is often a useful starting point but you cannot trust it. Linking to it is like linking to a Google search. A starting point, not a destination. I automatically highlight in red all links to Wikipedia and Google search and other possibly-unreliable user-generated content.