2

The $G (n, p)$ model, due to Erdös and Rényi, has two parameters, $n$ and $p$. Here $n$ is the number of vertices of the graph and $p$ is the edge probability. For each pair of distinct vertices, $v$ and $w, > p$ is the probability that the edge $(v,w)$ is present. The presence of each edge is statistically independent of all other edges. The graph-valued random variable with these parameters is denoted by $G(n,p)$. When we refer to “the graph $G(n,p)$”, we mean one realization of the random variable

Random graphs are random variables?

I thought that $G(n,p)$ is a random variable with $\Omega\rightarrow \mathbb{R}$, where $\Omega$ is $\mathcal{P}\{1,...,n\}^2,\mathcal{P}\{\mathcal{P}\{1,...,n\}^2\},1/|\mathcal{P}\{1,...,n\}^2|$ and $G(n,p)(\omega)= |\omega|^p|\{1,...,n\}^2|-|\omega|^{1-p}$. But if that would be the case I don t know how I can formally verify that the event that an edge is present is stochastically independed that an oher edge is present. I have chosen the model to look at all possible sets of edges ie all graphs possible, the author of this paper (J.Spencer) mentioned a graph-valued random variable hence I thought I have to find a probabiliypace where an elemen represents a graph.

If someone could tell me how I can verify the stochastic independence of the existence of two edges and how the random graphs are modeled as random variables I would really appreciate it

GNUSupporter 8964民主女神 地下教會
  • 17,627
New2Math
  • 1,265

1 Answers1

5

Random graphs are a random variable, but not a real-valued random variable: a graph-valued one. $G(n,p)$ is a function from the sample space $\Omega$ to the set of all $2^{\binom n2}$ graphs on a fixed vertex set $\{v_1, v_2, \dots, v_n\}$.

So what's the sample space, then? We could be lazy and just take $\Omega$ to be the same set of graphs, so that $G(n,p)$ is the identity function. Generally, we try not to be too specific about what $\Omega$ is, though, because we might want other sources of randomness involved. We are happy as long as the distribution of $G(n,p)$ is correct: as long as $$\Pr[G(n,p) = G] = p^{|E(G)|} (1-p)^{\binom n2 - |E(G)|}.$$

We might also want to think of the graph evolution process, in which case $\Omega = [0,1]^{\binom n2}$. For each outcome $\omega \in \Omega$, $G(n,p)(\omega)$ includes the $i^{\text{th}}$ edge (order the edges however you like) if $\omega_i < p$. Here, we can define multiple graph valued random variables $G(n,p)$ and $G(n,p')$ in the same probability space.

Misha Lavrov
  • 142,276
  • what is the sample space here? – New2Math Jan 14 '21 at 17:16
  • edited to mention the sample space as well – Misha Lavrov Jan 14 '21 at 17:17
  • If $\Omega$ would be the same set of graphs and G(n,p) would be the identity function ie. $G(n,p)(\omega)=\omega$ where does $p$ come into play? – New2Math Jan 14 '21 at 17:21
  • 1
    A probability space is a triple $(\Omega, \mathcal F, P)$. In the "take $\Omega$ to be the same set of graphs" case, we assign $P(\omega) = p^{|E(\omega)|} (1-p)^{\binom n2 - |E(\omega)|}$. – Misha Lavrov Jan 14 '21 at 17:23
  • why do we say that a random graph is a random variable and not an element of $\Omega$ and how can I show that the edges are satisitcally independent? – New2Math Jan 14 '21 at 17:27
  • If we say that a random graph is an outcome of the probability space, then we've "hardcoded in" the probability space; we can't change it in any way. The point of random variables is to abstract away "implementation details": any process by which we obtain a graph at random can have the $G(n,p)$ distribution if it gets the same results with the same probabilities. – Misha Lavrov Jan 14 '21 at 17:31
  • Statistical independence of edges depends on how you've defined the probability space. In the graph evolution example, it's particularly easy, because $\omega_i$ and $\omega_j$ are independent for $i \ne j$. – Misha Lavrov Jan 14 '21 at 17:33
  • Last question why are $\omega_i$ and $\omega_j$ are independent for $i\neq j$. ?An event has to be a subset of the probability space $(\Omega, \mathcal F, P)$ what would be the subset in this case for the event $A$ that an edge existst and for the event $B$ that an other edge exists. And how could we show that $Pr(A\cap B)= Pr(A)Pr(B)$ ? – New2Math Jan 14 '21 at 17:42
  • In that case the distribution on $\Omega$ is uniform, and probability is just $\binom n2$-dimensional volume, so you check that ${\omega \in [0,1]^{\binom n2} : \omega_i < p}$ and ${\omega \in [0,1]^{\binom n2} : \omega_j < p}$ are sets of volume $p$ whose intersection has volume $p^2$. – Misha Lavrov Jan 14 '21 at 17:47