Hostname: page-component-78c5997874-s2hrs Total loading time: 0 Render date: 2024-11-05T09:21:30.505Z Has data issue: false hasContentIssue false
  • English
  • Français

Ballots, queues and random graphs

Published online by Cambridge University Press:  14 July 2016

Lajos Takács
Lajos Takács*
Affiliation:
Case Western Reserve University
*
∗Postal address: Department of Mathematics and Statistics, Case Western Reserve University, Cleveland, Ohio 44106, USA.
Get access Rights & Permissions [Opens in a new window]

Abstract

This paper demonstrates how a simple ballot theorem leads, through the interjection of a queuing process, to the solution of a problem in the theory of random graphs connected with a study of polymers in chemistry. Let Γn(p) denote a random graph with n vertices in which any two vertices, independently of the others, are connected by an edge with probability p where 0 < p < 1. Denote by ρ n(s) the number of vertices in the union of all those components of Γn(p) which contain at least one vertex of a given set of s vertices. This paper is concerned with the determination of the distribution of ρ n(s) and the limit distribution of ρ n(s) as n → ∞and ρ → 0 in such a way that np → a where a is a positive real number.

Keywords

CONNECTEDNESSEXACT AND LIMIT DISTRIBUTIONS
Type
Research Papers
Information
Journal of Applied Probability , Volume 26 , Issue 1 , March 1989 , pp. 103 - 112
Copyright
Copyright © Applied Probability Trust 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.)

Footnotes

Research supported by National Science Foundation Grant DMS-85-10073 and Office of Naval Research Grant N0001485-K-009.

References

[1] Andre, D. (1887) Solution directe du problème résolu par M. Bertrand. C. R. Acad. Sci. Paris 105, 436–437.Google Scholar
[2] Bertrand, J. (1887) Solution d'un problème. C. R. Acad. Sci. Paris 105, 369.Google Scholar
[3] Kennedy, J. W. (1978) Random clumps, graphs, and polymer solutions. Theory and Applications of Graphs. Edited by Alavi, Y. and Lick, D. R. Lecture Notes in Mathematics 642. Springer-Verlag, Berlin, pp. 314–329.Google Scholar
[4] Takács, L. (1955) Investigation of waiting time problems by reduction to Markov processes. Acta Math. Acad. Sci. Hangar. 6, 101–129.Google Scholar
[5] Takács, L. (1962) A generalization of the ballot problem and its application in the theory of queues. J. Amer. Stat. Assoc. 57, 327–337.Google Scholar
[6] Takács, L. (1963) The stochastic law of the busy period for a single server queue with Poisson input. J. Math. Anal. Appl. 6, 33–42.Google Scholar
[7] Takács, L. (1967) Combinatorial Methods in the Theory of Stochastic Processes. Wiley, New York.Google Scholar