A non-intuitive(?) fact

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.

Advertisement

Simplexity of songs

Knuth’s paper The Complexity of Songs
Paper by Broder and Stolfi, Pessimal Algorithms and Simplexity Analysis.

More generally, there is a paper A Stress Analysis of a Strapless Evening Gown which led to an apparently good book of the same name.

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.

Writing for Computer Science

There is a book with that title. Other good related resources are the links here, and (more general) here. Also, maybe at this course home page.

The “Singleton” in “Singleton bound”

Is a person. Might seem hard to believe, though.
Searching for [R C Singleton “Singleton bound”] throws some references.
Probably Maximum distance q-nary codes is the paper.