Our Paper on Realizing a Graph on Random Points

A minimum spanning tree. (image source)


Our paper, titled How to Realize a Graph on Random Points, has gone up in the Arxiv. I’ll write more about it in future posts.


Continue reading “Our Paper on Realizing a Graph on Random Points”


Notes On Unbiased Random Walks

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 $altex -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 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.

Continue reading “Notes On Unbiased Random Walks”

Characterizing the Adversarial Grinding Power in a Proof-of-Stake Blockchain Protocol

[Contents of this post are based on an ongoing discussion with Alex Russell and Aggelos Kiayias. It contains potentially unpublished material.]

In a proof-of-stake blockchain protocol such as Ouroboros, at most half of the users are dishonest. While an honest user always extends the longest available blockchain, the dishonest users try to fool him into extending a manipulated blockchain. Here, the user who is allowed to issue a block at any time-slot is called the “slot leader.” As it happens, a number of future slot leaders are computed in advance using the random values present in the blocks. Although counterintuitive, such a scheme ensures that if the adversary does not control more than half the users now, it is very unlikely that he cannot control more than half the slot leaders. The time-slots are divided into “epochs” of length R.

Continue reading “Characterizing the Adversarial Grinding Power in a Proof-of-Stake Blockchain Protocol”

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”

Upper Bounds on Binomial Coefficients using Stirling’s Approximation

We need to bound the binomial coefficients a lot of times. In this post, we will prove bounds on the coefficients of the form {n \choose k}, {n \choose \alpha n} and {(1-\alpha)n \choose \alpha n} where \alpha \in (0, 1/2] and \alpha n is an integer.

Proposition 1. For positive integers n, k such that 1 \leq k \leq n,

\displaystyle {n \choose k} \leq \left( \frac{n e}{k} \right)^k.

Proposition 2. For a positive integer n and any \alpha such that \alpha n \in \mathbb{N} and \displaystyle \frac{1}{n} \leq \alpha \leq \frac{1}{2},

\displaystyle {n \choose \alpha n} \leq 2^{n H(\alpha)}

where the binary entropy function H : [0, 1] \rightarrow [0, 1] is defined as follows:

\displaystyle H(\alpha) := \left\{ \begin{array}{ll}0\,, & \text{ if } \alpha \in \{0, 1\}\\ -\alpha \log_2(\alpha) - (1-\alpha) \log_2(1-\alpha)\, , & \text{ if } \alpha \in (0, 1) \end{array} \right.

Proposition 3. For a positive integer n and any \alpha such that \alpha n \in \mathbb{N} and \displaystyle 1 \leq n\alpha \leq \left\lfloor n\left( \frac{1}{2} - \frac{1}{2n} \right) \right\rfloor ,

\displaystyle {(1-\alpha)n \choose \alpha n} \leq \frac{2^{(1-\alpha)n\,H\left( \frac{\alpha}{1-\alpha} \right)} }{ \sqrt{(1-2\alpha) n}} \leq 2^{(1-\alpha)n\,H\left( \frac{\alpha}{1-\alpha} \right)}

where H(.) is the binary entropy function.


Continue reading “Upper Bounds on Binomial Coefficients using Stirling’s Approximation”

Stirling Numbers of First and Second Kind: A Combinatorial Explanation of the Recursive Definitions

Stirling Numbers (of the first and second kind) are famous in combinatorics. There are well known recursive formulas for them, and they can be expressed through generating functions. Below we mention and explain the recursive definitions of the Stirling numbers through combinatorial ideas.

Since the Stirling numbers of the second kind are more intuitive, we will start with them.

Continue reading “Stirling Numbers of First and Second Kind: A Combinatorial Explanation of the Recursive Definitions”