Showing posts tagged essays

Information Theory

I have just uploaded the beginnings of an essay on information theory to my website. You can see the essay (in its currently incomplete state) here. Information theory was first described by Claude Shannon in his groundbreaking 1948 paper, A Mathematical Theory of Communication. What is particularly surprising about Shannon’s truly remarkable paper is its completeness. Not only does Shannon suggest a mathematical model for (digital) communication and information, but he produces a huge array of fundamental results for his model. It is exceptionally rare that such a complete…

Keep reading

Estimating the Second Frequency Moment

\(\) I just uploaded an updated version of an essay, Estimating the Second Frequency Moment. The frequency moment problem was addressed in the seminal paper of Alon, Matias and Szegedy. In my essay, I give a couple of results from that paper and give indications of how the results can be generalized. Suppose you are shown a stream of numbers \(s_1, s_2, \ldots, s_n\) where each \(s_j \in {1,2, \ldots, m}\) for \(j = 1, 2, \ldots, n\). If \(f_i\) denotes the number of times \(i…

Keep reading