Grado medio di grafo random
Questo è il calcolo del grado medio del modello di grafo casuale di Erdos-Renyi (da dispense fornite da prof.)
\(\displaystyle \bar{k} = \sum_{k=0}^{n-1} k p_{k} = \sum_{k=1}^{n-1} k \binom{n-1}{k} p^{k} (1-p)^{n-1-k}
\\= \sum_{k=1}^{n-1} (n-1) \binom{n-2}{k-1} p^{k} (1-p)^{n-1-k}
\\=(n-1)p \sum_{k=0}^{n-2} \binom{n-2}{k} p^{k} (1-p)^{n-2-k}
\\= p(n-1)\)
(p è la prob. che ci sia un arco tra una coppia di nodi)
Pur riconoscendo che è banale, c'è un dettaglio che non mi quadra.
Spiego quel che ho capito riga per riga:
#1 sostituisco \(\displaystyle p \) con la prob. che un nodo abbia grado k
#2 dal coefficiente binomiale 'estraggo' un \(\displaystyle (n-1) \)
#3 porto fuori dalla sommatoria \(\displaystyle (n-1) \) e decremento l'estremo della sommatoria a \(\displaystyle n-2 \)
questo passaggio non mi è chiaro: decrementando l'indice della sommatoria dovrei portare fuori qualcosa come:
\(\displaystyle \binom{n-2}{n-2} p^{n-2} (1-p)^{n-2-n-2} = p^{n-2} \)
giusto? Invece mi trovo solo un \(\displaystyle p \)
Confermate il ragionamento dei passaggi precedenti? E nel #3 dove sbaglio? Notate poi che anche il \(\displaystyle k \) della sommatoria che cambia da 0 a 1 e poi ancora a 0
Poi, se possibile, avrei un dubbio ancora più banale (ma i forum esistono anche per questo giusto?
) al #3 la sommatoria si annulla per il binomio di Newton, ma perché non avrei potuto annullarla al primo passaggio? Il risultato finale poi sarebbe stato \(\displaystyle n-1 \) che in effetti ha poco senso.
(Essendo dispense può essere che ci sia qualche errore..)
Un riferimento utile
http://www.cs.cornell.edu/courses/cs485 ... cture1.pdf
\(\displaystyle \bar{k} = \sum_{k=0}^{n-1} k p_{k} = \sum_{k=1}^{n-1} k \binom{n-1}{k} p^{k} (1-p)^{n-1-k}
\\= \sum_{k=1}^{n-1} (n-1) \binom{n-2}{k-1} p^{k} (1-p)^{n-1-k}
\\=(n-1)p \sum_{k=0}^{n-2} \binom{n-2}{k} p^{k} (1-p)^{n-2-k}
\\= p(n-1)\)
(p è la prob. che ci sia un arco tra una coppia di nodi)
Pur riconoscendo che è banale, c'è un dettaglio che non mi quadra.
Spiego quel che ho capito riga per riga:
#1 sostituisco \(\displaystyle p \) con la prob. che un nodo abbia grado k
#2 dal coefficiente binomiale 'estraggo' un \(\displaystyle (n-1) \)
#3 porto fuori dalla sommatoria \(\displaystyle (n-1) \) e decremento l'estremo della sommatoria a \(\displaystyle n-2 \)
questo passaggio non mi è chiaro: decrementando l'indice della sommatoria dovrei portare fuori qualcosa come:
\(\displaystyle \binom{n-2}{n-2} p^{n-2} (1-p)^{n-2-n-2} = p^{n-2} \)
giusto? Invece mi trovo solo un \(\displaystyle p \)
Confermate il ragionamento dei passaggi precedenti? E nel #3 dove sbaglio? Notate poi che anche il \(\displaystyle k \) della sommatoria che cambia da 0 a 1 e poi ancora a 0
Poi, se possibile, avrei un dubbio ancora più banale (ma i forum esistono anche per questo giusto?
) al #3 la sommatoria si annulla per il binomio di Newton, ma perché non avrei potuto annullarla al primo passaggio? Il risultato finale poi sarebbe stato \(\displaystyle n-1 \) che in effetti ha poco senso.(Essendo dispense può essere che ci sia qualche errore..)
Un riferimento utile
http://www.cs.cornell.edu/courses/cs485 ... cture1.pdf
Risposte
E' semplicemente la dimostrazione della media di una variabile binomiale. I passaggi postati mi sembrano tutti corretti e puoi controllarne l'esattezza su qualunque testo di Statistica.
Il punti principali che non comprendi sono questi:
1)
$k ((n-1),(k))=(k (n-1)!)/(k!(n-1-k)!)=(n-1)((n-2)!)/((k-1)!(n-1-k)!)=(n-1)((n-2),(k-1))$
2)
"tira fuori" $(n-1)$ perché non dipende dalla sommatoria e un $p$ in modo da trovarsi con una somma $=1$ per il binomio di Newton. Ecco i passaggi di dettaglio non inseriti nelle dispense perché lasciati al lettore come esercizio:
$(n-1)sum_(k=1)^(n-1)((n-2),(k-1))p^k q^(n-1-k)$
poni $k-1=h rarr k=h+1$ e ottieni
$(n-1)sum_(h=0)^(n-2)((n-2),(h))p^(h+1) q^(n-1-h-1)$
ora puoi "tirar fuori" anche un "p" (che non dipende più da $h$) ottenendo ciò che ti serve:
$(n-1)p sum_(h=0)^(n-2)((n-2),(h))p^(h) q^(n-2-h)=(n-1)p[p+(1-p)]^(n-2)=(n-1)p$
tutto qui.
Per essere precisi non è che la somma si annulla ma è uguale a uno, essendo $[p+(1-p)]^m=1^m=1$
...e ciò non vale nel primo passaggio perché ogni elemento della somma è moltiplicato per $k$...
Il punti principali che non comprendi sono questi:
1)
$k ((n-1),(k))=(k (n-1)!)/(k!(n-1-k)!)=(n-1)((n-2)!)/((k-1)!(n-1-k)!)=(n-1)((n-2),(k-1))$
2)
"tira fuori" $(n-1)$ perché non dipende dalla sommatoria e un $p$ in modo da trovarsi con una somma $=1$ per il binomio di Newton. Ecco i passaggi di dettaglio non inseriti nelle dispense perché lasciati al lettore come esercizio:
$(n-1)sum_(k=1)^(n-1)((n-2),(k-1))p^k q^(n-1-k)$
poni $k-1=h rarr k=h+1$ e ottieni
$(n-1)sum_(h=0)^(n-2)((n-2),(h))p^(h+1) q^(n-1-h-1)$
ora puoi "tirar fuori" anche un "p" (che non dipende più da $h$) ottenendo ciò che ti serve:
$(n-1)p sum_(h=0)^(n-2)((n-2),(h))p^(h) q^(n-2-h)=(n-1)p[p+(1-p)]^(n-2)=(n-1)p$
tutto qui.
"alfredopacino":
al #3 la sommatoria si annulla per il binomio di Newton, ma perché non avrei potuto annullarla al primo passaggio?
Per essere precisi non è che la somma si annulla ma è uguale a uno, essendo $[p+(1-p)]^m=1^m=1$
...e ciò non vale nel primo passaggio perché ogni elemento della somma è moltiplicato per $k$...
Grazie mille, è tutto più chiaro.
Sopravvivono giusto un paio di piccoli dubbi ancora:
- però nel mio primo passaggio (la prima riga della dimostrazione) la sommatoria passa dal partire da k=0 a k=1 "impunemente"?
- riguardo la domanda sul binomio di newton, sempre al primo passaggio avrei potuto portare \(\displaystyle k \) fuori dalla sommatoria che sarebbe diventato \(\displaystyle \frac{(n-1)(n-2)}{2} \) quindi:
\(\displaystyle \bar{k} = \sum_{k=0}^{n-1} k p_{k} = \sum_{k=1}^{n-1} k \binom{n-1}{k} p^{k} (1-p)^{n-1-k}
\\= \frac{(n-1)(n-2)}{2} \sum_{k=1}^{n-1} \binom{n-1}{k} p^{k} (1-p)^{n-1-k}
\\= \frac{(n-1)(n-2)}{2} \)
Il \(\displaystyle k \) fuori è un passaggio che non posso fare?
Sopravvivono giusto un paio di piccoli dubbi ancora:
- però nel mio primo passaggio (la prima riga della dimostrazione) la sommatoria passa dal partire da k=0 a k=1 "impunemente"?
- riguardo la domanda sul binomio di newton, sempre al primo passaggio avrei potuto portare \(\displaystyle k \) fuori dalla sommatoria che sarebbe diventato \(\displaystyle \frac{(n-1)(n-2)}{2} \) quindi:
\(\displaystyle \bar{k} = \sum_{k=0}^{n-1} k p_{k} = \sum_{k=1}^{n-1} k \binom{n-1}{k} p^{k} (1-p)^{n-1-k}
\\= \frac{(n-1)(n-2)}{2} \sum_{k=1}^{n-1} \binom{n-1}{k} p^{k} (1-p)^{n-1-k}
\\= \frac{(n-1)(n-2)}{2} \)
Il \(\displaystyle k \) fuori è un passaggio che non posso fare?
domanda 1)
no, non impunemente: se ci pensi un attimo, ha semplicemente escluso dalla somma l'addendo con $k=0$, ovvero $0*((n-1),(0))*p^0*q^(n-1)=0$
domanda 2)
no, non puoi portar fuori k perché k è l'indice della sommatoria.....e quindi k varia....puoi portar fuori solo "cose" che non dipendono dall'indice della somma
EDIT: ho capito ora cosa vorresti fare
[size=200]
Ps: quando ti vengono queste idee malsane la prima cosa da fare è provare a sviluppare alcuni addendi della somma.....così ti rendi conto di cosa puoi o non puoi fare algebricamente.....
In questo caso la somma estesa è:
$1*((n-1),(1))*p*q^(n-2)+2*((n-1),(2))*p^2*q^(n-3)+...+(n-1)*((n-1),(n-1))*p^(n-1)*q^0$
e tu stai cercando di raccogliere $[1+2+...+(n-1)]$ tra l'altro anche calcolando male la somma perché il risultato sarebbe $n/2 (n-1)$
spero di essermi spiegato bene.....ma sicuramente quando riguarderai le cose che hai scritto te ne accorgerai da solo di cosa avresti voluto fare....
no, non impunemente: se ci pensi un attimo, ha semplicemente escluso dalla somma l'addendo con $k=0$, ovvero $0*((n-1),(0))*p^0*q^(n-1)=0$
domanda 2)
no, non puoi portar fuori k perché k è l'indice della sommatoria.....e quindi k varia....puoi portar fuori solo "cose" che non dipendono dall'indice della somma
EDIT: ho capito ora cosa vorresti fare
[size=200]
non si può!
[/size]Ps: quando ti vengono queste idee malsane la prima cosa da fare è provare a sviluppare alcuni addendi della somma.....così ti rendi conto di cosa puoi o non puoi fare algebricamente.....
In questo caso la somma estesa è:
$1*((n-1),(1))*p*q^(n-2)+2*((n-1),(2))*p^2*q^(n-3)+...+(n-1)*((n-1),(n-1))*p^(n-1)*q^0$
e tu stai cercando di raccogliere $[1+2+...+(n-1)]$ tra l'altro anche calcolando male la somma perché il risultato sarebbe $n/2 (n-1)$
spero di essermi spiegato bene.....ma sicuramente quando riguarderai le cose che hai scritto te ne accorgerai da solo di cosa avresti voluto fare....
bello, ho fatto un errore nell'errore 
grazie mille, si vede che pure volendo non è la temperatura adatta per studiare
grazie mille, si vede che pure volendo non è la temperatura adatta per studiare
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo