MHB Are Events in Random Graphs from G(n, 1/2) Independent?

  • Thread starter Thread starter joypav
  • Start date Start date
  • Tags Tags
    Graph Random
AI Thread Summary
In the discussion about the independence of events in random graphs from G(n, 1/2), it is established that each edge in the graph has a probability of 1/2 of being included. The events A_i, representing the presence of edges, are independent because the occurrence of one edge does not affect the occurrence of another. This independence follows directly from the definition of the random graph model G(n, p), where edges appear independently. The proof is straightforward, as the probability of any subset of events occurring is the product of their individual probabilities. Thus, the independence of events A_1 through A_{n choose 2} is a fundamental characteristic of the model.
joypav
Messages
149
Reaction score
0
Let $n$ be a positive integer, and let $G$ be a random graph from $G(n, 1/2)$. Let $e_1, . . . , e_{n \choose 2}$ be the
possible edges on the vertex set ${1, . . . , n}$, and for each $i$, let $A_i$ be the event that $e_i ∈ E(G)$.
Prove that the events $A_1, . . . , A_{n \choose 2}$ are independent.Can I just have some help understanding what details I should be including here?
It's so trivial that I don't know how to write it down as a proof.
There is a probability of $\frac{1}{2}$ that any arbitrary possible edge will be an edge of the graph. And it just seems obvious that whether one edge is in the graph has nothing at all to do with if another edge is in the graph.

So then if we choose an arbitrary subset of $A_1, . . . , A_{n \choose 2}$, the probability of the events in the subset occurring will be the product of the individual probabilities of the events.
 
Physics news on Phys.org
joypav said:
Let $n$ be a positive integer, and let $G$ be a random graph from $G(n, 1/2)$. Let $e_1, . . . , e_{n \choose 2}$ be the
possible edges on the vertex set ${1, . . . , n}$, and for each $i$, let $A_i$ be the event that $e_i ∈ E(G)$.
Prove that the events $A_1, . . . , A_{n \choose 2}$ are independent.Can I just have some help understanding what details I should be including here?
It's so trivial that I don't know how to write it down as a proof.
There is a probability of $\frac{1}{2}$ that any arbitrary possible edge will be an edge of the graph. And it just seems obvious that whether one edge is in the graph has nothing at all to do with if another edge is in the graph.

So then if we choose an arbitrary subset of $A_1, . . . , A_{n \choose 2}$, the probability of the events in the subset occurring will be the product of the individual probabilities of the events.

In $G(n, p)$, the edges appear independently with probability $p$ (by definition of $G(n, p)$). So the question indeed is asking to prove something that is immediate from the definition.
 
Back
Top