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

In summary, the events $A_1, . . . , A_{n \choose 2}$ are independent because the edges in $G(n, 1/2)$ appear independently with probability $\frac{1}{2}$.
  • #1
joypav
151
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
  • #2
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.
 

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

What is a random graph?

A random graph is a mathematical structure that consists of a set of vertices or nodes, and a set of edges that connect these vertices randomly. It is a model that is used to study complex systems, such as social networks, biological networks, and computer networks.

How are edges chosen in a random graph?

In a random graph, edges are chosen randomly between the vertices. This means that there is no predetermined pattern or rule for how the edges are selected. Each edge has an equal probability of being chosen, and the resulting graph is a random representation of the underlying system.

What is the importance of choosing edges in a random graph?

The choice of edges in a random graph is crucial because it determines the structure and properties of the graph. By selecting edges randomly, we can study the behavior of complex systems and make predictions about their behavior in real-life scenarios.

Can we control the number of edges in a random graph?

Yes, we can control the number of edges in a random graph by adjusting the probability of choosing an edge between two vertices. For example, if we want a graph with a higher density of edges, we can increase the probability of choosing an edge, and vice versa.

How are random graphs used in scientific research?

Random graphs are used in various scientific fields, including computer science, sociology, biology, and physics. They are used to model and study complex systems, understand their properties, and make predictions about their behavior. Random graphs also serve as a benchmark for comparing and evaluating other network models and algorithms.

Similar threads

Replies
1
Views
2K
Replies
3
Views
2K
Replies
6
Views
2K
Replies
1
Views
1K
Replies
1
Views
1K
Replies
7
Views
2K
Back
Top