Posts Tagged ‘CS’
This seems counter-intuitive, at least to me, but if you can find an intuitive explanation for it, please comment!
Fact: Let G be a cycle (connected graph where every vertex has degree 2: you know what I mean) of length n (i.e., n vertices and n edges). Start a random walk on G from any node u. Then the probability that v is the last node visited (i.e., the random walk hits all other nodes before hitting v) is the same for every v other than u!
[Such a property is obviously true for the complete graph, and apparently it’s true only for cycles and complete graphs.]
I do not know a probabilist’s proof; what I could think of is a distinctly ComputerSciencey (Dynamic Programming / recurrence relation) proof.
Apart from The Worm-Runner’s Digest which was the source of the above, there was Manifold (and a book), source of excellent stuff such as this, there is the Journal of Irreproducible Results, its rival Annals of Improbable Research (which awards the Ig Nobel Prizes), and (found through Wikipedia) Null Hypothesis. Sigh, there is competition in every market.