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
Click For 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.
 
There is a nice little variation of the problem. The host says, after you have chosen the door, that you can change your guess, but to sweeten the deal, he says you can choose the two other doors, if you wish. This proposition is a no brainer, however before you are quick enough to accept it, the host opens one of the two doors and it is empty. In this version you really want to change your pick, but at the same time ask yourself is the host impartial and does that change anything. The host...

Similar threads

  • · Replies 1 ·
Replies
1
Views
2K
Replies
1
Views
2K
Replies
1
Views
2K
  • · Replies 6 ·
Replies
6
Views
3K
  • · Replies 3 ·
Replies
3
Views
2K
  • · Replies 6 ·
Replies
6
Views
3K
  • · Replies 1 ·
Replies
1
Views
2K
  • · Replies 1 ·
Replies
1
Views
2K
  • · Replies 8 ·
Replies
8
Views
2K
  • · Replies 6 ·
Replies
6
Views
3K