The Binomial Distribution

x <- rbinom(1000, size = 30, prob = .8)
hist(x)

barplot(dbinom(0:30, 30, .8))

Random Graphs

Suppose we have a graph with \(n\) nodes and non-directed edges that form with probability \(p\).

library(igraph)
set.seed(404)
n <- 45
p <- .05
m <- matrix(sample(c(0, 1), size = n^2, replace = TRUE, prob = c(1 - p, p)), ncol = n)
g <- graph_from_adjacency_matrix(m)
g <- simplify(g, remove.multiple = F, remove.loops = T) 
plot(g, edge.arrow.size = .4, vertex.size = 9, vertex.label = NA)

Graph Density

Let \(X\) be the number of edges in a random graph of \(n\) vertices. There are \({n \choose 2}\) possible edges (trials), each forming independently with the same probability \(p\). Thus,

\[ X \sim \textrm{Binom}(n = {n \choose 2}, p = p) \]

Let’s simulate many random graphs and note the number of edges of each.

# replicate
simlist <- rep(NA, 1e5)

for(i in 1:1e5) {
  # simulate
  m <- matrix(sample(c(0, 1), size = n^2, replace = TRUE, prob = c(1 - p, p)), ncol = n)
  m[lower.tri(m, diag = TRUE)] <- 0 # make undirected and remove loops
  # store
  simlist[i] <- sum(m)
}

hist(simlist, xlim = c(15, 75))

barplot(dbinom(1:choose(n, 2), choose(n, 2), prob = p))

Stirling’s Approximation

f1 <- function(n) {
  factorial(n)
}

f2 <- function(n) {
  n^n * exp(-n) * sqrt(2 * pi * n)
}

df <- data.frame(n = rep(1:30, 2),
                 f = log(c(f1(1:30), f2(1:30))),
                 func = as.factor(rep(c("factorial", "Stirlings"), each = 30))
                 )
library(ggplot2)
ggplot(df, aes(x = n, y = f)) +
  geom_line(aes(color = func))