2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2, 3  След.
 
 О выборе распределения случайных графов
Сообщение23.10.2006, 11:23 


23/10/06
22
Москва
Доброе время суток всем!

Подскажите пути решения следующей задачи, привожу оригинальную формулировку:
Дан неориентированный граф с 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).

 Профиль  
                  
 
 
Сообщение24.10.2006, 09:11 


23/10/06
22
Москва
Получилось найти выражение для вероятности существования пути между двумя произвольными элементами. При больших 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.
Неплохо было бы с её учетом получить, например, наиболее вероятный размер подграфа.

 Профиль  
                  
 
 
Сообщение16.11.2006, 12:20 
Заблокирован
Аватара пользователя


07/08/06

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

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

 Профиль  
                  
 
 
Сообщение16.11.2006, 12:58 
Модератор
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение22.11.2006, 16:15 


23/10/06
22
Москва
AlexDem писал(а):
M214, удалось ли Вам подступиться к решению? Интересная задачка, но как ее решать - идеи так и не возникло... :oops:

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

 Профиль  
                  
 
 
Сообщение22.11.2006, 16:18 
Заблокирован
Аватара пользователя


07/08/06

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

 Профиль  
                  
 
 
Сообщение22.11.2006, 17:09 


23/10/06
22
Москва
В общем и целом, когда я осознал, что найти гениально простой путь к ответам на поставленные вопросы не получается, я стал вытягивать из этой системы все, что удавалось. (Под системой я понимаю разваливающийся граф.)
Я стал изучать повередие математических ожиданий различных параметров этой системы как функций 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}\]). Тем не менее эти многочлены как-будто к чему-то приближаются (в некотором смысле) и, скорее всего, есть какая-нибудь рекуррентная формула для их получения.

 Профиль  
                  
 
 
Сообщение22.11.2006, 17:36 
Заблокирован
Аватара пользователя


07/08/06

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

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

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

 Профиль  
                  
 
 
Сообщение22.11.2006, 18:08 


23/10/06
22
Москва
C - это просто биномиальный коэффициент.

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

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

 Профиль  
                  
 
 
Сообщение22.11.2006, 21:05 
Модератор
Аватара пользователя


11/01/06
5660
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 ?

 Профиль  
                  
 
 
Сообщение22.11.2006, 22:36 


23/10/06
22
Москва
все просто \[\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]

 Профиль  
                  
 
 
Сообщение23.11.2006, 05:56 
Модератор
Аватара пользователя


11/01/06
5660
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.$$

 Профиль  
                  
 
 
Сообщение23.11.2006, 12:37 


23/10/06
22
Москва
Это, несомненно, очень полезный для меня комментарий. Спасибо!

До настоящего момента я считал коэффициенты \[\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)$.

 Профиль  
                  
 
 
Сообщение23.11.2006, 19:12 
Модератор
Аватара пользователя


11/01/06
5660
Из производящей функции для $\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}.$$
Вроде нигде не напутал :lol:

 Профиль  
                  
 
 
Сообщение28.11.2006, 04:19 
Модератор
Аватара пользователя


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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 35 ]  На страницу 1, 2, 3  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group