The Drunkard's Pilgrimage
The Drunkard's Walk Wed, Oct 17, 2018 02:00 CEST

A drunkard is zigzagging home. At every steps forward (or backward) he is making, he also moves \(1\) step to the left with probability \(p\) and \(1\) step to the right otherwise. He starts \(i\) steps to the right of a river. What is the expected number of steps forward before he falls into the river?

Sums of geometric series Sun, Jul 23, 2017 02:00 CEST

Among the identities that are useful in the analysis of algorithms, this one shows how sums of geometric series converge when the ratio is smaller than one (in absolute value). It occurs in divide an conquer schemes. For example, it allows to show that hierarchical cuttings for \(n\) hyperplanes in \(d\) dimensions only need space proportional to \(n^d\).

\[ \sum_{i=0}^{\infty} \binom{i+j}{j} x^i = \frac{1}{ {(1-x)}^{j+1} }, \forall j \in \mathbb{N}, \forall x \in (-1,1). \]

Ulam's Spiral
Infinite Number of Primes Sat, Jul 22, 2017 02:00 CEST

The erroneous proof I hear most often is: Suppose \(P\) is a finite set that contains all the primes, then \(p^* = 1 + \prod_{p \in P} p\) is prime. Indeed, the flaw is that \(p^*\) is not necessarily prime but rather must be a multiple of some prime not in \(P\).

Recurrences Sat, Apr 22, 2017 02:00 CEST


Let \( a \in \mathbb{N} \), \( t < a \in \mathbb{N} \), and \( b \in \mathbb{R}\). Defining \( A_t \) to be some real number and

\[ A_N = (1 - \frac{a}{N}) A_{N-1} + b, N > t \in \mathbb{N}, \]


\[ A_N = \frac{b}{1+a} (N+1), N \ge a \in \mathbb{N}. \]

Converging series Fri, Apr 21, 2017 02:00 CEST

Let \(-1 < x < 1\),

\[ 1 + x + x^2 + x^3 + x^4 + \cdots = \frac{1}{1-x}. \]

Polynomial-time approximation schemes Wed, May 4, 2016 02:00 CEST


\((1\pm\varepsilon)\)-approximation with complexity \(O(n^{f(\varepsilon)})\).

Equivalence of 3SUM problems Wed, Apr 27, 2016 02:00 CEST

Are different versions of the 3SUM problem equivalent?

Log Log Log Thu, Apr 14, 2016 02:00 CEST


\[ \frac{\log n}{\log \log n}! = \Theta(n) \]

VC-dimension Tue, Apr 12, 2016 02:00 CEST

Definitions of VC-dimesion and \(\varepsilon\)-nets.