Traditional Problems
We begin by introducing a number of every classical examples to illustrate the main themes of this book. We then recall, without proofs, the basic notions of analysis and probability theory which figure in numerous reference works; we also describe the fi
- PDF / 2,839,047 Bytes
- 36 Pages / 439.37 x 666.142 pts Page_size
- 66 Downloads / 169 Views
We begin by introducing a number of very classical examples to illustrate the main themes of this book. We then recaU, without proofs, the basic notions of analysis and probability theory which figure in numerous reference works; we also describe the first tools specific to recursive methods which we apply to the examples given at the beginning of the chapter. 1.1 Themes 1.1.1 Dosage: Robbins-Monro Procedure 1.1.2 Search for a Maximum: Kiefer-Wolfowitz Procedure 1.1.3 The Two-armed Bandit 1.1.4 Tracking 1.1.5 Decisions Adapted to a Sequence of Observations 1.1.6 Recursive Estimation 1.2 Deterministic Recursive Approximation 1.2.1 Search for a Zero of a Continuous Function 1.2.2 Search for Extrema 1.3 Random Sequences and Series 1.3.1 Martingales 1.3.2 Stopping and Inequalities 1.3.3 Robbins-Siegmund Theorem 1.3.4 Laws of Large Numbers 1.3.5 Laws of Large Numbers and Limits of Maxima 1.3.6 Noise and Regressive Series 1.4 Stochastic Recursive Approximation 1.4.1 Robbins-Monro Aigorithm 1.4.2 Control 1.4.3 The Two-armed Bandit 1.4.4 Tracking 1.4.5 Recursive Estimation
1.1 Themes 1.1.1 Dosage: Robbins-Monro Procedure A dose u of a chernical product creates a randorn effect rneasured by J(u, E), where E is a randorn variable and J is an unknown function frorn ]R2 to IR. The rnean effect is assurned to be increasing; in other words, J(u, E) is assurned to be a randorn variable with rnean cf>(u) = E[f(u, E)], where cf> is increasing (unknown). We seek to deterrnine the dose u' which creates a rnean effect of a given level a; in other words, to solve the equation cf>(u*) = a.
M. Duflo, Random Iterative Models © Springer-Verlag Berlin Heidelberg 1997
4
1. Traditional Problems
The Robbins-Monro procedure is as follows. Uo is chosen arbitrarily and administered to a subject which reacts with the effect XI = f(Uo, cd. The procedure continues recursively. At time na dose Un is chosen, based on previous observations, and administered to a subject independent of those already treated: the effect is X n + 1 = f(Un , cn+l). The subjects treated are assumed to be of the same type and mutually independent, which translates into the fact that (cn) is a sequence of independent random variables with the same law as c. Thus, since Un depends only upon the previous observations,
If X n +1 is greater than oe, it is sensible to reduce the dose; if X n + 1 is less than oe, it is sensible to increase the dose. The Robbins-Monro algorithm for choosing the Unis of the form: Un+ 1 = Un - I'n(Xn+ 1
-
oe), where I'n ::::: O.
1.1.2 Search for a Maximum: Kiefer-Wolfowitz Procedure We return to the above problem of dosage, but now our aim is to maximize the mean effect. The function
Data Loading...
