Introduction

Consider an initially empty urn to which balls, either red or black, are added one at a time. Let y n denote the number of red balls at time n and \({x_n}\mathop = \limits^{def} {y_n}/n\) the fraction of red balls at time n. We shall suppose that the conditional probability that the next, i.e., the (n + 1)st ball is red given the past up to time n is a function of x n alone. Specifically, suppose that it is given by p(x n ) for a prescribed p : [0, 1] → [0, 1]. It is easy to describe {x n , n ≥ 1} recursively as follows. For {y n }, we have the simple recursion $${y_{n + 1}} = {y_n} + {\xi _{n + 1}}$$, where $$\begin{array}{*{20}{l}} {{\xi _{n + 1}}\quad = \quad 1\,if\,the\,(n + 1)st\,ball\,is\,red,} \\ {\quad \quad \,\, = \quad 0\,if\,the\,(n + 1)st\,ball\,is\,black.} \end{array}$$. Some simple algebra then leads to the following recursion for {x n {: $${x_{n + 1}} = {x_n} + \frac{1}{{n + 1}}\left( {{\xi _{n + 1}} - {x_n}} \right),$$, with x0 = 0. This can be rewritten as $${x_{n + 1}} = {x_n} + \frac{1} {{n + 1}}\left( {p\left( {{x_n}} \right) - {x_n}} \right) + \frac{1} {{n + 1}}\left( {{\xi _{n + 1}} - p\left( {{x_n}} \right)} \right)$$. Note that \({M_n}\mathop = \limits^{def} {\xi _n} - p\left( {{x_{n - 1}}} \right){,_{\;n}} \geqslant 1\) (with \(p\left( {{x_0}} \right)\mathop = \limits^{def}\) probability of the first ball being red) is a sequence of zero mean random s/b variables satisfying E[Mn+1|ξ m , m ≤ n] = 0 for n ≥ 0. This means that {M n } is a martingale difference sequence (see Appendix C), i.e., uncorrelated with the ‘past’, and thus can be thought of as ‘noise’. The above equation then can be thought of as a noisy discretization (or Euler scheme in numerical analysis parlance) for the ordinary differential equation (o.d.e. for short) $$\dot x\left( t \right) = p\left( {x\left( t \right)} \right) - x\left( t \right)$$, for t ≥ 0, with nonuniform stepsizes \(a\left( n \right)\mathop = \limits^{def} 1/\left( {n + 1} \right)\) and ‘noise’ {M n }.