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?

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). \]

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\).

Notes from June 2015 containing the following: Phase kick-back, Deutsch's algorithm, Fourier sampling, Deutsch-Jozsa algorithm, Bernstein-Vazirani algorithm, Preimage of a function, Simon's algorithm, Grover's algorithm, Amplitude amplification, Quantum Fourier Transform, and Shor's algorithm.

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}, \]

then

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

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

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

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

Are different versions of the 3SUM problem equivalent?

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

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

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

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