RUS  ENG
Full version
JOURNALS // Teoriya Veroyatnostei i ee Primeneniya // Archive

Teor. Veroyatnost. i Primenen., 1969 Volume 14, Issue 3, Pages 393–420 (Mi tvp1195)

This article is cited in 21 papers

Combinatorial algebra and random graphs

V. E. Stepanov

Moscow

Abstract: Let $A$ be a finite set of vertices and $\lambda_a>0$ be the intensity of the vertex $a\in A$. A random time-dependent graph $\mathscr G_L(A\mid t)$ is defined as follows: at time $t=0$ all the vertices are isolated; the probability that at time $t>0$ vertices $a$ and $b$ are connected equals $1-e^{-\lambda}a^\lambda b^t$, and the connections appear independently for different pairs, let $\mathbf P_L(A\mid t)$ be the probability that the random graph $\mathscr G_L(A\mid t)$ is connected.
In the paper, an explicit expression for $\mathbf P_L(A\mid t)$ is found, a number of combinatorial relations including the probabilities $\mathbf P_L(A\mid t)$ is obtained, and it is proved that if the set of vertices $A$, intensities of vertices $\lambda_a$, and time $t$ are changed in a certain way, then, under some conditions, $\mathbf P_L(A\mid t)e^{\mu(A\mid t)}\to1$, where
$$ \mu(A\mid t)=\sum_{a\in A}\exp\{-t\lambda_aL(A)\}\quad\text{and}\quad L(A)=\sum_{a\in A}\lambda_a. $$


Received: 05.11.1967


 English version:
Theory of Probability and its Applications, 1969, 14:3, 373–399

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024