Random Walk on Integers

Unbiased Random Walks (source:Wikipedia) — Unbiased Random Walks

Imagine that a particle is walking in a two-dimensional space, starting at the origin $(0, 0)$ . At every time-step (or “epoch”) $n = 0, 1, 2, 3, \cdots$ it takes a $\pm 1$ vertical step. At every step, the particle either moves up by $+1$ , or down by $-1$ . This walk is “unbiased” in the sense that the up/down steps are equiprobable.

In this post, we will discuss some natural questions about this “unbiased” or “simple” random walk. For example, how long will it take for the particle to return to zero? What is the probability that it will ever reach +1? When will it touch $a$ for the first time? Contents of this post are a summary of the Chapter “Random Walks” from the awesome “Introduction to Probability” (Volume I) by William Feller. Also, this is an excellent reference.

Edit: the Biased Case. The biased walk follows

$\displaystyle p:=\Pr[ \text{down}]\, ,\qquad q:=\Pr[ \text{up} ]\, ,\qquad p + q = 1$ .

The lazy walk follows

$\displaystyle p:=\Pr[ \text{down}]\, ,\qquad q:=\Pr[ \text{up} ]\, , \qquad \Pr[stay] = r\, ,\qquad p + q = 1$ .

In the exposition, we’ll first state the unbiased case and when appropriate, follow it up with the biased case.

Continue reading “Random Walk on Integers” →

Forkable Strings are Rare

In a blockchain protocol such as Bitcoin, the users see the world as a sequence of states. A simple yet functional view of this world, for the purpose of analysis, is a Boolean string $w = w_1, w_2, \cdots$ of zeros and ones, where each bit is independently biased towards $1$ favoring the “bad guys.”

A bad guy is activated when $w_t = 1$ for some $t$ . He may try to present the good guys with a conflicting view of the world, such as presenting multiple candidate blockchains of equal length. This view is called a “fork”. A string $w$ that allows the bad guy to fork (with nonnegligible probability) is called a “forkable string”. Naturally, we would like to show that forkable strings are rare: that the manipulative power of the bad guys over the good guys is negligible.

Claim ([1], Bound 2). Suppose $w =w_1, \cdots, w_n$ is a Boolean string, with every bit independently set to $1$ with probability $(1-\epsilon)/2$ for some $\epsilon < 1$ . The probability that $w$ is forkable is at most $\exp(-\epsilon^3n/2)$ .

In this post, we present a commentary on the proof that forkable strings are rare. I like the proof because it uses simple facts about random walks, generating functions, and stochastic domination to bound an apparently difficult random process.

Continue reading “Forkable Strings are Rare” →

Some Facts about the Gambler’s Ruin Problem

Consider a random walk in the two-dimensional discrete space, where the horizontal direction is indexed by nonnegative time steps and the vertical direction is indexed by integers.

randwalk — A random walk starting at z, with absorbing barriers at zero and a. It goes up/down with probability p and q, respectively.

The particle is at its initial position $z > 0$ at time $0$ . At every time step, it independently takes a step up or down: up with probability $p$ and down with probability $q = 1-p$ . If $p = q$ the walk is called symmetric. Let $a$ be constant, $a > z$ . If the walk reaches either $a$ or $0$ , it stops. Define the two quantities below.