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
SUMMARY

The events $A_1, \ldots, A_{n \choose 2}$ in a random graph $G$ from the model $G(n, 1/2)$ are independent. Each edge $e_i$ has a probability of $\frac{1}{2}$ of being included in the graph, and the independence of these events follows directly from the definition of the random graph model $G(n, p)$. Specifically, the occurrence of any edge does not influence the occurrence of another edge, confirming that the joint probability of a subset of events equals the product of their individual probabilities.

PREREQUISITES
  • Understanding of random graph theory, specifically the Erdős–Rényi model $G(n, p)$
  • Basic probability concepts, including independence of events
  • Familiarity with combinatorial notation, such as ${n \choose 2}$
  • Knowledge of edge probability in random graphs
NEXT STEPS
  • Study the properties of random graphs, focusing on the Erdős–Rényi model $G(n, p)$
  • Learn about the implications of event independence in probability theory
  • Explore combinatorial proofs related to random graphs
  • Investigate applications of random graphs in network theory and computer science
USEFUL FOR

Mathematicians, computer scientists, and researchers in graph theory or probability who are interested in the properties and behaviors of random graphs, particularly those studying independence in probabilistic models.

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.
 
If there are an infinite number of natural numbers, and an infinite number of fractions in between any two natural numbers, and an infinite number of fractions in between any two of those fractions, and an infinite number of fractions in between any two of those fractions, and an infinite number of fractions in between any two of those fractions, and... then that must mean that there are not only infinite infinities, but an infinite number of those infinities. and an infinite number of those...

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