Производящая функция

[quantum newbie]

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

Дан граф; вероятность того, что случайно выбранная точка имеет $k$ соседей (degree), равна $p_k$; вероятность, что случайно выбранное ребро ведёт к точке, которое имеет $k+1$ соседей, равна $q_k$. Последние связаны очевидным соотношением

$$q_k=\frac{(k+1)p_{k+1}}z,\;\;z=\sum_kkp_k.$$

Далее, введём производящие функции (generating functions)

$$G_0(x)=\sum_kp_kx^k,\;\;G_1(x)=\sum_kq_kx^k.$$

Они связаны соотношением $zG_1(x)=G_0'(x)$
Пусть $u$ — вероятность того, что случайно выбранное ребро ведёт к вершине, которая не принадлежит гигантской компоненте (giant component) графа.
Утверждается, что имеет место соотношение $u=G_1(u)$.
Кроме того, утверждается, что доля $S$, которую занимает гигантская компонента, связана с $u$ соотношением $S=1-G_0(u)$.

Прошу, объясните мне, откуда получены эти соотношения.

[quantum newbie]

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

Это понятие для меня новое. Всё, что я о нём знаю:
$G(x)=\sum\limits_kp_kx^k$, где $p_k$ — вероятность исследуемой с.в. $\xi$ принять значение $k$
$G(1)=1$
$G(0)=p_0$
$G'(1)=\mathbb{M}\xi$
$G'(x)=p_1$
$x^nG(x)$ соответствует $\xi+n$
$\left[G(x)\right]^n$ соответствует сумме $n$ равнораспределённых с.в.
$G(x)H(x)$ соответствует сумме с.в., соответствующих $G(x)$ и $H(x)$, если они независимые. Вообще, два предыдущих утверждения являются следствием этого.

Что ещё нужно знать, чтобы понимать описанные в первом посте рассуждения?

[ИСН]

О производящих функциях надо ещё знать, когда возникает необходимость их итерировать и чем это грозит. Например, Вы кидаете обычный кубик один раз, смотрите на него, а потом кидаете кубик столько раз, сколько выпало в первый, и всё складываете. Какое будет распределение у получившейся случайной величины?
О графах Вы чего-то не договариваете. Какая ещё вероятность, например, если у каждой точки ровно три соседа и они известны? Это если граф - куб. Ах, не куб? А не сказать ли хоть слово о том, что это за граф у Вас?

[TOTAL]

quantum newbie в сообщении #659421 писал(а):

вероятность, что случайно выбранное ребро ведёт к точке, которое имеет $k+1$ соседей, равна $q_k$.

Ребро ведет к скольки точкам?

[quantum newbie]

ИСН в сообщении #661125 писал(а):

Например, Вы кидаете обычный кубик один раз, смотрите на него, а потом кидаете кубик столько раз, сколько выпало в первый, и всё складываете. Какое будет распределение у получившейся случайной величины?

Попробую угадать ход мыслей.
Пусть реализовался вариант, когда первый кубик дал $m$. Тогда производящая функция суммы будет $\left[G(x)\right]^m$, где $6G(x)=x+x^2+x^3+x^4+x^5+x^6$.
Теперь попробуем учесть, что вероятность получить $m$ равна $p_m=\frac 16$. При $x^k$ будет стоять коэффециент, равный сумме по всем $m$ произведения $p_m$ на коэффициент при $x^k$ в $\left[G(x)\right]^m$. Таким образом, $G(x)=\sum\limits_m x^m\left(G(x)\right)^m=G(G(x))$.
Я восхищён.

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

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

2 TOTAL: опять же, автор не уделяет большое значение этому вопросу, слабо разделяя случаи ориентированного и неориентированного графа. Если граф ориентирован, думаю, такого вопроса не возникает, там одно ребро ведёт к одной вершине. Если граф неориентирован, то случайновыбранное ребро ведёт к двум вершинам, из которых мы случайно выбираем одну, как я понял. Такой граф ведёт себя как ориентированных граф, где каждое неориентированное ребро суть две противонаправленные дуги.

[quantum newbie]

Вот, кстати, ИСН полезную вещь сказал. Я хотел было ещё один вопрос дописать, всё из той же статьи, но немного раньше, чем приведённые рассуждения, которые я также не понимал. А сейчас понял, откуда примерно получается формула, но не до конца.

Суть такая: пусть $H(x)$ — производящая функция полного числа точек, достижимых от некоторого ребра. Я это понимаю так: мы выбираем, конечно случайно, ребро, достигаем его конца, далее идём во всевозможных направлениях и повторяем процедуру подсчёта вершин. В некотором смысле для неориентированного графа, это число вершин подграфа, максимально большого, связанного, содержащего выбранную вершину.
Утверждается, что $H(x)=xG_1(H(x))$.
Это объясняется так: если мы последуем ребру, мы найдём по крайней мере одну точку, о чём говорит ведущий коэффициент x, плюс несколько других кластеров вершин, размер каждого из которых выражается пр.ф. $H(x)$. Их количество распределено по закону $q_k$, поэтому появляется $G_1$.
Последний переход суть то самое итеративное свойство, как я понял, о котором говорил ИСН.
Единственное, что мне не понятно, так это то, как влияет условие независимости складываемых с.в. Размеры кластеров, вообще говоря, не является независимыми величинами. Так, если граф хоть как-то похож на 'small-world', две "почти соседние" вершины будут иметь много общих знакомых, хоть их процент от размера кластеров может быть мал. Кратко говоря, с.в. не являются независимыми, почему тогда можем применять формулу?
Может, это свойство конкретно рассматриваемой модели. Кстати, здесь рассматривается т.н. конфигурационная модель, т.е. ансамбль всевозможных графов с $n$ вершинами и долей $p_k$ вершин со степенью $k$ для каждого $k$. Последовательность $p_0,\ldots,p_n$ называется конфигурацией, она задана. Это определение я дал от себя, поэтому оно не является полностью правильным, работает только в приближении больших $n$.