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.