Reflected Brownian motion

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In probability theory, reflected Brownian motion (or regulated Brownian motion,[1][2] both with the acronym RBM) is a Wiener process in a space with reflecting boundaries.[3]

RBMs have been shown to describe queueing models experiencing heavy traffic[2] as first proposed by Kingman[4] and proven by Iglehart and Whitt.[5][6]

Definition[edit]

A d–dimensional reflected Brownian motion Z is a stochastic process on \scriptstyle \mathbb R^d_+ uniquely defined by

  • a d–dimensional drift vector μ
  • a d×d non-singular covariance matrix Σ and
  • a d×d reflection matrix R.[7]

where X(t) is an unconstrained Brownian motion and[8]

Z(t) = X(t) + R Y(t)

with Y(t) a d–dimensional vector where

  • Y is continuous and non–decreasing with Y(0) = 0
  • Yj only increases at times for which Zj = 0 for j = 1,2,...,d
  • Z(t) ∈ S, t ≥ 0.

The reflection matrix describes boundary behaviour. In the interior of \scriptstyle \mathbb R^d_+ the process behaves like a Wiener process, on the boundary "roughly speaking, Z is pushed in direction Rj whenever the boundary surface \scriptstyle \{ z \in \mathbb R^d_+ : z_j=0\} is hit, where Rj is the jth column of the matrix R."[8]

Stability conditions[edit]

Stability conditions are known for RBMs in 1, 2, and 3 dimensions. "The problem of recurrence classification for SRBMs in four and higher dimensions remains open."[8] In the special case where R is an M-matrix then necessary and sufficient conditions for stability are[8]

  1. R is a non-singular matrix and
  2. R−1μ < 0.

Stationary distribution[edit]

One dimension[edit]

The transient distribution of a one-dimensional Brownian motion starting at 0 restricted to positive values (a single reflecting barrier at 0) with drift μ and variance σ2 is

\mathbb P(Z \leq z) = \Phi \left(\frac{z-\mu t}{\sigma t^{1/2}} \right) - e^{-2 \mu z /\sigma^2} \Phi \left( \frac{-z-\mu t}{\sigma t^{1/2}} \right)

for all t ≥ 0, (with Φ the cumulative distribution function of the normal distribution) which yields (for μ < 0) when taking t → ∞ an exponential distribution[2]

\mathbb P(Z<z) = 1-e^{-2\mu z/\sigma^2}.

Multiple dimensions[edit]

The stationary distribution of a reflected Brownian motion in multiple dimensions is tractable analytically when there is a product form stationary distribution,[9] which occurs when the process is stable and[10]

2 \Sigma = RD + DR'

where D = diag(Σ). In this case the probability density function is[7]

p(z_1,z_2,\ldots,z_d) = \prod_{k=1}^d \eta_k e^{-\eta_k z_k}

where ηk = 2μkγk/Σkk and γ = R−1μ. Closed-form expressions for situations where the product form condition does not hold can be computed numerically as described below in the simulation section.

Hitting times[edit]

One dimension[edit]

Write T(y) for the first time a one-dimensional RBM starting at 0 reaches the level y. Then[2]

\mathbb P(T(y)>t) = \Phi\left(\frac{y-\mu t}{\sigma t^{1/2}}\right) -e^{2\mu y/\sigma^2}\Phi\left(\frac{-y-\mu t}{\sigma t^{1/2}}\right).

Simulation[edit]

One dimension[edit]

In one dimension the simulated process is the absolute value of a Wiener process. The following MATLAB program creates a sample path.[11]

%rbm.m
n=10^4; h=10^(-3); t=h.*(0:n); mu=-1;
X=zeros(1,n+1); M=X; B=X;
B(1)=3; X(1)=3;
for k=2:n+1
  Y=sqrt(h)*randn; U=rand(1);
  B(k)=B(k-1)+mu*h-Y;
  M=(Y + sqrt(Y^2-2*h*log(U)))/2;
  X(k)=max(M-Y,X(k-1)+h*mu-Y);
end
subplot(2,1,1)
plot(t,X,'k-');
subplot(2,1,2)
plot(t,X-B,'k-');

The error involved in discrete simulations has been quantified.[12]

Multiple dimensions[edit]

QNET allows simulation of steady state RBMs.[13][14][15]

Other boundary conditions[edit]

Feller described possible boundary condition for the process[16][17][18]

See also[edit]

References[edit]

  1. ^ Dieker, A. B. (2011). "Reflected Brownian Motion". Wiley Encyclopedia of Operations Research and Management Science. doi:10.1002/9780470400531.eorms0711. ISBN 9780470400531.  edit
  2. ^ a b c d Harrison, J. Michael (1985). Brownian Motion and Stochastic Flow Systems. John Wiley & Sons. ISBN 0471819395. 
  3. ^ Veestraeten, D. (2004). "The Conditional Probability Density Function for a Reflected Brownian Motion". Computational Economics 24 (2): 185–207. doi:10.1023/B:CSEM.0000049491.13935.af.  edit
  4. ^ Kingman, J. F. C. (1962). "On Queues in Heavy Traffic". Journal of the Royal Statistical Society. Series B (Methodological) (Wiley) 24 (2): 383–392. JSTOR 2984229. Retrieved 30 Nov 2012.  edit
  5. ^ Iglehart, Donald L.; Whitt, Ward (1970). "Multiple Channel Queues in Heavy Traffic. I". Advances in Applied Probability (Applied Probability Trust) 2 (1): 150–177. JSTOR 3518347. Retrieved 30 Nov 2012.  edit
  6. ^ Iglehart, Donald L.; Ward, Whitt (1970). "Multiple Channel Queues in Heavy Traffic. II: Sequences, Networks, and Batches". Advances in Applied Probability (Applied Probability Trust) 2 (2): 355–369. JSTOR 1426324. Retrieved 30 Nov 2012.  edit
  7. ^ a b Harrison, J. M.; Williams, R. J. (1987). "Brownian models of open queueing networks with homogeneous customer populations". Stochastics 22 (2): 77. doi:10.1080/17442508708833469.  edit
  8. ^ a b c d Bramson, M.; Dai, J. G.; Harrison, J. M. (2010). "Positive recurrence of reflecting Brownian motion in three dimensions". The Annals of Applied Probability 20 (2): 753. doi:10.1214/09-AAP631.  edit
  9. ^ Harrison, J. M.; Williams, R. J. (1992). "Brownian Models of Feedforward Queueing Networks: Quasireversibility and Product Form Solutions". The Annals of Applied Probability 2 (2): 263. doi:10.1214/aoap/1177005704. JSTOR 2959751.  edit
  10. ^ Harrison, J. M.; Reiman, M. I. (1981). "On the Distribution of Multidimensional Reflected Brownian Motion". SIAM Journal on Applied Mathematics 41 (2): 345–361. doi:10.1137/0141030.  edit
  11. ^ Kroese, Dirk P.; Taimre, Thomas; Botev, Zdravko I. (2011). Handbook of Monte Carlo Methods. John Wiley & Sons. p. 202. ISBN 1118014952. 
  12. ^ Asmussen, S.; Glynn, P.; Pitman, J. (1995). "Discretization Error in Simulation of One-Dimensional Reflecting Brownian Motion". The Annals of Applied Probability 5 (4): 875. doi:10.1214/aoap/1177004597. JSTOR 2245096.  edit
  13. ^ Dai, Jim G.; Harrison, J. Michael (1991). "Steady-State Analysis of RBM in a Rectangle: Numerical Methods and A Queueing Application". The Annals of Applied Probability (Institute of Mathematical Statistics) 1 (1): 16–35. JSTOR 2959623. Retrieved 5 December 2012.  edit
  14. ^ Dai, Jiangang "Jim" (1990). "Section A.5 (code for BNET)". Steady-state analysis of reflected Brownian motions: characterization, numerical methods and queueing applications (Ph. D. thesis). Stanford University. Dept. of Mathematics. Retrieved 5 December 2012. 
  15. ^ Dai, J. G.; Harrison, J. M. (1992). "Reflected Brownian Motion in an Orthant: Numerical Methods for Steady-State Analysis". The Annals of Applied Probability (Institute of Mathematical Statistics) 2 (1): 65–86. JSTOR 2959654.  edit
  16. ^ a b c d e Skorokhod, A. V. (1962). "Stochastic Equations for Diffusion Processes in a Bounded Region. II". Theory of Probability & Its Applications 7: 3–1. doi:10.1137/1107002.  edit
  17. ^ Feller, W. (1954). "Diffusion processes in one dimension". Transactions of the American Mathematical Society 77: 1–0. doi:10.1090/S0002-9947-1954-0063607-6.  edit
  18. ^ Engelbert, H. J.; Peskir, G. (2012). "Stochastic Differential Equations for Sticky Brownian Motion". Probab. Statist. Group Manchester Research Report (5). 
  19. ^ Chung, K. L.; Zhao, Z. (1995). "Killed Brownian Motion". From Brownian Motion to Schrödinger's Equation. Grundlehren der mathematischen Wissenschaften 312. p. 31. doi:10.1007/978-3-642-57856-4_2. ISBN 978-3-642-63381-2.  edit
  20. ^ Itō, K.; McKean, H. P. (1996). "Time changes and killing". Diffusion Processes and their Sample Paths. p. 164. doi:10.1007/978-3-642-62025-6_6. ISBN 978-3-540-60629-1.  edit