Blog Archives

Chernoff Bound

Consider the sum of a sequence of independent random variables. One may expect its distribution is concentrated around its expected value. This is characterized by the Chernoff bound, which gives exponentially decreasing bounds on tail distributions of the sum. Let

Tagged with:
Posted in Probability

Store compressed data in database using PHP

When storing big text contents in a database, it is better to store after compressing the data. The following is an example storing HTML contents in a database cache. We first create a table mapping URLs to HTML contents. The

Tagged with: , ,
Posted in PHP, SQL

Format numbers with leading and trailing zeros in PHP

PHP provides str_pad() to add a string to a certain length with another string. Another way is to use sprintf() with formatting patterns. Pad leading zeros to get exactly 3 digits:

Posted in PHP

Sperner Theorem on Maximal Antichains

Let \(S\) be a family of subsets of \(\{1,\ldots,n\}\) such that no set in \(S\) contains another. This is often called an antichain. Theorem. [Sperner's Theorem] \[ |S| \leq {n \choose \lfloor n/2 \rfloor}. \] The proof of Sperner’s Theorem

Tagged with: , ,
Posted in Theory