Adaptive stochastic paths and brownian bridge coupling

Assume the Axiom of Choice as in the finite-dimensional Gaussian and Brownian interfaces. Let $m\ge 1$ be a finite integer. A node represents an interval $[u,u+h]$, where $h>0$, and has an already sampled parent increment $\mathrm{\Delta }W\in {\mathbb{R}}^m$. Draw a fresh vector $Z\sim N_m(0,(h\mathrm{/}4)I_m)$ independently of the parent and of every innovation used at another node. Store the two child increments $\mathrm{\Delta }{W}_L=\frac{1}{2}\mathrm{\Delta }W+Z,\mathrm{\Delta }{W}_R=\frac{1}{2}\mathrm{\Delta }W-Z\mathrm{.}$

For a finite ordered list of $q\in {\mathbb{N}}_0$ split requests, each naming an existing leaf, apply the rule once to each requested leaf and retain every parent. Process a rejected trial's left child before its right child; if a child is later refined, draw a new independent innovation for it. Each request replaces one leaf by two children, so the result is a finite rooted tree with the sampled increments, interval lengths, and left-to-right order. Never discard a sampled parent and redraw a replacement for the same interval. The procedure assigns increments at dyadic tree nodes; it does not by itself define values at nondyadic times or prove that the node-selection rule is predictable. In an adaptive run, a finite work budget supplies a finite list of requests.

Conditional on a fixed parent, the child sum is fixed and their conditional cross-covariance is $-(h\mathrm{/}4)I_m$, so they are not conditionally independent. The exact unconditional Brownian increment laws at fixed dyadic depth are proved separately on the A page; this procedure makes no law claim for a data-dependent set of requested leaves.

Assume AC. Fix $m\ge 1$, $h>0$, and a finite tree depth $r\ge 0$. Take a root increment $D_{\mathrm{\varnothing }}\sim N_m(0,h{I}_m)$. At each internal node $v$ of length ${\mathrm{\ell }}_v=h\mathrm{/}{2}^{\mathrm{\mid }v\mathrm{\mid }}$, use the split in Dyadic Brownian bridge increment tree with a fresh $Z_v\sim N_m(0,({\mathrm{\ell }}_v\mathrm{/}4)I_m)$ independent of the root and of all other innovations. Then the $2^r$ increments at depth $r$ are mutually independent and each has law $N_m(0,(h\mathrm{/}{2}^r)I_m)$. At every internal node its increment is exactly the sum of its two children. The independence claim is unconditional; conditional on a fixed parent, the two children have covariance $-({\mathrm{\ell }}_v\mathrm{/}4)I_m$ and are not independent.

Assume $T>0$ and work on a filtered probability space with stopping times and stopped sigma-algebras as defined in Continuous-time stopping times and stopped sigma-algebras. A finite predictable stopping-time grid on $[0,T]$ consists of an integer-valued random variable $N$ with $1\le N<\mathrm{\infty }$ almost surely and a sequence $({\tau }_n{)}_{n\ge 0}$ of stopping times. It satisfies ${\tau }_0=0$, ${\tau }_n<{\tau }_{n+1}$ on $\{n<N\}$, and ${\tau }_n=T$ on $\{n\ge N\}$. For every fixed integer $n\ge 0$, define $h_n={\tau }_{n+1}-{\tau }_n$ and require that $h_n$ is ${\mathcal{F}}_{{\tau }_n}$-measurable; on $\{n<N\}$ require also $0<h_n\le h_{\max }$ for a deterministic $h_{\max }>0$. Thus $h_n=0$ on $\{n\ge N\}$. A budgeted predictable grid has a deterministic integer $B$ with $N\le B$ almost surely.

The condition $h_n\in {\mathcal{F}}_{{\tau }_n}$ says the next interval is selected using information available at its left endpoint. Predictability is relative to the specified filtration: a step choice using a trial Brownian increment is excluded when it fails this measurability test. No Brownian motion or filtration-relative independence assumption is part of this definition. Brownian-bridge refinement can retain sampled increments, but retaining them does not by itself establish the required measurability of the step choice.

Assume AC and use the usual augmented Brownian filtration of Natural and usual augmented Brownian filtrations. Let $X=(X_t{)}_{0\le t\le T}$ be an adapted, finite-dimensional real process with continuous paths on a measurable event of probability one. If $\tau$ is a stopping time with $0\le \tau \le T$, then the stopped random vector $X_{\tau }$ is ${\mathcal{F}}_{\tau }$-measurable.

Assume AC and the usual filtered-space hypotheses for the Itô integral. Let $W$ be a scalar Brownian motion on $[0,T]$, let $0\le \tau \le \sigma \le T$ be stopping times, and let $\xi \in L^2({\mathcal{F}}_{\tau })$. The process $H_s=\xi 1_{(\tau ,\sigma ]}(s)$ is predictable with finite energy, and its continuous Itô-integral version satisfies ${\int }_0^t{H}_{s}d{W}_s=\xi (W_{t\wedge \sigma }-W_{t\wedge \tau })(0\le t\le T)$ up to indistinguishability. The statement applies coordinatewise to each entry of a matrix-valued coefficient and a finite-dimensional Brownian motion.

Assume AC and use the coefficient, Brownian, and initial-value conventions of Euler–Maruyama recursion, on a filtered space satisfying the usual conditions. The inputs are $T>0$, the coefficients $b,\sigma$, the Brownian path or increment source, an initial value $X_0$, a deterministic maximum step $h_{\max }>0$, and a deterministic work budget $B\in {\mathbb{N}}_0$. Stopped Brownian values are measurable at their stopped sigma-algebras by the upper-grid approximation and null-completion argument of Continuous adapted processes are measurable at bounded stopping times, which applies to any complete filtration, and each stopping time ${\tau }_n$ is ${\mathcal{F}}_{{\tau }_n}$-measurable by the event tests of Continuous-time stopping times and stopped sigma-algebras. Since $h_n$ is ${\mathcal{F}}_{{\tau }_n}$-measurable, Borel coefficient evaluation and the predictable-grid update keep $Y_n$ measurable at ${\mathcal{F}}_{{\tau }_n}$ by induction. The continuous interpolation is adapted as well: at each fixed $t$, the active-interval events are in ${\mathcal{F}}_t$ by the stopping-time tests, and each term uses stopped values restricted to $\{{\tau }_n\le t\}$. Choose one of the following modes.

1. Predictable-grid mode. Supply a finite predictable grid Predictable stopping-time grid with $h_n\le h_{\max }$ on every active interval. Initialize $Y_0=X_0$ and process its intervals in order until the grid reaches $T$ or the budget is exhausted. Each interval uses the actual Brownian increment and update $Y_{n+1}=Y_n+b({\tau }_n,Y_n)h_n+\sigma ({\tau }_n,Y_n)(W_{{\tau }_{n+1}}-W_{{\tau }_n})\mathrm{.}$ The continuous interpolation on the interval is $Y_t=Y_n+b({\tau }_n,Y_n)(t-{\tau }_n)+\sigma ({\tau }_n,Y_n)(W_t-W_{{\tau }_n})\mathrm{.}$ This is the Euler–Maruyama update of Euler–Maruyama recursion with the supplied interval length; the fixed-grid supplier itself makes no variable-grid convergence assertion.

2. Endpoint-refinement mode. Supply a total Borel-measurable Boolean-valued accept/reject rule on the finite-dimensional current trial data. Initialize a queue with a finite partition $0=u_0<\cdots <u_J=T$ whose root intervals have lengths at most $h_{\max }$, together with their sampled Brownian increments. Pop the earliest interval $[u,u+\mathrm{\ell }]$, form the Euler trial $Y^{\ast }=Y+b(u,Y)\mathrm{\ell }+\sigma (u,Y)\mathrm{\Delta }W$, and apply the supplied Borel accept/reject rule (a Borel function of the finite trial history and current trial data). If accepted, set $Y\leftarrow Y^{\ast }$, append the right-endpoint/state pair to the accepted path record, and advance to the interval's right endpoint. If rejected, retain its parent increment, split it with Dyadic Brownian bridge increment tree, and put its left then right children at the front of the queue; do not update $Y$ on the rejected parent and do not redraw the parent or either child. This branch preserves the sampled path tree, but an endpoint-dependent acceptance rule does not by itself establish the stopped-measurability condition of a predictable-grid controller; the strong-error theorem on this page makes no error claim for this branch.

For either mode, initialize current_time=0, current_state=X_0, and trial_count=0. Maintain current_time and current_state as the endpoint and Euler state of the accepted path. In endpoint-refinement mode, also initialize the accepted path record with $(0,X_0)$; append each right-endpoint/state pair only when its interval is accepted. Count every trial node, accepted or rejected, as one work unit; after each trial, increment trial_count by one. Before the first trial and after every trial, first check whether the mode's completion condition holds: the supplied grid has reached $T$ in predictable-grid mode, or the queue is empty and the accepted path reaches $T$ in endpoint-refinement mode. If so, return with status: complete. Otherwise, if the count has reached $B$, return with status: inconclusive; if not, perform the next trial. Thus a budget $B=0$ returns inconclusive, and a last trial that reaches $T$ returns complete.

Both statuses use the output record (mode, status, current_time, current_state, approximation, pending_work, trial_count). On completion, current_time=T, current_state=Y_T, and pending_work is empty. The approximation is the full continuous Euler interpolation in predictable-grid mode; in endpoint-refinement mode it is the accepted ordered endpoint/state record together with the retained increment tree. On an inconclusive return, trial_count=B, current_state is the state at current_time, and approximation is the partial output through that time: the continuous interpolation restricted to $[0,\mathtt{\text{current\_time}}]$ in predictable-grid mode, and the accepted endpoint/state record and retained tree in endpoint-refinement mode. pending_work is the remaining ordered grid suffix or the current ordered tree queue, respectively. The tree assigns no values at non-dyadic times, so endpoint-refinement mode returns its accepted node record rather than a continuous interpolation. A finite budget never changes an inconclusive result into a successful certificate.

Assume AC and consider the budgeted procedure in Euler–Maruyama on a predictable grid with bridge-refinement status with integer budget $B\in {\mathbb{N}}_0$, at most $B$ trial operations occur. The procedure returns complete only after reaching $T$; if the budget is exhausted earlier it returns inconclusive. Consequently its number of trial operations is an integrable random variable with expectation at most $B$. This is a finite budget operation count, not an asymptotic cost estimate in terms of error.

Work on a filtered probability space satisfying the usual conditions for the It^o integral. Assume the coefficient and Brownian hypotheses of Euler–Maruyama recursion on $[0,T]$: finite state/noise dimensions, a square integrable ${\mathcal{F}}_0$-measurable initial value, globally Lipschitz state dependence, linear growth, and the stated half-Hölder time modulus. Let a finite predictable grid as in Predictable stopping-time grid have $N<\mathrm{\infty }$ almost surely and maximum step at most $h_{\max }\le T$. Form the complete continuous Euler interpolation by applying the predictable-grid updates in Euler–Maruyama on a predictable grid with bridge-refinement status on every interval. A finite-budget execution returns this interpolation as complete when its budget $B$ satisfies $N\le B$. Then a finite constant $C=C(T,K,m,\mathbb{E}\mathrm{\mid }{X}_0{\mathrm{\mid }}^2)$ satisfies $\mathbb{E}{\sup }_{0\le t\le T}\mathrm{\mid }{Y}_t{\mathrm{\mid }}^2\le C\mathrm{.}$ The bound is uniform over the controller and the number and placement of its predictable steps; no deterministic bound on $N$ is needed for this moment estimate.

Assume AC and the coefficient hypotheses of Euler–Maruyama recursion on $[0,T]$: finite state and noise dimensions, a square-integrable initial value independent of future Brownian increments, global Lipschitz dependence on the state, the stated linear-growth bound, and the stated half-Hölder time modulus. Work on the usual filtered Brownian space required by the It^o integral. Let $X$ be the strong solution of Itô SDE data and strong solution, whose existence and path-supremum second moment are supplied by Global strong well-posedness for Lipschitz Itô SDEs. Let a finite predictable grid as in Predictable stopping-time grid have $N<\mathrm{\infty }$ almost surely and step lengths bounded by a deterministic $0<h\le T$ (one may take $h=\min \{h_{\max },T\}$). Form the complete continuous Euler interpolation by applying the predictable-grid updates of Euler–Maruyama on a predictable grid with bridge-refinement status on every interval. A finite-budget execution returns it as complete when $N\le B$. Then there is a finite constant $C$, depending only on $T$, the coefficient bounds, $m$, and $\mathbb{E}\mathrm{\mid }{X}_0{\mathrm{\mid }}^2$, such that ${\sup }_{0\le t\le T}\mathbb{E}\mathrm{\mid }{X}_t-Y_t{\mathrm{\mid }}^2\le Ch\mathrm{.}$ Thus the one-time root-mean-square error is $O(h^{1\mathrm{/}2})$, uniformly over predictable controllers and finite meshes. The estimate is not an expectation of the path-supremum error. It does not cover a grid whose step choice or acceptance decision uses the endpoint of the interval being selected. No finite expected step-count or asymptotic cost claim follows without an additional step-count hypothesis.

Assume AC. Let $h>0$, $x,y\in \mathbb{R}$, and let $W$ be a standard scalar Brownian motion on $[0,h]$. The scalar Brownian bridge from $x$ to $y$ over duration $h$ is the continuous Gaussian process $B_t^{x,y,h}=x+\frac{t}{h}(y-x)+W_t-\frac{t}{h}{W}_h,0\le t\le h\mathrm{.}$ It starts at $x$ and ends at $y$. Its law does not depend on which Brownian motion is used: Brownian increment laws determine its finite-dimensional laws. For the path-law assertion, give $C([0,h])$ the uniform topology and extend each path $f$ by $E_{h}f(s)=f(s\wedge h)$ for $s\ge 0$. This is a homeomorphism onto the closed subspace of $C([0,\mathrm{\infty }))$ consisting of paths constant after $h$, with inverse restriction to $[0,h]$. Thus Borel sigma-algebra of continuous path space is generated by coordinates makes the Borel sigma-algebra on $C([0,h])$ generated by its coordinates: coordinates of the extension after $h$ equal $f(h)$, and continuity recovers every coordinate, including $h$, from rational times in $[0,h]$. Equality on finite coordinate cylinders now gives equality of path laws by Dynkin's pi-lambda theorem. The endpoint-conditional and restriction-density properties are established separately on the A page.

Assume AC, let $h>0$ and $x,y\in \mathbb{R}$, and let ${\mu }_{x,y}^h$ be the law on $C([0,h])$ of the bridge in Scalar Brownian bridge from x to y. If $X_s=x+W_s$ is Brownian motion started at $x$, then for every Borel path event $A\subseteq C([0,h])$ and Borel set $D\subseteq \mathbb{R}$, $\mathbb{P}\{X\in A,X_h\in D\}={\int }_D{p}_h(y-x){\mu }_{x,y}^h(A)dy,$ where $p_t(z)=(2\pi t{)}^{-1\mathrm{/}2}{e}^{-z^2\mathrm{/}(2t)}$. In particular this specifies the endpoint-conditioned bridge law for every endpoint $y$. For every $0\le t<h$, the restriction of ${\mu }_{x,y}^h$ to path events up to time $t$ has density $\frac{p_{h-t}(y-X_t)}{p_h(y-x)}$ relative to Brownian motion $X$ started at $x$ on $[0,t]$.