О выборе распределения случайных графов

[maxal]

Добавил в OEIS еще 4 последовательности A125208-A125210,A127258 с коэффициентами многочленов $\alpha_n(p)$ и дуальных к ним.

Добавлено спустя 8 минут 7 секунд:

Некоторые интересные свойства для исследования:
1) Верно ли, что A125210(n,2)=0 для всех n ?
2) Верно ли, что A125208(n,n-1)=n для n>=3 ?
3) Верно ли, что для n>=4 третий ненулевой коэффициент в n-ом ряду A125208 - это A125208(n,2n-4) ?
4) Для каких n, A125208(n,2n-4) = -A125208(n,2n-3) ? Это так по крайней мере для n=5,7,8,9,10.

На первый взгляд свойства 1,2 просто доказать, а 3,4 будут посложнее.

[maxal]

M214 писал(а):

Получилось найти выражение для вероятности существования пути между двумя произвольными элементами. При больших N зависимость имеет вид:

\[ \tau \left( {p,N} \right) = \frac{1}{e} \cdot \sum\limits_{i = 1}^{N - 1} {\frac{{\rho ^i }}{{\left( {n - i - 1} \right)!}}} \]

. Здесь \rho = 1-p.

Только вот непонятно, насколько точная у вас формула.

Кстати, вот тут решали похожую задачи: какова вероятность того, что в случайном графе на $n$ вершинах существует путь между первой и второй (т.е. фиксированными) вершинами.

Приведу набросок своего решения через производящие функции.

Пусть $D(n,k)$ - это число графов на $n$ помеченных вершинах с $k$ ребрами таких, что существует путь между первой и второй вершинами. Тогда искомая вероятность равна:

$$\beta_n(p)=\sum_{k=0}^{n(n-1)/2} D(n,k) p^{n(n-1)/2-k} q^k=p^{n(n-1)/2} \sum_{k=0}^{n(n-1)/2} D(n,k) \left(\frac{1-p}{p}\right)^k=$$

$$=(1-q)^{n(n-1)/2} \sum_{k=0}^{n(n-1)/2} D(n,k) \left(\frac{q}{1-q}\right)^k$$

где $p$ - как и прежде вероятность отсутсвия ребра, а $q$ - вероятность присутствия, $p+q=1.$

Производящая функция для $D(n,k)$ также выражается через производящую функцию (и ее экспоненту) для A062734:

$$\sum_{n,k} D(n+2,k) \frac{x^n}{n!} y^k = e^{F(x,y)-1} \frac{\partial^2 F(x,y)}{\partial x^2} = \frac{\partial^2 G(x,y)}{\partial x^2} - \frac{\left(\partial G(x,y)/\partial x\right)^2}{G(x,y)},$$

где

$$G(x,y) = e^{F(x,y)-1} = \sum_{n=0}^{\infty} \frac{(1+y)^{n(n-1)/2}x^n}{n!}.$$

При этом нетрудно видеть, что

$$\frac{\partial G(x,y)}{\partial x} = \sum_{n=1}^{\infty} \frac{(1+y)^{n(n-1)/2}x^{n-1}}{(n-1)!} =\sum_{n=0}^{\infty} \frac{(1+y)^{n(n+1)/2}x^n}{n!} = G(x(1+y),y)$$

и соответственно:

$$\frac{\partial^2 G(x,y)}{\partial x^2} = (1+y)\cdot G(x(1+y)^2,y).$$

Поэтому производящую функцию для $D(n,k)$ можно также записать в виде:

$$\sum_{n,k} D(n+2,k) \frac{x^n}{n!} y^k = (1+y)\cdot G(x(1+y)^2,y) - \frac{G(x(1+y),y)^2}{G(x,y)}.$$

Подставив $y=\frac{1-p}{p}$, получаем производящую функцию для $\beta(p)$:

$$\sum_{n} \beta_{n+2}(p) \frac{x^n}{p^{(n+1)(n+2)/2}n!} = \frac{G(x/p^2,(1-p)/p)}{p} - \frac{G(x/p,(1-p)/p)^2}{G(x,(1-p)/p)}.$$

При желании отсюда можно вывести и явную формулу для $D(n,k)$ и $\beta(p)$, но поля этого форума слишком малы, чтобы её вместить.

Напоследок немного численных экспериментов в PARI/GP. Сначала вычислим числа $D(n,k)$ для $n=2,3,\dots,10$:

? G(x, y) = sum(n=0,12,(1+y)^(n*(n-1)/2)*x^n/n!) + O(x^13);
? D=(1+y)*G(x*(1+y)^2,y) - G(x*(1+y),y)^2/G(x,y);
? for(n=2,10,print("n=",n,": ",Vecrev((n-2)!*polcoeff(D,n-2,x)))) 
n=2: [0, 1]
n=3: [0, 1, 3, 1]
n=4: [0, 1, 7, 18, 15, 6, 1]
n=5: [0, 1, 12, 63, 174, 240, 208, 120, 45, 10, 1]
n=6: [0, 1, 18, 151, 754, 2349, 4532, 6187, 6345, 4985, 3001, 1365, 455, 105, 15, 1]
n=7: [0, 1, 25, 300, 2255, 11525, 40754, 100780, 189285, 283460, 346611, 349976, 293020, 203280, 116250, 54262, 20349, 5985, 1330, 210, 21, 1]
n=8: [0, 1, 33, 531, 5490, 40215, 216335, 863175, 2597280, 6226055, 12351771, 20731599, 29817560, 37029795, 39882795, 37333453, 30381045, 21462210, 13120450, 6906480, 3108063, 1184038, 376740, 98280, 20475, 3276, 378, 28, 1]
n=9: [0, 1, 42, 868, 11690, 114051, 844522, 4834452, 21569448, 76329820, 222719252, 552136620, 1185497866, 2231663126, 3713209830, 5491411334, 7246282897, 8554268583, 9048806578, 8583664390, 7301652981, 5565534187, 3795543706, 2310593040, 1251636750, 600798744, 254186100, 94143224, 30260338, 8347680, 1947792, 376992, 58905, 7140, 630, 36, 1]
n=10: [0, 1, 52, 1338, 22624, 280735, 2695560, 20539764, 125570206, 620727923, 2522409392, 8672961962, 25842496190, 67837707693, 158639895240, 333071700680, 631409428415, 1085392293686, 1697397237158, 2420961972296, 3155147125949, 3762471289854, 4109104186228, 4112087853696, 3771150842689, 3168668895210, 2437853751270, 1715696202360, 1103008082763, 646609727594, 344863530000, 166870580976, 73006091235, 28760007465, 10150594650, 3190187214, 886163133, 215553195, 45379620, 8145060, 1221759, 148995, 14190, 990, 45, 1]

Аналогично вычислим коэффициенты $\beta(p)$:

? B=G(x/p^2,(1-p)/p)/p-G(x/p,(1-p)/p)^2/G(x,(1-p)/p);
? for(n=2,10,print("n=",n,": ",(n-2)!*p^((n-1)*n/2)*polcoeff(B,n-2,x))) 
n=2: -p + 1
n=3: p^3 - 2*p^2 + 1
n=4: -2*p^6 + 5*p^5 - 2*p^4 - 2*p^3 + 1
n=5: 6*p^10 - 18*p^9 + 12*p^8 + 7*p^7 - 6*p^6 - 2*p^4 + 1
n=6: -24*p^15 + 84*p^14 - 78*p^13 - 20*p^12 + 44*p^11 + 3*p^9 - 8*p^8 - 2*p^5 + 1
n=7: 120*p^21 - 480*p^20 + 570*p^19 - 340*p^17 + 80*p^16 + 70*p^14 - 20*p^12 + 11*p^11 - 10*p^10 - 2*p^6 + 1
n=8: -720*p^28 + 3240*p^27 - 4680*p^26 + 1050*p^25 + 2700*p^24 - 1380*p^23 - 110*p^22 - 420*p^21 + 150*p^20 + 190*p^19 - 72*p^18 + 102*p^17 - 20*p^16 - 30*p^15 + 13*p^13 - 12*p^12 - 2*p^7 + 1
n=9: 5040*p^36 - 25200*p^35 + 42840*p^34 - 18480*p^33 - 21840*p^32 + 19530*p^31 - 420*p^30 + 2030*p^29 - 2940*p^28 - 1680*p^27 + 1456*p^26 - 1050*p^25 + 462*p^24 + 322*p^23 - 98*p^21 + 70*p^20 - 42*p^18 + 15*p^15 - 14*p^14 - 2*p^8 + 1
n=10: -40320*p^45 + 221760*p^44 - 433440*p^43 + 272160*p^42 + 172200*p^41 - 263760*p^40 + 43680*p^39 + 36260*p^37 + 10640*p^36 - 24304*p^35 + 11424*p^34 - 6314*p^33 - 2464*p^32 + 1736*p^31 + 840*p^30 - 812*p^29 + 392*p^28 + 504*p^27 - 70*p^25 - 240*p^24 + 184*p^23 - 56*p^21 + 17*p^17 - 16*p^16 - 2*p^9 + 1

Ну и то же самое в терминах $q$:

? for(n=2,10,print("n=",n,": ",subst((n-2)!*p^((n-1)*n/2)*polcoeff(B,n-2,x),p,1-q))) 
n=2: q
n=3: -q^3 + q^2 + q
n=4: -2*q^6 + 7*q^5 - 7*q^4 + 2*q^2 + q
n=5: 6*q^10 - 42*q^9 + 120*q^8 - 175*q^7 + 127*q^6 - 27*q^5 - 15*q^4 + 3*q^3 + 3*q^2 + q
n=6: 24*q^15 - 276*q^14 + 1422*q^13 - 4310*q^12 + 8464*q^11 - 11132*q^10 + 9699*q^9 - 5195*q^8 + 1276*q^7 + 160*q^6 - 126*q^5 - 18*q^4 + 8*q^3 + 4*q^2 + q
n=7: -120*q^21 + 2040*q^20 - 16170*q^19 + 79230*q^18 - 268130*q^17 + 662910*q^16 - 1234120*q^15 + 1755230*q^14 - 1911020*q^13 + 1575190*q^12 - 953711*q^11 + 395681*q^10 - 92305*q^9 + 815*q^8 + 5130*q^7 - 370*q^6 - 290*q^5 - 10*q^4 + 15*q^3 + 5*q^2 + q
n=8: -720*q^28 + 16920*q^27 - 189360*q^26 + 1342110*q^25 - 6757050*q^24 + 25689180*q^23 - 76525250*q^22 + 182891480*q^21 - 356096160*q^20 + 570187510*q^19 - 754395832*q^18 + 825120654*q^17 - 743077262*q^16 + 545786030*q^15 - 321299790*q^14 + 146965873*q^13 - 49192405*q^12 + 10407516*q^11 - 638244*q^10 - 299055*q^9 + 57495*q^8 + 8860*q^7 - 2050*q^6 - 495*q^5 + 15*q^4 + 24*q^3 + 6*q^2 + q
n=9: 5040*q^36 - 156240*q^35 + 2336040*q^34 - 22429680*q^33 + 155348760*q^32 - 826485450*q^31 + 3511838610*q^30 - 12233705120*q^29 + 35586221860*q^28 - 87589854590*q^27 + 184179975406*q^26 - 333137967386*q^25 + 520735389412*q^24 - 705369559860*q^23 + 828819159168*q^22 - 844164553036*q^21 + 743329835766*q^20 - 563148007128*q^19 + 364260463798*q^18 - 198825736046*q^17 + 89954803288*q^16 - 32774738417*q^15 + 9132396253*q^14 - 1735030283*q^13 + 143448711*q^12 + 24110303*q^11 - 7216279*q^10 - 96285*q^9 + 204365*q^8 + 5075*q^7 - 5467*q^6 - 693*q^5 + 63*q^4 + 35*q^3 + 7*q^2 + q
n=10: 40320*q^45 - 1592640*q^44 + 30592800*q^43 - 380721600*q^42 + 3450282360*q^41 - 24265137960*q^40 + 137811421440*q^39 - 649424892480*q^38 + 2589199733260*q^37 - 8861175241100*q^36 + 26321650988584*q^35 - 68447362735976*q^34 + 156866153721438*q^33 - 318488516926062*q^32 + 575158670045848*q^31 - 926622972439136*q^30 + 1334566654900948*q^29 - 1720443520219844*q^28 + 1986098244607624*q^27 - 2052454714331952*q^26 + 1896481636947058*q^25 - 1563560636660290*q^24 + 1146555516696776*q^23 - 744464579528448*q^22 + 425385941669304*q^21 - 212097241724312*q^20 + 91194696015080*q^19 - 33240686472224*q^18 + 10005169644865*q^17 - 2377426654433*q^16 + 406161752032*q^15 - 36764788920*q^14 - 2361494184*q^13 + 1120601048*q^12 - 60235840*q^11 - 20066648*q^10 + 1793218*q^9 + 441070*q^8 - 19320*q^7 - 11088*q^6 - 812*q^5 + 140*q^4 + 48*q^3 + 8*q^2 + q

[rishelie]

Кстати, если инвертировать задачу и рассматривать не удаление ребер, а наоборот их случайное кидание в граф, то получится т.н. coalescent process. Этими делами одно время занимались американцы, по-моему, в связи с образованием звездных систем. Наверняка можно найти конкретные результаты о предельных распределениях количества компонент такого графа при $N\to\infty$

[maxal]

rishelie писал(а):

Кстати, если инвертировать задачу и рассматривать не удаление ребер, а наоборот их случайное кидание в граф, то получится т.н. coalescent process. Этими делами одно время занимались американцы, по-моему, в связи с образованием звездных систем. Наверняка можно найти конкретные результаты о предельных распределениях количества компонент такого графа при $N\to\infty$

Насколько я понял, у coalescent process и у рассматриваемой задачи есть существенное различие: количество вершин в coalescent process не является фиксированным, и граф может бесконечно "расти". А у нас граф конечен, количество вершин в нём фиксировано, и они являются помеченными.

[rishelie]

maxal писал(а):

rishelie писал(а):

Кстати, если инвертировать задачу и рассматривать не удаление ребер, а наоборот их случайное кидание в граф, то получится т.н. coalescent process. Этими делами одно время занимались американцы, по-моему, в связи с образованием звездных систем. Наверняка можно найти конкретные результаты о предельных распределениях количества компонент такого графа при $N\to\infty$

Насколько я понял, у coalescent process и у рассматриваемой задачи есть существенное различие: количество вершин в coalescent process не является фиксированным, и граф может бесконечно "расти". А у нас граф конечен, количество вершин в нём фиксировано, и они являются помеченными.

не совсем так. при каждом фиксированном N рассматривается результат "кидания" ребер на граф, т.е. по сути N(N-1)/2 независимых испытаний с вероятностью успеха p, где успех означает появление ребра на заданном месте. В результате для каждого N имеем случайный граф с N вершинами. переход к пределу осуществляется по N при рассмотрении различных числовых характеристик данного графа, например, распределения числа компонент связности. То есть точного ответа для конкретного N не будет, но будет его асимптотика, которая полезна при рассмотрении задач с очень большими N.

[maxal]

rishelie писал(а):

не совсем так.

Но вот в этой статье рассматривают бесконечные графы:
Percolation on Transitive Graphs as a Coalescent Process: Relentless Merging Followed by Simultaneous Uniqueness

rishelie писал(а):

при каждом фиксированном N рассматривается результат "кидания" ребер на граф, т.е. по сути N(N-1)/2 независимых испытаний с вероятностью успеха p, где успех означает появление ребра на заданном месте. В результате для каждого N имеем случайный граф с N вершинами.

Если так, то это то же самое, что и случайные графы, которые мы здесь рассматривали, только надо $p$ заменить на $q$ (у нас $p$ - вероятность отсутствия ребра, а $q=1-p$ - вероятность присутствия).

[rishelie]

maxal писал(а):

Но вот в этой статье рассматривают бесконечные графы:
Percolation on Transitive Graphs as a Coalescent Process: Relentless Merging Followed by Simultaneous Uniqueness

да, это не совсем то, что надо. я слово coalescent вспомнил в связи с coalescent forest, которыми занимается Jim Pitman.

Он же, кстати, ссылается на книжку B. Bollobas Random Graphs, где изучаются графы со случайными ребрами, см. там главу 2.

по поводу графов со случайными ребрами есть кое-что у В.Ф.Колчина в книге Случайные графы, см. там пункт 2.3

Вообще, пробежал глазами все эти ссылки и понял, что задачка ой какая непростая

[rishelie]

Есть следующие соображения. Рассмотрим такой вариант задачи: вершины графа занумерованы, компоненты связности - нет. Я думаю, именно это имеется ввиду в постановке задачи.

Допустим, что в результате удаления ребер с вероятностью $p$ (независимо друг от друга) образовалось $s$ не связанных друг с другом подграфов. Будем считать, что мы получили $j_1$ подграфов объема 1, $j_2$ подграфа объема $2$, и т.д., $j_n$ подграфов объема $n$. Ясно, что

$$ j_1+2j_2+\dots+nj_n=n,\quad j_r\geq 0, $$

кроме того, $j_1+\dots+j_n=s$.

Заметим, что получение $s$ несвязанных подграфов из полного графа получается удалением всех ребер, соединяющих вершины из разных подграфов. Таких ребер существует ровно

$$ A_{deleted}=\sum_{i<j}k_ik_j=\frac{n^2-k_1^2-\dots-k_s^2}{2}, $$

где $k_1,\dots,k_s$ - объемы наших $s$ подграфов в произвольном порядке. В $j$-обозначениях это будет выглядеть так:

$$ A_{deleted}=\frac{n^2-j_1-4j_2-\dots-n^2j_n}{2}. $$

Соответственно, вероятность удаления одного такого конкретного набора ребер равна $p^{A_{deleted}}$.

Осталось разобраться с количеством подграфов - сколько существует неупорядоченных разбиений множества вершин графа на подмножества: $j_1$ единичных, $j_2$ - с двумя вершинами, и т.д., $j_n$ с $n$ вершинами. Если рассматривать упорядоченные разбиения, то количество будет равно

$$ \frac{n!}{(1!)^{j_1}(2!)^{j_2}\dots(n!)^{j_n}}, $$

но, учитывая, что при таком разбиении порядок подмножеств с одинаковыми объемами учитывается, разделим на количества перестановок этих подмножеств, т.е. на $j_r!$, в итоге получим

$$ \frac{1}{(1!)^{j_1}(2!)^{j_2}\dots(n!)^{j_n}}\cdot\frac{n!}{j_1!\dots j_n!}. $$

Знакомая штука, не правда ли? Осталось все сложить вместе: вероятность того, что компонент связности будет не менее $s$, равна

$$ P_n(s)=p^{n^2/2}\sum_{j_1+2j_2+\dots+nj_n=n\atop j_1+\dots+j_n=s}\frac{n!}{j_1!\dots j_n!}\left(\frac{p^{-1/2}}{1!}\right)^{j_1}\cdots\left(\frac{p^{-n^2/2}}{n!}\right)^{j_n}= p^{n^2/2}B_{n,s}(p^{-1/2},p^{-2^2/2},\dots,p^{-n^2/2}), $$

где $B_{n,s}$ - известные полиномы Белла.

К примеру, $P_n(1)=1$ (вероятность, что компонент не менее 1), а $P_n(n)=p^{n(n-1)/2}$ (вероятность, что компонент будет $n$).

Добавлено спустя 52 минуты 54 секунды:

Кстати, вспоминая формулу Faa di Bruno, можно показать следующее.

Обозначим через $X_n$ случайную величину, равную количеству компонент связности в нашем случайном графе с числом вершин $n$. Легко проверить, что

$$ EX_n=\sum_{s=1}^nP\{X_n\geq s\}=\sum_{s=1}^n p^{n^2/2}B_{n,s}(p^{-1/2},\dots,p^{-n^2/2}).\quad\quad (1) $$

Теперь введем две функции:

$$ g(t)=\sum_{n=0}^\infty p^{-n^2/2}\frac{t^n}{n!}, $$

$$ f(t)=e^{g(t)-1}. $$

Легко видеть, что $g^{(n)}(0)=p^{-n^2/2}$, в частности, $g(0)=1$. А все производные $e^{t-1}$ в точке $t=1$ равны 1. Тогда по упомянутой формуле имеем:

$$ f^{(n)}(0)=\sum_{s=0}^n B_{n,s}(p^{-1/2},\dots,p^{-n^2/2}). $$

Поскольку $B_{n,0}()=0$ при $n>0$, можно вести суммирование от $s=1$, и по формуле (1) получим, что

$$ f^{(n)}(0)=p^{-n^2/2}EX_n. $$

Интересно, можно ли выписать $g(t)$ явно и тем самым попытаться найти асимптотику $EX_n$?

[maxal]

rishelie писал(а):

Обозначим через $X_n$ случайную величину, равную количеству компонент связности в нашем случайном графе с числом вершин $n$. Легко проверить, что

$$ EX_n=\sum_{s=1}^nP\{X_n\geq s\}=\sum_{s=1}^n p^{n^2/2}B_{n,s}(p^{-1/2},\dots,p^{-n^2/2}).\quad\quad (1) $$

Величина $EX_n$ в этой дискуссии ранее была обозначена $\alpha_n(p)$, то есть $EX_n = \alpha_n(p)$.
И, кстати, величина $\sum_{s=1}^n B_{n,s}(\cdots) = B_n(\cdots)$ - это так называемые полные полиномы Белла.

Но вынужден заметить, что ваша формула (1) неверна, в чем легко убедиться, подставив $p=1$. Тогда слева получается $\alpha_n(1)=n$, а справа $n$-е число Белла. Тем не менее, понятно, куда Вы клоните - см. ниже.

rishelie писал(а):

Теперь введем две функции:

$$ g(t)=\sum_{n=0}^\infty p^{-n^2/2}\frac{t^n}{n!}, $$

$$ f(t)=e^{g(t)-1}. $$

Легко видеть, что $g^{(n)}(0)=p^{-n^2/2}$, в частности, $g(0)=1$. А все производные $e^{t-1}$ в точке $t=1$ равны 1. Тогда по упомянутой формуле имеем:

$$ f^{(n)}(0)=\sum_{s=0}^n B_{n,s}(p^{-1/2},\dots,p^{-n^2/2}). $$

Поскольку $B_{n,0}()=0$ при $n>0$, можно вести суммирование от $s=1$, и по формуле (1) получим, что

$$ f^{(n)}(0)=p^{-n^2/2}EX_n. $$

Другими словами:

$$f(t) = \sum_{n=0}^{\infty} p^{-n^2/2} \alpha_n(p) \frac{t^n}{n!} = e^{g(t)-1} = \exp \sum_{n=1}^\infty p^{-n^2/2}\frac{t^n}{n!}$$

Но тогда, подставляя $t=x\sqrt{p}$, получаем:

$$\sum_{n=0}^{\infty} p^{-n(n-1)/2} \alpha_n(p) \frac{x^n}{n!} = \exp \sum_{n=1}^\infty p^{-n(n-1)/2}\frac{x^n}{n!}$$

что опять же противоречит формуле, полученной здесь.
А именно, правильная формула выглядит так:

$$\sum_{n=0}^{\infty} \alpha_n(p) \frac{x^n}{p^{n(n-1)/2} n!} = \sum_{n=0}^{\infty} \frac{x^n}{p^{n(n-1)/2} n!} \cdot \ln \sum_{n=0}^{\infty} \frac{x^n}{p^{n(n-1)/2} n!}$$

То есть, если исправить формулу (1), то из нее подобным образом, скорее всего, выведется вышеуказанная формула.

[rishelie]

это все было бы замечательно, если бы не было так грустно. проблема в том, что радиус сходимости ряда $\sum_{s=1}^\infty \frac{x^n}{p^{n(n-1)/2}n!}$ равен нулю.

[maxal]

rishelie писал(а):

это все было бы замечательно, если бы не было так грустно. проблема в том, что радиус сходимости ряда $\sum_{s=1}^\infty \frac{x^n}{p^{n(n-1)/2}n!}$ равен нулю.

А зачем вам сходимость? Формула выводится в формальных степенных рядах, без использования каких-либо аналитических свойст.

[rishelie]

согласен, намутил с вероятностями, сложил пересекающиеся события, в итоге вероятности стали больше 1. пойдем другим путем, ибо без вероятностей связности все-таки не обойтись

обозначим через $\alpha_i$ с.в., равную количеству компонент связности объема $i$, $i=\overline{1,n}$. и пусть $p_n=P\{\alpha_n=1\}$ - вероятность связности графа с $n$ вершинами. тогда, по всей видимости, будет верно раенство:

$$ P\{\alpha_1=j_1,\dots,\alpha_n=j_n\}=p^{n^2/2}\frac{n!}{j_1!\dots j_n!}\cdot\left(\frac{p_1p^{-1/2}}{1!}\right)^{j_1} \cdots \left(\frac{p_np^{-n^2/2}}{n!}\right)^{j_n}\quad\quad (2) $$

Иными словами берется количество разбиений множества вершин на заданное число подмножеств заданного объема, удаляются ребра между этими подмножествами с вероятностью $p^{A_{deleted}}$, а затем умножаем на вероятности связности заданных компонент, объемы которых известны.

Заметим, кстати, что $p_1=1$ и что все $p_n$ есть функции от $p$, $n>1$. Из (2) получим, что

$$ P\{X_n=s\}=P\{\alpha_1+\dots+\alpha_n=s\}=p^{n^2/2}\sum_{j_1+2j_2+\dots+nj_n=n\atop j_1+\dots+j_n=s} \frac{n!}{j_1!\dots j_n!}\cdot\left(\frac{p_1p^{-1/2}}{1!}\right)^{j_1} \cdots \left(\frac{p_np^{-n^2/2}}{n!}\right)^{j_n}=p^{n^2/2}B_{n,s}(p_1p^{-1/2},\dots,p_np^{-n^2/2}) $$

Отсюда

$$ EX_n=\sum_{s=1}^nsP\{X_n=s\}=p^{n^2/2}\sum_{s=1}^nsB_{n,s}(p_1p^{-1/2},\dots,p_np^{-n^2/2}) \quad\quad (3) $$

Заметим, что теперь при $p=1$ в силу того, что $p_n=0$ при $n>0$, получим

$$ EX_n=\sum_{s=1}^nsB_{n,s}(1,0,\dots,0)=n, $$

поскольку $B_{n,s}(1,0,\dots,0)=1$ при $n=s$, а в остальных случаях это ноль.
При $p=0$ получается, что $p^{(n^2-j_1-4j_2-\dots-n^2j_n)/2}=1$ при $j_n=1$ (ибо мы в комбинаторике считаем $0^0=1$ в таких сверточных формулах), а в остальных случаях это будет $0$. А также $p_n=1$ при $p=0$. Поэтому получим $P\{X_n=s\}=1$ для $s=1$ и ноль в противном случае. А это будет означать, что $EX_n=1$ при $p=0$.

Если теперь исправить функции $g(t)$ и $f(t)$ в виде

$$ g(t)=\sum_{n=0}^\infty \frac{p_nt^n}{p^{n^2/2}n!},\quad f(t)=(g(t)-1)e^{g(t)-1} $$

где $p_0=1$, то по формуле Фаа ди Бруно получим соотношение:

$$ f^{(n)}(0)=p^{-n^2/2}EX_n, $$

откуда

$$ f(t)=\sum_{n=1}^\infty\frac{EX_nt^n}{p^{n^2/2}n!}=\sum_{n=1}^\infty \frac{p_nt^n}{p^{n^2/2}n!} \exp\sum_{n=1}^\infty \frac{p_nt^n}{p^{n^2/2}n!}. $$

Далее, пользуясь подстановкой $t=x\sqrt p$, находим, что

$$ \sum_{n=1}^\infty\frac{EX_nx^n}{p^{n(n-1)/2}n!}=\sum_{n=1}^\infty \frac{p_nx^n}{p^{n(n-1)/2}n!} \exp\sum_{n=1}^\infty \frac{p_nx^n}{p^{n(n-1)2/2}n!}. $$

последнее, по найденным вами ранее соотношениям, должно быть равно

$$ \sum_{n=0}^\infty \frac{x^n}{p^{n(n-1)/2}n!} \ln\sum_{n=0}^\infty \frac{x^n}{p^{n(n-1)2/2}n!} $$

или, иначе говоря

$$ \sum_{n=1}^\infty \frac{p_nx^n}{p^{n(n-1)/2}n!} \exp\sum_{n=1}^\infty \frac{p_nx^n}{p^{n(n-1)2/2}n!}=\sum_{n=0}^\infty \frac{x^n}{p^{n(n-1)/2}n!} \ln\sum_{n=0}^\infty \frac{x^n}{p^{n(n-1)2/2}n!}. $$

Любопытное равенство, которое, кстати, легко выполняется при $p=1$

[rishelie]

Возвращаясь к старому сообщению, получим, заменяя $y=\frac{1-p}p$, что

$$ \sum_{n=0}^\infty\frac{x^n}{p^{n(n-1)/2}n!} \ln\sum_{n=0}^\infty\frac{x^n}{p^{n(n-1)/2}n!}= \left(F\left(x,\frac{1-p}p\right)-1\right) \exp\left(F\left(x,\frac{1-p}p\right)-1\right), $$

то есть, возвращаясь к моим баранам , получаем

$$ F\left(x,\frac{1-p}p\right)=\sum_{n=0}^\infty\frac{p_nx^n}{p^{n(n-1)/2}n!},\quad\quad (4) $$

при $n=0$ там как раз единичка получается. Но тогда, сравнивая коэффициенты при $x^n$, получаем тождество:

$$ p_n=p^{n(n-1)/2}\sum_{k=0}^\infty A062734(n,k)(q/p)^k, $$

где $q=1-p$. В общем-то, оно вполне соответствует определению треугольной последовательности.

Ну, и кроме того, из (4) и ранее приведенного соотношения для $F(x,y)$, переходя снова к $t$, получим выражение производящей функции для $p_n$:

$$ g(t)-1=\sum_{n=1}^\infty\frac{p_nt^n}{p^{n^2/2}n!}=\ln\sum_{n=0}^\infty\frac{t^n}{p^{n^2/2}n!}.\quad\quad(5) $$

И отсюда, кстати, все по той же формуле Фаа ди Бруно для производной сложной функции можно найти соотношение:

$$ p_n=p^{n^2/2}\sum_{k=1}^n(-1)^{k-1}(k-1)!B_{n,k}(p^{-1/2},\dots,p^{-n^2/2}). $$

[rishelie]

Теперь, аналогично тому, как мы искали производящую функцию $EX_n$, найдем п.ф. $P\{X_n=s\}$.

Рассмотрим функцию $f(t)=(g(t)-1)^s$. Опять же по формуле Фаа ди Бруно находим:

$$ f^{(n)}(0)=s!B_{n,s}(g'(0),\dots,g^{(n)}(0))=\frac{s!}{p^{n^2/2}}P\{X_n=s\}, $$

где я воспользовался равенством для $P\{X_n=s\}$ и определением $g(t)$. Тогда

$$ f(t)=\sum_{n=s}^\infty\frac{s!t^n}{p^{n^2/2}n!}P\{X_n=s\}. $$

С другой стороны, из (5) следует, что

$$ f(t)=\left(\ln\sum_{n=0}\frac{t^n}{p^{n^2/2}n!}\right)^s. $$

Теперь положим $h(x)=(\ln x)^s$ и все по той же формуле вернемся обратно к

$$ f^{(n)}(0)=\sum_{k=0}^nh^{(k)}(1)B_{n,k}(p^{-1/2},\dots,p^{-n^2/2}), $$

откуда

$$ P\{X_n=s\}=\frac{p^{n^2/2}}{s!}\sum_{k=0}^nh^{(k)}(1)B_{n,k}(p^{-1/2},\dots,p^{-n^2/2})= p^{n^2/2}\sum_{k=s}^nB_{n,k}(p^{-1/2},\dots,p^{-n^2/2})B_{k,s}(1,-1,\dots,(-1)^{k-1}(k-1)!). $$

[rishelie]

Интересно, но у меня получилось, что $p_n\to 1$. Сначала дифференцированием по $t$ формулы (5) (см. выше) и по формуле свертки последовательностей получаем путем нехитрых манипуляций рекурсивное соотношение

$$ p_n=1-\sum_{k=1}^{n-1}\binom{n-1}{k-1} p^{k(n-k)}p_k. \qquad (6) $$

Затем оцениваем сумму через сумму геометрической прогрессии с основанием $np^{n/2}$, что и означает стремление суммы к нулю, если вероятность $p$ исчезновения ребра меньше 1. Но тогда вероятность связности $p_n$ стремится к 1.

То есть число компонент связности сходится к 1 по вероятности.

Кстати, как частный случай при $p=q=1/2$ получится известный результат о том, что число связных графов порядка $n$ эквивалентно числу графов порядка $n$. См. Харари и Палмера "Перечисление графов".

Есть также рекурсия для вероятностей числа компонент:

$$ P\{X_n=s\}=\sum_{k=s-1}^{n-1}\binom{n-1}k P\{X_k=s-1\}p_{n-k}p^{k(n-k)}. \qquad (7) $$

Контрольный выстрел

$$ P\{X_n=n\}=P\{X_{n-1}=n-1\}p^{n-1}=\dots=p^{n(n-1)/2}. $$