Hostname: page-component-cd9895bd7-fscjk Total loading time: 0 Render date: 2024-12-23T09:54:46.152Z Has data issue: false hasContentIssue false
  • English
  • Français

The Central Limit Theorem and the Law of Large Numbers for Pair-Connectivity in Bernoulli Trees

Published online by Cambridge University Press:  27 July 2009

Kyle T. Siegrist ,
Ashok T. Amin  and
Peter J. Slater
Kyle T. Siegrist
Affiliation:
Department of Mathematical SciencesThe University of Alabama in Huntsville Huntsville, Alabama 35899
Ashok T. Amin
Affiliation:
Department of Computer ScienceThe University of Alabama in HuntsvilleHuntsville, Alabama 35899
Peter J. Slater
Affiliation:
Department of Mathematical SciencesThe University of Alabama in Huntsville Huntsville, Alabama 35899
Get access Rights & Permissions [Opens in a new window]

Abstract

Consider the standard network reliability model in which each edge of a given (n, m)-graph G is deleted, independently of all others, with probability q = 1– p (0 <p < 1). The pair-connectivity random variable X is defined to be the number of connected pairs of vertices that remain in G. The mean of X has been proposed as a measure of reliability for failure-prone communications networks in which the edge deletions correspond to failures of the communications links. We consider deviations from the mean, the law of large numbers, and the central limit theorem for X as n → ∞. Some explicit results are obtained when G is a tree using martingale difference sequences. Stars and paths are treated in detail.

Type
Articles
Information
Probability in the Engineering and Informational Sciences , Volume 3 , Issue 4 , October 1989 , pp. 477 - 491
Copyright
Copyright © Cambridge University Press 1989

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Amin, A.T., Siegrist, K.T., & Slater, P.J. (1989). On the expected number of pairs of connected nodes: pair-connected reliability. To appear in Computers and Mathematics with Applications.Google Scholar
Amin, A.T., Siegrist, K.T., & Slater, P.J. (1987). Pair-connected reliability of a tree and its distance degree sequences. Congressus Numerantium 58: 29–42.Google Scholar
Amin, A.T., Siegrist, K.T., & Slater, P.J. (1987). Exact formulas for reliability measures for various classes of graphs. Congressus Numerantium 58: 43–52.Google Scholar
Billingsley, P. (1979). Probability and measure. New York: Wiley.Google Scholar
Birnbaum, Z.W., Esary, J.D., & Saunders, S.C. (1961). Multicomponent systems and structures and their reliability. Technometrics 3: 55–77.CrossRefGoogle Scholar
Clark, B.N., Neufeld, E.M., & Colbourn, C.J. (1986). Maximizing the mean number of communicating vertex pairs in series parallel networks. IEEE Transactions on Reliability R-35: 247–251.CrossRefGoogle Scholar
Colbourn, C.J. (1989). Network resilience. To appear in Computers and Mathematics with Applications.Google Scholar
Cox, J.T. & Grimmett, G. (1981). Central limit theorems for percolation models. Journal of Statistical Physics 25: 237–251.CrossRefGoogle Scholar
Esary, J.D. & Proschan, F. (1963). Coherent structures of non-identical components. Technometrics 5: 191–209.CrossRefGoogle Scholar
Feller, W. (1968). An introduction to probability theory and its applications, Vol. 1, 3rd edition. New York: Wiley.Google Scholar
Kesten, H. (1982). Percolation theory for mathematicians. Boston: Birkhäuser. 1982.CrossRefGoogle Scholar
McLeish, D.L. (1974). Dependent central limit theorems and invariance principles. Annals of Probability 2: 620–628.CrossRefGoogle Scholar
Moore, E.F. & Shannon, C.E. (1956). Reliable circuits using less reliable relays. Journal of the Franklin Institute 262: 191–208 and 281–297.CrossRefGoogle Scholar
Rhee, W.T. & Talagrand, M. (1987). Martingale inequalities and NP-complete problems. Mathematics of Operations Research 12: 177–181.CrossRefGoogle Scholar