Poisson convergence and Poisson processes with applications to random graphs. (English) Zbl 0633.60070
The author uses the Stein-Chen method to establish conditions under which a sequence of sums of dependent indicator random variables converges in distribution to a Poisson limit. The result is then extended to provide new sufficient conditions for the convergence of weakly dependent point processes to a Poisson point process.
The theorems are applied to a variety of attractive problems from random graph theory, including that of finding the approximate distribution of the size of the first cycle in a graph with a large number of vertices, when edges are added one by one at random.
The theorems are applied to a variety of attractive problems from random graph theory, including that of finding the approximate distribution of the size of the first cycle in a graph with a large number of vertices, when edges are added one by one at random.
Reviewer: A.D.Barbour
MSC:
| 60G55 | Point processes (e.g., Poisson, Cox, Hawkes processes) |
| 60F17 | Functional limit theorems; invariance principles |
| 05C80 | Random graphs (graph-theoretic aspects) |
| 05C38 | Paths and cycles |
Keywords:
Stein-Chen method; convergence of weakly dependent point processes to a Poisson point process; random graph theory; graph with a large number of verticesReferences:
| [1] | Barbour, A. D., Poisson convergence and random graphs, (Math. Proc. Camb. Phil. Soc., 92 (1982)), 349-359 · Zbl 0498.60016 |
| [2] | Barbour, A. D.; Eagleson, G. K., Poisson approximation for some statistics based on exchangeable trials, Adv. Appl. Prob., 15, 585-600 (1983) · Zbl 0511.60025 |
| [3] | Barbour, A. D.; Eagleson, G. K., Poisson convergence for dissociated statistics, J.R. Statist. Soc. Ser. B, 46, 397-402 (1984) · Zbl 0567.62062 |
| [4] | Berman, M.; Eagleson, G. K., A Poisson limit theorem for incomplete symmetric statistics, J. Appl. Probab., 20, 47-60 (1982) · Zbl 0528.60040 |
| [5] | Billingsley, P., Convergence of Probability Measures (1968), John Wiley & Sons: John Wiley & Sons New York, etc. · Zbl 0172.21201 |
| [6] | Bollobás, B., Random Graphs (1985), Academic Press: Academic Press London, etc. · Zbl 0567.05042 |
| [7] | Chen, L. H.Y., Two central limit problems for dependent random variables, Z. Wahrsch. Verw. Geb., 43, 223-243 (1978) · Zbl 0364.60049 |
| [8] | Dante Alighieri, Divina Commedia (Florence, 1321).; Dante Alighieri, Divina Commedia (Florence, 1321). |
| [9] | Eagleson, G. K., A Poisson limit theorem for weakly exchangeable events, J. Appl. Probab., 16, 794-802 (1979) · Zbl 0424.60026 |
| [10] | Erdös, P.; Rényi, A., On the evolution of random graphs, Magyar Tud. Akad. Mat. Kut. Int. Közl., 5, 17-61 (1960) · Zbl 0103.16301 |
| [11] | P. Flajolet, personal communication.; P. Flajolet, personal communication. |
| [12] | Jammalamadaka, S. R.; Janson, S., Limit theorems for a triangular scheme of \(U\)-statistics with applications to inter-point distances, Ann. Probab., 14, 1347-1358 (1986) · Zbl 0604.60023 |
| [13] | Janson, S., Random trees in a graph and trees in a random graph, (Math. Proc. Camb. Phil. Soc., 100 (1986)), 319-330 · Zbl 0622.60018 |
| [14] | Kallenberg, O., Random Measures (1983), Akademie-Verlag: Akademie-Verlag Berlin · Zbl 0288.60053 |
| [15] | Karónski, M., Balanced subgraphs of large random graphs (1984), Adam Mickiewicz University: Adam Mickiewicz University Poznań · Zbl 0558.05056 |
| [16] | McDiarmid, C., Colouring random graphs, Ann. Operations Research, 1, 183-200 (1984) · Zbl 0673.05037 |
| [17] | McGinley, W. G.; Sibson, R., Dissociated random variables, (Math. Proc. Camb. Phil. Soc., 77 (1975)), 185-188 · Zbl 0353.60018 |
| [18] | Nowicki, K., Poisson limit distribution of incomplete \(U\)-statistics with application to graph theory, (Report (1986), University of Lund) |
| [19] | Palmer, E., Graphical Evolution, ((1985), John Wiley & Sons: John Wiley & Sons New York), etc. · Zbl 0566.05002 |
| [20] | Poisson, S. D., Recherches sur la probabilité des jugements en matière criminelle et en matière civile (1837), Paris |
| [21] | Silverman, B.; Brown, T., Short distances, flat triangles and Poisson limits, J. Appl. Probab., 15, 815-825 (1978) · Zbl 0396.60029 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
