Reflected Brownian motion

From Wikipedia, the free encyclopedia

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

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)+RY(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

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

One dimension

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

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

One dimension

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

One dimension

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

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

Other boundary conditions

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

See also

References

  1. ↑ Dieker, A. B. (2011). "Reflected Brownian Motion". Wiley Encyclopedia of Operations Research and Management Science. doi:10.1002/9780470400531.eorms0711. ISBN 9780470400531. 
  2. ↑ 2.0 2.1 2.2 2.3 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. 
  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. 
  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. 
  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. 
  7. ↑ 7.0 7.1 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. 
  8. ↑ 8.0 8.1 8.2 8.3 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. 
  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. 
  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. 
  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. 
  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. 
  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. 
  16. ↑ 16.0 16.1 16.2 16.3 16.4 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. 
  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. 
  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. 
  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. 
Single queueing nodes
Queueing networks
Service policies
Key concepts
Limit theorems
Extensions
Category
This article is issued from Wikipedia. The text is available under the Creative Commons Attribution/Share Alike; additional terms may apply for the media files.