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 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]

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) ∈ , t ≥ 0.

The reflection matrix describes boundary behaviour. In the interior of the process behaves like a Wiener process, on the boundary "roughly speaking, Z is pushed in direction Rj whenever the boundary surface 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.

Marginal and stationary distribution[edit]

One dimension[edit]

The marginal distribution (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

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

For fixed t, the distribution of Z(t) coincides with the distribution of the running maximum M(t) of the Brownian motion,

But be aware that the distributions of the processes as a whole are very different. In particular, M(t) is increasing in t, which is not the case for Z(t).

The heat kernel for reflected Brownian motion at :

For the plane above

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]

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

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]

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. 
  2. ^ a b c Harrison, J. Michael (1985). Brownian Motion and Stochastic Flow Systems (PDF). 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. doi:10.2307/3518347. JSTOR 3518347. Retrieved 30 Nov 2012. 
  6. ^ Iglehart, Donald L.; Ward, Whitt (1970). "Multiple Channel Queues in Heavy Traffic. II: Sequences, Networks, and Batches" (PDF). Advances in Applied Probability. Applied Probability Trust. 2 (2): 355–369. doi:10.2307/1426324. JSTOR 1426324. Retrieved 30 Nov 2012. 
  7. ^ a b Harrison, J. M.; Williams, R. J. (1987). "Brownian models of open queueing networks with homogeneous customer populations" (PDF). Stochastics. 22 (2): 77. doi:10.1080/17442508708833469. 
  8. ^ a b c d Bramson, M.; Dai, J. G.; Harrison, J. M. (2010). "Positive recurrence of reflecting Brownian motion in three dimensions" (PDF). 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. doi:10.1214/aoap/1177005979. JSTOR 2959623. Retrieved 5 December 2012. 
  14. ^ Dai, Jiangang "Jim" (1990). "Steady-state analysis of reflected Brownian motions: characterization, numerical methods and queueing applications (Ph. D. thesis)" (PDF). Stanford University. Dept. of Mathematics. Retrieved 5 December 2012.  |chapter= ignored (help)
  15. ^ Dai, J. G.; Harrison, J. M. (1992). "Reflected Brownian Motion in an Orthant: Numerical Methods for Steady-State Analysis" (PDF). The Annals of Applied Probability. Institute of Mathematical Statistics. 2 (1): 65–86. doi:10.1214/aoap/1177005771. JSTOR 2959654. 
  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. 
  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" (PDF). Probab. Statist. Group Manchester Research Report (5).  line feed character in |title= at position 34 (help)
  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.