Home | Contents | Submissions, editors, etc. | Login | Search | ECP
 Electronic Journal of Probability > Vol. 7 (2002) > Paper 5 open journal systems 


Non-Colliding Random Walks, Tandem Queues, and Discrete Orthogonal Polynomial Ensembles

Wolfgang König, BRIMS, Hewlett-Packard Laboratories
Neil O'Connell, BRIMS, Hewlett-Packard Laboratories
Sébastien Roch, École Polytechnique


Abstract
We show that the function h(x)=prodi < j(xj-xi) is harmonic for any random walk in Rk with exchangeable increments, provided the required moments exist. For the subclass of random walks which can only exit the Weyl chamber W={x: x1 < x2 < ... < xk} onto a point where h vanishes, we define the corresponding Doob h-transform. For certain special cases, we show that the marginal distribution of the conditioned process at a fixed time is given by a familiar discrete orthogonal polynomial ensemble. These include the Krawtchouk and Charlier ensembles, where the underlying walks are binomial and Poisson, respectively. We refer to the corresponding conditioned processes in these cases as the Krawtchouk and Charlier processes. In [O'Connell and Yor (2001b)], a representation was obtained for the Charlier process by considering a sequence of M/M/1 queues in tandem. We present the analogue of this representation theorem for the Krawtchouk process, by considering a sequence of discrete-time M/M/1 queues in tandem. We also present related results for random walks on the circle, and relate a system of non-colliding walks in this case to the discrete analogue of the circular unitary ensemble (CUE).


Full text: PDF

Pages: 1-24

Published on: October 12, 2001
Bibliography
  1. S. Asmussen (1987), Applied Probability and Queues, Wiley. Math. Review 89a:60208
  2. J. Baik (2000), Random vicious walks and random matrices, Comm. Pure Appl. Math. 53, 1385-1410. Math. Review CMP 1 773 413
  3. J. Baik, P. Deift and K. Johansson (1999), On the distribution of the length of the longest increasing subsequence of random permutations, J. Amer. Math. Soc. 12, no. 4, 1119-1178. Math. Review 2000e:05006
  4. Yu. Baryshnikov (2001), GUES and queues, Probab. Theor. Rel. Fields 119, 256-274. Math. Review 1 818 248
  5. Ph. Biane (1994), Quelques propriétés du mouvement brownien dans un cone. Stoch. Proc. Appl. 53, no. 2, 233-240. Math. Review 95j:60129
  6. Ph. Bougerol and Th. Jeulin, Paths in Weyl chambers and random matrices, In preparation, Math. Review number not available.
  7. P. Brémaud (1981), Point Processes and Queues: Martingale Dynamics, Springer, Berlin. Review 82m:60058
  8. P. Brémaud (1999), Markov Chains, Gibbs Fields, Monte-Carlo Simulation, and Queues, Texts in App. Maths., vol. 31, Springer. Review 2000k:60137
  9. P.J. Burke (1956), The output of a queueing system, Operations Research 4, no. 6, 699-704, Math. Review number not available.
  10. J.N. Darroch and E. Seneta (1965), On quasi-stationarity distributions in absorbing discrete-time finite Markov chains, J. App. Prob. 2, 88-100. Math. Review 35 #3731
  11. J.L. Doob (1984), Classical Potential Theory and its Probabilistic Counterpart, Springer. Math. Review 85k:31001
  12. F.J Dyson (1962), A Brownian-motion model for the eigenvalues of a random matrix. J. Math. Phys. 3, 1191-1198. Math. Review 26 #5904
  13. P.J. Forrester (1999), Random walks and random permutations, preprint, (xxx: math.CO/9907037), Math. Review number not available.
  14. P.W. Glynn and W. Whitt (1991), Departures from many queues in series, Ann. Appl. Prob. 1, no. 4, 546-572. Math. Review 92i:60162
  15. D. Grabiner (1999), Brownian motion in a Weyl chamber, non-colliding particles, and random matrices. Ann. Inst. H. Poincaré Probab. Statist. 35, no. 2, 177-204. Math. Review 2000i:60091
  16. J. Gravner, C.A. Tracy and H. Widom (2001), Limit theorems for height fluctuations in a class of discrete space and time growth models, J. Stat. Phys. 102, nos. 5-6, 1085-1132. Math. Review CMP 1 830 441
  17. J.M. Harrison and R.J. Williams (1990), On the quasireversibility of a multiclass Brownian service station, Ann. Probab. 18, 1249-1268. Math. Review 91i:60204
  18. D. Hobson and W. Werner (1996), Non-colliding Brownian motion on the circle, Bull. Math. Soc. 28, 643-650. Math. Review 97k:60217
  19. K. Johansson (2001), Discrete orthogonal polynomial ensembles and the Plancherel measure, Ann. Math. (2) 253, no. 1, 259--296. Math. Review CMP 1 826 414
  20. K. Johansson (2000), Shape fluctuations and random matrices, Commun. Math. Phys. 209, 437-476. Math. Review 2001h:60177
  21. K. Johansson (2000), Non-intersecting paths, random tilings and random matrices, preprint, Math. Review number not available.
  22. S.P. Karlin and G. MacGregor (1959), Coincidence probabilities, Pacif. J. Math. 9, 1141-1164. Math. Review 22:5072
  23. F.P. Kelly (1979), Reversibility and Stochastic Networks, Wiley. Math. Review 81j:60105
  24. W. König and Neil O'Connell (2001), Eigenvalues of the Laguerre process as non-colliding squared Bessel processes, ECP, Vol. 6 (2001) Paper no. 11, pages 107-114, Math. Review number not available.
  25. M.L. Mehta (1991), Random Matrices. Second Edition, Academic Press. Math. Review 92f:82002
  26. H. Minc (1988), Nonnegative Matrices, Wiley. Math. Review 89i:15001
  27. Neil O'Connell and Marc Yor (2001), Brownian analogues of Burke's theorem, Stoch. Proc. Appl., 96 (2001), no. 2, 285--30, Math. Review 1 865 759
  28. Neil O'Connell and Marc Yor (2001), A representation for non-colliding random walks, ECP, Vol. 7 (2002) Paper no. 1, pages 1-12, Math. Review number not available.
  29. V.V. Petrov (1975), Sums of Independent Random Variables, Springer, Berlin. Math. Review 52 #9335
  30. R.G. Pinsky (1985), On the convergence of diffusion processes conditioned to remain in a bounded region for large time to limiting positive recurrent diffusion processes, Ann. Prob. 13:2, 363-378. Math. Review 86i:60201
  31. J.W. Pitman (1975), One-dimensional Brownian motion and the three-dimensional Bessel process, Adv. Appl. Probab. 7, 511-526. Math. Review 51 #11677
  32. J.W. Pitman and L.C.G. Rogers (1981), Markov functions, Ann. Probab. 9, 573-582. Math. Review 82j:60133
  33. E. Reich (1957), Waiting times when queues are in tandem, Ann. Math. Statist. 28, 768-773. Math. Review 19,1203b
  34. Ph. Robert (2000), Réseaux et files d'attente: méthodes probabilistes, Math. et Applications, vol. 35. Springer, Math. Review number not available.
  35. C.A. Tracy and H. Widom (1994), Fredholm determinants, differential equations and matrix models, Comm. Math. Phys. 163, no. 1, 33-72. Math. Review 95e:82005
  36. David Williams (1979), Diffusions, Markov Processes, and Martingales. Volume 1: Foundations. Wiley. Math. Review 80i:60100













Research
Support Tool
Capture Cite
View Metadata
Printer Friendly
Context
Author Address
Action
Email Author
Email Others


Home | Contents | Submissions, editors, etc. | Login | Search | ECP

Electronic Journal of Probability. ISSN: 1083-6489