Random Graphs are Complicated

Want to get notified about new posts? Join the mailing list and follow on X/Twitter.

Random graphs are super interesting, and it’s amazing how quickly things become intractably complex!

On Math Academy, a student is essentially a stochastic process on an irregular knowledge graph, and when calculating expected XP remaining, we actually have to brute-force simulate the student working through the knowledge graph. Would be nice to have a fast, elegant analytical solution but it’s just too complicated.

Even the simplest toy problems are incredibly hard. For instance, to my knowledge, there’s not even a full analytical solution for the expected diameter of an Erdos-Renyi graph (n nodes each connected with edge probability p).

Want to get notified about new posts? Join the mailing list and follow on X/Twitter.