Calcolo combinatorio
Ciao a tutti, è il primo topic che scrivo (sono un pò emozionato 
). Avrei un problema da sottoporre alla vostra attenzione, che vi spiego subito. Studiando i grafi casuali di Erdos e Renyi mi sono imbattuto in una formula per il calcolo asintotico della distribuzione del grado di questa tipologia di grafi, che risulta essere una distribuzione di Poisson. Ebbene il problema è che non riesco a derivare questo risultato. Vi riporto di seguito la dimostrazione data dai due matematici ungheresi in un loro lavoro chiamato "On Random Graphs".
Per coloro che non sapessero cosa è un grafo casuale di Erdos-Renyi: esso è un grafo $G_(n,N)$ avente n nodi ed N archi scelti casualmente in modo che $G_(n,N)$ non abbia né archi paralleli né cappi. Erdos e Renyi dimostrano che la distribuzione del grado di un generico nodo del grafo G così ottenuto è una distribuzione di Poisson.
TEOREMA: Sia $D_(n,N)(P_k)$ il grado del vertice $P_k$ in $G_(n,N)$. Per $N(n)~~cn$ si ha per ogni $k$:
$lim_{n\to\ infty}P(D_(n,N)(P_k)=j)=((2c)^je^(-2c))/(j!)$
DIMOSTRAZIONE: La probabilità che un dato vertice $P_k$ sia connesso ad esattamente altri $r$ vertici di $G_(n,N)$ è:
$(C(n-1,r)*C(C(n-1,2),N-r))/(C(C(n,2),N))~~(((2N)/n)^re^(-(2N)/n))/(r!)$ (*)
Quindi se $N(n)~~cn$ si ha una distribuzione di Poisson con parametro $\lambda\=2c$
Il passaggio che non capisco è quello con l'asterisco (*). L'unica formula che viene menzionata nel testo è la seguente approssimazione del coefficiente binomiale:
$C(n,k)~~(n^k)/(k!)*e^(-(k^2)/(2n)-(k^3)/(6n^2))$
Ringrazio anticipatamente chiunque riesca ad aiutarmi a risolvere questo problema, ciao e buonanotte!
). Avrei un problema da sottoporre alla vostra attenzione, che vi spiego subito. Studiando i grafi casuali di Erdos e Renyi mi sono imbattuto in una formula per il calcolo asintotico della distribuzione del grado di questa tipologia di grafi, che risulta essere una distribuzione di Poisson. Ebbene il problema è che non riesco a derivare questo risultato. Vi riporto di seguito la dimostrazione data dai due matematici ungheresi in un loro lavoro chiamato "On Random Graphs".Per coloro che non sapessero cosa è un grafo casuale di Erdos-Renyi: esso è un grafo $G_(n,N)$ avente n nodi ed N archi scelti casualmente in modo che $G_(n,N)$ non abbia né archi paralleli né cappi. Erdos e Renyi dimostrano che la distribuzione del grado di un generico nodo del grafo G così ottenuto è una distribuzione di Poisson.
TEOREMA: Sia $D_(n,N)(P_k)$ il grado del vertice $P_k$ in $G_(n,N)$. Per $N(n)~~cn$ si ha per ogni $k$:
$lim_{n\to\ infty}P(D_(n,N)(P_k)=j)=((2c)^je^(-2c))/(j!)$
DIMOSTRAZIONE: La probabilità che un dato vertice $P_k$ sia connesso ad esattamente altri $r$ vertici di $G_(n,N)$ è:
$(C(n-1,r)*C(C(n-1,2),N-r))/(C(C(n,2),N))~~(((2N)/n)^re^(-(2N)/n))/(r!)$ (*)
Quindi se $N(n)~~cn$ si ha una distribuzione di Poisson con parametro $\lambda\=2c$
Il passaggio che non capisco è quello con l'asterisco (*). L'unica formula che viene menzionata nel testo è la seguente approssimazione del coefficiente binomiale:
$C(n,k)~~(n^k)/(k!)*e^(-(k^2)/(2n)-(k^3)/(6n^2))$
Ringrazio anticipatamente chiunque riesca ad aiutarmi a risolvere questo problema, ciao e buonanotte!
Risposte
$C(n,2)$ rappresenta il numero totale (massimo di archi dato che il grafo è semplice) che puoi avere su $n$ nodi, e quindi $C(C(n,2),N)$ è il numero di sottoinsiemi di archi di cardinailità $N$.
$C(C(n-1,2),N-r)$ ha l'equivalente significato di quello di prima: si prende $N-r$ (nota $N=N-r+r$) dato che sugli $N$ archi a disposizione ne devi scegliere $N-r$ che non insistano sul nodo scelto da cui si considerano $n-1$ nodi.
$C(n-1,r)$ rappresenta la cardinalità del gruppo di automorfismo associato dato che il grafo non considera i nodi etichettati.
Il rapporto delle quantità, nel giusto ordine, darà la probabilità cercata.
Se vuoi delle ottime lecture notes sui grafi aleatori: http://www.win.tue.nl/~rhofstad/NotesRGCN2010.pdf
$C(C(n-1,2),N-r)$ ha l'equivalente significato di quello di prima: si prende $N-r$ (nota $N=N-r+r$) dato che sugli $N$ archi a disposizione ne devi scegliere $N-r$ che non insistano sul nodo scelto da cui si considerano $n-1$ nodi.
$C(n-1,r)$ rappresenta la cardinalità del gruppo di automorfismo associato dato che il grafo non considera i nodi etichettati.
Il rapporto delle quantità, nel giusto ordine, darà la probabilità cercata.
Se vuoi delle ottime lecture notes sui grafi aleatori: http://www.win.tue.nl/~rhofstad/NotesRGCN2010.pdf
ciao andrea, ti ringrazio moltissimo per il tuo intervento chiarificatore. Ora la formula mi risulta più chiara, ma continuo a non riuscire ad ottenere la probabilità cercata. Ho tentato in vari modi applicando la formula di approssimazione per il calcolo del binomiale, ma non capisco proprio da dove spunti fuori quel $(2N)/n$ come parametro della distribuzione di Poisson. Spero di poter continuare questa discussione con te o con altri amici del forum, un saluto, e a presto
up!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo