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

[M214]

Доброе время суток всем!

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

Вопросы:
1. Какое распределение имеет количество подграфов при фиксированном p. Обозначим это распределение f[p,N](m). m - количество подграфов.
2. Найти вероятность образования k подграфов в зависимости от p. Обозначим эту вероятность t[k,N](p).

Для наводки был проведен численный эксперимент на системе из 100 элементов, по 1 млн. розыгрышей для каждого значения p от 0 до 1 с шагом 0.001. Эмпирические выводы такие: распределение количества подграфов при фиксированном p явно нормальное. Зависимость вероятности образования k подграфов от p`=1-p по форме напоминает x^4exp(-x).

[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.
Неплохо было бы с её учетом получить, например, наиболее вероятный размер подграфа.

[AlexDem]

M214, удалось ли Вам подступиться к решению? Интересная задачка, но как ее решать - идеи так и не возникло...

Вернее, была одна - расположить все вершины по окружности, для простоты я полагал, что в каждый момент времени выкидывается одно ребро, и нужно было решить, через какое время граф "развалится", но что-то до решения я так и не довел.

[maxal]

См. вот эту статью: http://math.ucsd.edu/~fan/wp/conn.pdf

[M214]

AlexDem писал(а):

M214, удалось ли Вам подступиться к решению? Интересная задачка, но как ее решать - идеи так и не возникло...

Да идеи появились и открылось несколько удивительных (для меня) соотношений, правда есть еще очень много нерешенных вопросов. Удалось найти вид и способ построения некоторых характеристических функций этой системы. Если интересно - могу поделиться.

[AlexDem]

Да, очень интересно.

[M214]

В общем и целом, когда я осознал, что найти гениально простой путь к ответам на поставленные вопросы не получается, я стал вытягивать из этой системы все, что удавалось. (Под системой я понимаю разваливающийся граф.)
Я стал изучать повередие математических ожиданий различных параметров этой системы как функций p. Меня заинтересовало математическое ожидание числа сегментов, на которые развалится граф при удалении каждого ребера с вероятностью p. Очевидно, что эта функция - полином вида:

\[\alpha \left( p \right) = \sum\limits_{k = 0}^m {K\left( {m,k} \right)p^{m - k} \left( {1 - p} \right)^k }\]

Где

\[{K\left( {m,k} \right)}\]

- число всевозможных сегментов при всевозможных распадах графа при удалении ровно

\[\left( m-k \right)\]

ребер, m - число ребер.
Намек на то, как считается

\[{K\left( {m,k} \right)}\]

я нашел в книге Эндрюса по теории разбиений и еще в некоторых трудах по комбинаторике. Оказалось, что

\[\alpha \left( p \right)\]

это многочлен, коэффициенты которого ведут себя весьма своеобразно. Вот один из фактов, которые удалось доказать:

\[\alpha \left( p \right) = 1 + np^{n - 1} + ? + ( - 1)^n \left( {n - 2} \right)!p^m\]

Здесь "?" это другие члены полинома со степенями между n и m, природа коэффициентов при которых мне пока не ясна. Для доказательства этого факта пришлось вывести удивительное тождество, следствия которого сейчас меня занимают почти столь же как и сама задача:

\[\left\| {C_i^j } \right\|^{ - 1} = \left\| {\left( { - 1} \right)^{i + j} C_i^j } \right\|\]

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

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

Сейчас я практически уверен, что ответ нужно искать в асимптотической теории разбиений, где существенно потрудились Харди, Рамануджан и потом Радемахер.

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

\[ \begin{array}{l} \alpha _2 \left( p \right) = 1 + p \\ \alpha _3 \left( p \right) = 1 + 3p^2 - p^3 \\ \alpha _4 \left( p \right) = 1 + 4p^3 + 3p^4 - 6p^5 + 2p^6 \\ \alpha _5 \left( p \right) = 1 + 5p^4 + 10p^6 - 10p^7 - 15p^8 + 20p^9 - 6p^{10} \\ \ldots \\ \end{array} \]

При больших n считать коэффициенты очень сложно, да и счет конкретных средних значений - тоже малоприятное занятие (при n=100 старший член имеет вид

\[98!p^{4950}\]

). Тем не менее эти многочлены как-будто к чему-то приближаются (в некотором смысле) и, скорее всего, есть какая-нибудь рекуррентная формула для их получения.

[AlexDem]

M214 писал(а):

Для доказательства этого факта пришлось вывести удивительное тождество

Что-то мне не очень понятна запись тождества, что такое C? Объясните, пожалуйста

Чтобы не плодить лишних сообщений, поправлю свой же пост: если C - коэффициент, то что тогда означает ||C||? А, я так и подумал про матрицу, но она вроде не квадратная получается, судя по приведенным многочленам для a(p). Хотя, если бесконечная - то понятно. Спасибо

[M214]

C - это просто биномиальный коэффициент.

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

Имеется ввиду бесконечная матрица, элементами которой являются биномиальные коэффициенты. Оказывается, что обратная к ней матрица имеет ту же самую стркутуру с точностью до знаков, расставленных в шахматном порядке.

[maxal]

M214 писал(а):

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

\[\left\| {C_i^j } \right\|^{ - 1} = \left\| {\left( { - 1} \right)^{i + j} C_i^j } \right\|\]

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

Подобного рода тождества являются прямыми следствиями т.н. "взаимно обратных соотношений".
См. книгу Дж.Риордан "Комбинаторные тождества".

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

M214 писал(а):

Я стал изучать повередие математических ожиданий различных параметров этой системы как функций p. Меня заинтересовало математическое ожидание числа сегментов, на которые развалится граф при удалении каждого ребера с вероятностью p. Очевидно, что эта функция - полином вида:

\[\alpha \left( p \right) = \sum\limits_{k = 0}^m {K\left( {m,k} \right)p^{m - k} \left( {1 - p} \right)^k }\]

Где

\[{K\left( {m,k} \right)}\]

- число всевозможных сегментов при всевозможных распадах графа при удалении ровно

\[\left( m-k \right)\]

ребер, m - число ребер.

Наверняка, $K(m,k)$ - это какие-то известные числа. Приведите их значения, скажем, для $m=1,\dots,5$ - попробуем распознать.

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

M214 писал(а):

Оказалось, что

\[\alpha \left( p \right)\]

это многочлен, коэффициенты которого ведут себя весьма своеобразно. Вот один из фактов, которые удалось доказать:

\[\alpha \left( p \right) = 1 + np^{n - 1} + ? + ( - 1)^n \left( {n - 2} \right)!p^m\]

Здесь "?" это другие члены полинома со степенями между n и m, природа коэффициентов при которых мне пока не ясна.
...

\[ \begin{array}{l} \alpha _2 \left( p \right) = 1 + p \\ \alpha _3 \left( p \right) = 1 + 3p^2 - p^3 \\ \alpha _4 \left( p \right) = 1 + 4p^3 + 3p^4 - 6p^5 + 2p^6 \\ \alpha _5 \left( p \right) = 1 + 5p^4 + 10p^6 - 10p^7 - 15p^8 + 20p^9 - 6p^{10} \\ \ldots \\ \end{array} \]

Непонятны обозначения. Если $a_k(p)$ - это многочлен $\alpha(p)$ при $m=k,$ то почему степень $\alpha_4(p)$ равна 6 ?

[M214]

все просто

\[\alpha _n \left( p \right)\]

- это многочлен степени

\[m = \frac{1}{2}n\left( {n - 1} \right)\]

.

K(2,i) = { 2, 1 }
K(3,i) = { 3, 6, 3, 1 }
K(4,i) = { 4, 18, 30, 24, 15, 6, 1 }
K(5,i) = { 5, 40, 135, 250, 295, 282, 215, 120, 45, 10, 1 }
K(6,i) = { 6, 75, 420, 1385, 3015, 4800, 6365, 7170, 6705, 5065, 3009, 1365, 455, 105, 15, 1 }
K(7,i) = { 7, 126, 1050, 5355, 18690, 47880, 96796, 166890, 251370, 329945, 373947, 362292, 297115, 204225, 116385, 54271, 20349, 5985, 1330, 210, 21, 1 }

Здесь i меняется от 0 до

\[\frac{1}{2}n\left( {n - 1} \right)\]

.

Занятно, что одна из головоломных последовательностей http://www.research.att.com/~njas/sequences/A001187 связана с этой задачей, правда в данный момент у меня нет времени, чтобы описать как именно - дополню позже.[/url]

[maxal]

M214 писал(а):

K(2,i) = { 2, 1 }
K(3,i) = { 3, 6, 3, 1 }
K(4,i) = { 4, 18, 30, 24, 15, 6, 1 }
K(5,i) = { 5, 40, 135, 250, 295, 282, 215, 120, 45, 10, 1 }
K(6,i) = { 6, 75, 420, 1385, 3015, 4800, 6365, 7170, 6705, 5065, 3009, 1365, 455, 105, 15, 1 }
K(7,i) = { 7, 126, 1050, 5355, 18690, 47880, 96796, 166890, 251370, 329945, 373947, 362292, 297115, 204225, 116385, 54271, 20349, 5985, 1330, 210, 21, 1 }

Здесь i меняется от 0 до

\[\frac{1}{2}n\left( {n - 1} \right)\]

.

Тогда, видимо, везде выше имелись в виду $K(n,k),$ а не $K(m,k).$

M214 писал(а):

Занятно, что одна из головоломных последовательностей A001187 связана с этой задачей, правда в данный момент у меня нет времени, чтобы описать как именно - дополню позже.

Скорее уж тогда наблюдается связь с треугольной последовательностью A062734, для которой A001187 является суммой элементов в строках. А еще точнее с ее производящей функцией:

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

Производящая функция для $K(n,k)$ выражается через $F(x,y)$ так:

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

В PARI/GP можно повычислять так:

? \ps 46 
   seriesprecision = 46 significant terms
? G(x, y) = sum(n=0,10,(1+y)^(n*(n-1)/2)*x^n/n!) 
? KK=G(x,y)*log(G(x,y)) 
? for(n=1,10,print("n=",n,": ",Vecrev(n!*polcoeff(KK,n,x)))) 
n=1: [1]
n=2: [2, 1]
n=3: [3, 6, 3, 1]
n=4: [4, 18, 30, 24, 15, 6, 1]
n=5: [5, 40, 135, 250, 295, 282, 215, 120, 45, 10, 1]
n=6: [6, 75, 420, 1385, 3015, 4800, 6365, 7170, 6705, 5065, 3009, 1365, 455, 105, 15, 1]
n=7: [7, 126, 1050, 5355, 18690, 47880, 96796, 166890, 251370, 329945, 373947, 362292, 297115, 204225, 116385, 54271, 20349, 5985, 1330, 210, 21, 1]
n=8: [8, 196, 2268, 16436, 83510, 316932, 943936, 2325036, 4980192, 9477860, 16101568, 24384612, 32812178, 39082876, 41049780, 37876692, 30584575, 21522060, 13133750, 6908580, 3108273, 1184048, 376740, 98280, 20475, 3276, 378, 28, 1]
n=9: [9, 288, 4410, 42924, 297675, 1565172, 6509076, 22222080, 64745514, 166666920, 385872228, 809076744, 1539570522, 2659016808, 4164916680, 5909134776, 7583634135, 8791498296, 9193458834, 8659706580, 7335852615, 5578559676, 3799687896, 2311674120, 1251861975, 600834780, 254190258, 94143532, 30260349, 8347680, 1947792, 376992, 58905, 7140, 630, 36, 1]
n=10: [10, 405, 7920, 99450, 899640, 6239709, 34540380, 157406760, 607957920, 2049467615, 6183624960, 16943351670, 42465035760, 97696733085, 206693778420, 402472822908, 721461066660, 1190447422245, 1807616325760, 2524932326070, 3243261563262, 3829474875885, 4154731650360, 4139840215980, 3786176949870, 3175879804461, 2440904193000, 1716825944750, 1103371208550, 646709899815, 344886903504, 166875104880, 73006798095, 28760093145, 10150602210, 3190187646, 886163145, 215553195, 45379620, 8145060, 1221759, 148995, 14190, 990, 45, 1]

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

Заметим, что

$$\alpha_n(p)= p^{n(n-1)/2} \sum_{k=0}^{n(n-1)/2} K(n,k) \left(\frac{1-p}{p}\right)^k.$$

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

$$\sum_{n,k} K(n,k) \frac{x^n}{n!} \left(\frac{1-p}{p}\right)^k = \sum_{n=0}^{\infty} \frac{x^n}{p^{n(n-1)/2} n!}\cdot \ln \sum_{t=0}^{\infty} \frac{x^t}{p^{t(t-1)/2} t!}.$$

Получаем производящую функцию для $\alpha_n(p):$

$$\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_{t=0}^{\infty} \frac{x^t}{p^{t(t-1)/2} t!}$$

или

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

[M214]

Это, несомненно, очень полезный для меня комментарий. Спасибо!

До настоящего момента я считал коэффициенты

\[\alpha _n \left( p \right)\]

не через производящую функцию, а по формуле

$b_i = \sum\limits_{k = 0}^i {K\left( {n,n - i + k} \right)\left( { - 1} \right)^k C_{n - i + k}^k } $

Как мне кажется, это несколько проще.

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

P.S. Прошу прощения за путаницу с коэффициентами $K\left( {n,k} \right)$.

[maxal]

Из производящей функции для $\alpha_n(p)$ следует явная формула:

$$\alpha_n(p) = n!\cdot p^{n(n-1)/2}\cdot \sum_{s + t_1 + 2t_2 + \dots + n t_n = n\atop s, t_1, \dots, t_n \geq 0,\ t_1+\dots+t_n\geq 1} {t_1 + \dots + t_n\choose t_1\ \dots\ t_n} \frac{(-1)^{1+t_1+\dots+t_n}}{(t_1 + \dots + t_n)\cdot p^{s(s-1)/2}\cdot s!} \prod_{j=1}^n \left(\frac{1}{p^{j(j-1)/2}\cdot j!}\right)^{t_j}.$$

Вроде нигде не напутал

[maxal]

Я добавил в OEIS три последовательности A125205-A125207, связанные числами K(n,k), и планирую добавить еще три аналогичных для коэффициентов многочленов $\alpha_n(p).$

M214, если хотите, ваше имя/email тоже может быть включено в список авторов этих последовательностей. Для этого сообщите мне его в английской транскипции в PM вместе с email'ом или без него :)