American Institute of Mathematical Sciences

Advanced
October  2012, 8(4): 877-894. doi: 10.3934/jimo.2012.8.877

Networks with cascading overloads

Jesse Collingwood 1, , Robert D. Foley 2, and  David R. McDonald 1,

1. 

Department of Mathematics and Statistics, University of Ottawa, 585 King Edward Avenue, Ottawa, Ontario K1N 6M8, Canada, Canada
2. 

Industrial and Systems Engineering, Georgia Institute of Technology, Groseclose Building, Room 428, Atlanta GA 30332-0205, United States

Received  September 2011 Revised  July 2012 Published  September 2012

Here we study large deviations in networks that are more likely to result from the accumulation of many slightly unusual events. We are particularly interested in analyzing large deviations where the most probable path changes direction. These deviations arise when a large deviation in one part of the system cascades across the network to produce a large deviation in another part of the network. Our technique involves the construction of an approximate time reversal. We also use this approximate time reversal to do rare event simulation.
Keywords: Markov chains., approximate time reversal, change of measure, Rare events, exact asymptotics, large deviations, importance sampling.
Mathematics Subject Classification: Primary: 60J20, 60K2.
Citation: Jesse Collingwood, Robert D. Foley, David R. McDonald. Networks with cascading overloads. Journal of Industrial & Management Optimization, 2012, 8 (4) : 877-894. doi: 10.3934/jimo.2012.8.877
References:
[1]

Queueing Syst., 62 (2009), 311-344. doi: 10.1007/s11134-009-9140-y.  Google Scholar

[2]

Research Report, RC 16280, Computer Science Division, IBM T. J. Watson Center, Yorktown Heights, New York. Google Scholar

[3]

Springer Verlag, 2003.  Google Scholar

[4]

Stochastic Processes and their Applications, 89 (1997), 141-173. doi: 10.1016/S0304-4149(00)00018-1.  Google Scholar

[5]

Siberian Mathematical Journal, 4 (2001), 245-270. doi: 10.1023/A:1004832928857.  Google Scholar

[6]

Annals of Applied Probability, 11 (2001), 569-607.  Google Scholar

[7]

Ann. Appl. Probab., 15 (2004), 519-541. doi: 10.1214/105051604000000666.  Google Scholar

[8]

Annals of Applied Probability, 15 (2005), 542-–586. doi: 10.1214/105051604000000675.  Google Scholar

[9]

R. D. Foley and D. R. McDonald, Constructing a harmonic function for an irreducible non-negative matrix with convergence parameter $R > 1$,, Accepted subject to revisions London Mathematical Society., ().   Google Scholar

[10]

Ann. Probab, 38 (2010), 1106-1142. doi: 10.1214/09-AOP506.  Google Scholar

[11]

Stoch. Proc. Appl., 6 (1978), 223-240. doi: 10.1016/0304-4149(78)90020-0.  Google Scholar

[12]

preprint. 2008. Google Scholar

[13]

Springer-Verlag, London. 1993.  Google Scholar

[14]

Advances in Applied Probability, 36 (2004), 1231-1251. doi: 10.1239/aap/1103662965.  Google Scholar

[15]

ACM Transactions on Modeling and Computer Simulation, 17 (2007). Google Scholar

show all references

References:
[1]

Queueing Syst., 62 (2009), 311-344. doi: 10.1007/s11134-009-9140-y.  Google Scholar

[2]

Research Report, RC 16280, Computer Science Division, IBM T. J. Watson Center, Yorktown Heights, New York. Google Scholar

[3]

Springer Verlag, 2003.  Google Scholar

[4]

Stochastic Processes and their Applications, 89 (1997), 141-173. doi: 10.1016/S0304-4149(00)00018-1.  Google Scholar

[5]

Siberian Mathematical Journal, 4 (2001), 245-270. doi: 10.1023/A:1004832928857.  Google Scholar

[6]

Annals of Applied Probability, 11 (2001), 569-607.  Google Scholar

[7]

Ann. Appl. Probab., 15 (2004), 519-541. doi: 10.1214/105051604000000666.  Google Scholar

[8]

Annals of Applied Probability, 15 (2005), 542-–586. doi: 10.1214/105051604000000675.  Google Scholar

[9]

R. D. Foley and D. R. McDonald, Constructing a harmonic function for an irreducible non-negative matrix with convergence parameter $R > 1$,, Accepted subject to revisions London Mathematical Society., ().   Google Scholar

[10]

Ann. Probab, 38 (2010), 1106-1142. doi: 10.1214/09-AOP506.  Google Scholar

[11]

Stoch. Proc. Appl., 6 (1978), 223-240. doi: 10.1016/0304-4149(78)90020-0.  Google Scholar

[12]

preprint. 2008. Google Scholar

[13]

Springer-Verlag, London. 1993.  Google Scholar

[14]

Advances in Applied Probability, 36 (2004), 1231-1251. doi: 10.1239/aap/1103662965.  Google Scholar

[15]

ACM Transactions on Modeling and Computer Simulation, 17 (2007). Google Scholar

[1]

Tatsuaki Kimura, Hiroyuki Masuyama, Yutaka Takahashi. Light-tailed asymptotics of GI/G/1-type Markov chains. Journal of Industrial & Management Optimization, 2017, 13 (4) : 2093-2146. doi: 10.3934/jimo.2017033
[2]

Idriss Mazari. Trait selection and rare mutations: The case of large diffusivities. Discrete & Continuous Dynamical Systems - B, 2019, 24 (12) : 6693-6724. doi: 10.3934/dcdsb.2019163
[3]

Koen De Turck, Sabine Wittevrongel. Receiver buffer behavior for the selective repeat protocol over a wireless channel: An exact and large-deviations analysis. Journal of Industrial & Management Optimization, 2010, 6 (3) : 603-619. doi: 10.3934/jimo.2010.6.603
[4]

Miguel Abadi, Sandro Vaienti. Large deviations for short recurrence. Discrete & Continuous Dynamical Systems, 2008, 21 (3) : 729-747. doi: 10.3934/dcds.2008.21.729
[5]

Jerry L. Bona, Laihan Luo. Large-time asymptotics of the generalized Benjamin-Ono-Burgers equation. Discrete & Continuous Dynamical Systems - S, 2011, 4 (1) : 15-50. doi: 10.3934/dcdss.2011.4.15
[6]

Jean Dolbeault, Giuseppe Toscani. Fast diffusion equations: Matching large time asymptotics by relative entropy methods. Kinetic & Related Models, 2011, 4 (3) : 701-716. doi: 10.3934/krm.2011.4.701
[7]

Sandra Cerrai, Mark Freidlin, Michael Salins. On the Smoluchowski-Kramers approximation for SPDEs and its interplay with large deviations and long time behavior. Discrete & Continuous Dynamical Systems, 2017, 37 (1) : 33-76. doi: 10.3934/dcds.2017003
[8]

Dongmei Zheng, Ercai Chen, Jiahong Yang. On large deviations for amenable group actions. Discrete & Continuous Dynamical Systems, 2016, 36 (12) : 7191-7206. doi: 10.3934/dcds.2016113
[9]

Salah-Eldin A. Mohammed, Tusheng Zhang. Large deviations for stochastic systems with memory. Discrete & Continuous Dynamical Systems - B, 2006, 6 (4) : 881-893. doi: 10.3934/dcdsb.2006.6.881
[10]

Kenrick Bingham, Yaroslav Kurylev, Matti Lassas, Samuli Siltanen. Iterative time-reversal control for inverse problems. Inverse Problems & Imaging, 2008, 2 (1) : 63-81. doi: 10.3934/ipi.2008.2.63
[11]

Rodrigo I. Brevis, Jaime H. Ortega, David Pardo. A source time reversal method for seismicity induced by mining. Inverse Problems & Imaging, 2017, 11 (1) : 25-45. doi: 10.3934/ipi.2017002
[12]

Yakov Pesin. On the work of Sarig on countable Markov chains and thermodynamic formalism. Journal of Modern Dynamics, 2014, 8 (1) : 1-14. doi: 10.3934/jmd.2014.8.1
[13]

Felix X.-F. Ye, Yue Wang, Hong Qian. Stochastic dynamics: Markov chains and random transformations. Discrete & Continuous Dynamical Systems - B, 2016, 21 (7) : 2337-2361. doi: 10.3934/dcdsb.2016050
[14]

Yongqiang Suo, Chenggui Yuan. Large deviations for neutral stochastic functional differential equations. Communications on Pure & Applied Analysis, 2020, 19 (4) : 2369-2384. doi: 10.3934/cpaa.2020103
[15]

Thomas Bogenschütz, Achim Doebler. Large deviations in expanding random dynamical systems. Discrete & Continuous Dynamical Systems, 1999, 5 (4) : 805-812. doi: 10.3934/dcds.1999.5.805
[16]

E. Almaraz, A. Gómez-Corral. On SIR-models with Markov-modulated events: Length of an outbreak, total size of the epidemic and number of secondary infections. Discrete & Continuous Dynamical Systems - B, 2018, 23 (6) : 2153-2176. doi: 10.3934/dcdsb.2018229
[17]

Josef DiblÍk, Rigoberto Medina. Exact asymptotics of positive solutions to Dickman equation. Discrete & Continuous Dynamical Systems - B, 2018, 23 (1) : 101-121. doi: 10.3934/dcdsb.2018007
[18]

Zvi Drezner, Carlton Scott. Approximate and exact formulas for the $(Q,r)$ inventory model. Journal of Industrial & Management Optimization, 2015, 11 (1) : 135-144. doi: 10.3934/jimo.2015.11.135
[19]

Albert Fannjiang, Knut Solna. Time reversal of parabolic waves and two-frequency Wigner distribution. Discrete & Continuous Dynamical Systems - B, 2006, 6 (4) : 783-802. doi: 10.3934/dcdsb.2006.6.783
[20]

Kazufumi Ito, Karim Ramdani, Marius Tucsnak. A time reversal based algorithm for solving initial data inverse problems. Discrete & Continuous Dynamical Systems - S, 2011, 4 (3) : 641-652. doi: 10.3934/dcdss.2011.4.641

2019 Impact Factor: 1.366

Tools

Metrics

  • PDF downloads (53)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences