Limit Theorems for Sums of Independent Random Variables
in Applied Problems of Probabilistic Combinatorics

Kolchin, Valentin (Moscow, Russia)
kolchin@mi.ras.ru

In several last decades the so called generalized scheme of allocating particles found a wide spread in enumeration problems of combinatorics [1,2]. Non-negative integer-valued random variables $\eta_1,\ldots,\eta_N$ form a generalized scheme of allocating n particles to N cells if there exist independent random variables $\xi_1,\ldots,\xi_N$ such that for any non-negative integers $n_1,\ldots,n_N$

$$\mathsf P\{\eta_1=n_1,\ldots,\eta_N=n_N\}=\mathsf P\{\xi_1=n_1,\ldots,\xi_N=n_N\mid \xi_1+\ldots+\xi_N=n\}.$$

In view of the independence of the random variables $\xi_1,\ldots,\xi_N$, the study of some characteristics of the random variables $\eta_1,\ldots,\eta_N$ is reduced to problems concerning sums of independent summands [1-3].

In some cases, in generalized schemes of allocating particles there exists an effect similar to the phase transition and appearance of the so called giant component in evolution of random graphs.

For a sequence of random graphs G_n,N with n vertices and N edges, as $n\to\infty$, the parameter $\alpha=n/N$ is usually considered as time, if the parameter $\alpha$ goes through the value 1, the properties of the graphs are changed abruptly [4]. Let $n,N\to\infty$ in such a way that $\alpha\to\lambda$.If $\lambda<1$, then with probability tending to one each component of the graph G_n,N contains no more than one cycle and its size does not exceed $c_\lambda\ln n$, where $c_\lambda$is a constant. If $\lambda\gt 1$, then with probability tending to one there is a giant component with the number of vertices of order n , and each of the remaining components contains no more that one cycle and its size does not exceed $c_\lambda\ln n$. Thus, if $n,N\to\infty$and the parameter $\alpha$ goes through the value one, then with probability tending to one the giant components appears and the number of its vertices is of order n and is greater in order than all the other components.

We say that the giant component appears in a generalized scheme of allocating if, as $n,N\to\infty$ and the ratio $\alpha=n/N$ increases, the maximum of the random variables $\eta_1,\ldots,\eta_N$ with probability tending to one is of order n and the second order statistic has a limit distribution with normalizing constant of less order than n .

In some generalized schemes, as $n,N\to\infty$ and the ratio $\alpha=n/N$ increases, the giant component appears [5,6], and in others there is no giant component even as $\alpha$ tends to infinity [2,7].

In my talk, example of generalized schemes of allocating n particles to N cells are given which illustrate the situations where a giant component appears and where this property does no appear if $\alpha=n/N$ increases as $nN\to\infty$.The giant component appears in the generalized schemes corresponding to the classical allocating problem [2], random partitions of integers [7], random partitions of a finite set. On the other hand, it is proved that the giant component appears in the generalized schemes corresponding random forests of rooted and unrooted trees [5,6]. In is not known whether a giant component exists in random permutations with N cycles and in the graph of random mapping with N components.

Note that the general results on the distributions of the order statistics in generalized schemes are not enough to clarify what properties of the random variables $\xi_1,\ldots,\xi_N$ influence on the existence of the giant component in the scheme generated by these variables. This question remains open for the scheme of sequential allocating particles to cell with probabilities of hitting cells dependent of the contents of the cells.

An effect similar to the appearance of a giant component is observed in the processes of aggregating particles [8, 9].

References

1. V.F. Kolchin, A class of limit theorems for conditional distributions. Liet. Mat. Rink. (1968) 8, 1, 53-63.

2. V.F. Kolchin, B.A. Sevastyanov, and V.P. Chistyakov, Random Allocations. Wiley, New York, 1978.

3. V.F. Kolchin, Random Mappings. Optimization Software, New York, 1986.

4. P. Erdos, and A. Renyi, On the evolution of random graphs. Publ. Math. Inst. Hungarian Acad. Sci., Ser A (1960) 5, 17-61.

5. I.A. Cheplyukova, Emergence of the giant tree in a random forest. Discrete Math. Appl. (1998) 1, 17-34.

6. T. uczak, B. Pittel, Components of random forests. Combinatorics, Probability and Computing (1992) 1, 35-52.

7. A.N. Trunov, Limit theorems in the problem of distributing identical particles in different cells. -Proc. Steklov Institute Math. (1988) 177, 157-175.

8. V.F. Kolchin, Processes of aggregation of particles. In: Abstr. 2nd Colloq.on Stochastic Methods. TVP, Moscow, 1995, pp.74-75.

9. V.F. Kolchin, Comparison theorems for processes of aggregation of particles. In: Abstr. 3rd Colloq. on Stochastic Methods. TVP, Moscow, 1996, pp.84-85.