51% attack: Gambler’s ruin problem

We discussed the probability of mining the next block in the previous article and started to understand the probability of double-spending. Towards the end of the article, we saw that double spending is similar to the gambler’s ruin problem. In this article, we will try to find the probability of double spending by studying the gambler’s ruin problem.

First, let’s try to understand the gambler’s ruin problem. Assume that a gambler starts with i dollars. If they win the bet, they will make 1 dollar. If they lose the bet, they lose 1 dollar. The game ends, if they lose all their money or they win n more dollars than what they started with. In other words, the gambler should either reach 0 dollars or i + n =T dollars if the game is to end.

Let’s try to find the probability of the gambler reaching T dollars before they hit 0.

• Let W be the event that the gambler reaches T before they reach 0.
• Let D_t be the amount of dollars the gambler has at any step t.
• Let P_i be the probability that the gambler reaches T before they reach 0 provided that they begin with i dollars.

If i is equal to 0, then P_i is also zero. This is because when the gambler has no dollars left, they can’t gamble anymore. So, the probability of the gambler reaching T becomes 0. If i is equal to T, then P_i becomes 1 since the probability of reaching T when you already have T is always 1.

Now, let’s try to find out P_i when i is greater than 0 and less than T. We can define it as follows:

P_i = P(W | D_0=i) \text{ ---(1)}

That is, P_i is equal to the probability of event W happening provided that the gambler is at step 0 and has i dollars.

At the first step, when the gambler makes the first bet, they can either win 1 dollar or lose. Let E be the event the first bet is won, and L be the event that it is lost. If the gambler wins, they will have i + 1 dollar; if they lose, they will have i – 1 dollar. Now, we can once again rewrite equation (1) replacing i with i – 1 or i + 1 dollars. As you can see this becomes a recurrence. Let’s try to find a way to express this recurrence.

A gambler can win the first bet and get to T or lose the first bet and get to T. This can be expressed using the following Venn diagram.

Using this, let’s rewrite equation (1) utilizing the theorem of total probability.

P_i=P(W \cap E | D_0=i)  +  P(W \cap L | D_0=i) \text{ ---(2)}

Using the definition of conditional probability, we can write:

P(W \cap E | D_0=i) = P(E | D_0=i) . P(W | E\cap D_0=i) \text{ ---(3)}

So, using conditional probability, let’s rewrite equation (2).

P_i= P(E | D_0=i) . P(W | E\cap D_0=i) + P(L | D_0=i) . P(W | L\cap D_0=i) \text{ ---(4)}

Let q be the probability of the gambler winning the first bet and p be the probability of losing it.

So,

P(E | D_0=i) = q

And

P(L | D_0=i) = p

When the gambler wins the first step, the dollars they have become i + 1 and they move to the next bet.

So,

(E \cap D_0=i )= D_1=i+1

Similarly,

(L \cap D_0=i )= D_1=i-1

Plugging all these back into equation 4, we get:

P_i= q.P(W | D_1=i+1) + p.P(W | D_1=i-1) \text{ ---(5)}

Now, consider this equation:

P(W | D_1=i+1)

This can be considered as the gambler starting to bet with i + 1 dollars in hand. The history is not important here. We can just assume the next bet is the first bet of the gambler with i + 1 dollars in hands. So, we can write the following equations:

P_{i+1}=P(W|D_0 =i+1)

Similarly, we can say:

P_{i-1}=P(W|D_0 ={i-1})

Using this, let’s rewrite equation (5).

P_i= q. P_{i+1} + p. P_{i-1} \text{ ---(6)}

This is a recurrence.

We can summarize P_i as follows:

P_i = 

\begin{cases}

0 & \text {if $i$=0;}\\

1 & \text{if $i$=$T$;}\\

q. P_{i+1} + p. P_{i-1}  & \text{if 0<$i$<$T$.}

\end{cases}

We know p + q = 1. Therefore, we can write,

P_i = 1. P_i

P_i = (p+q) P_i

P_i = p .P_i + q.P_i \text{ ---(7)}

Let’s replace P_i in equation (6) with equation (7).

p .P_i + q.P_i  = q. P_{i+1} + p. P_{i-1}

p .P_i - p. P_{i-1} = q .P_{i+1} - q.P_i

p(P_i - P_{i-1} ) = q(P_{i+1} - P_i )

\frac{p}{q}.(P_i - P_{i-1} )= P_{i+1} - P_i

P_{i+1} - P_i=\frac{p}{q}.(P_i - P_{i-1} ) \text{ ---(8)}

Now, let i be 1. We can rewrite this equation as follows:

P_2 - P_1=\frac{p}{q}.(P_1 - P_0 ) \text{ ---(9)}

Let’s increment i by 1.

P_3 - P_2=\frac{p}{q}.(P_2 - P_1 ) \text{ ---(10)}

Let’s substitute P₂ – P₁ in equation (10) with its equivalent in equation (9):

P_3 - P_2 = \frac{p}{q}. \frac{p}{q} (P_1 – P_0)

P_3 - P_2 = (\frac{p}{q})^2 (P_1 – P_0)

But

P_0=0

since the gambler loses when they have 0 dollars. So, we can write,

P_3 - P_2 = (\frac{p}{q})^2 .P_1

We can generalize this observation as follows:

P_{i+1} - P_i = (\frac{p}{q})^i .P_1 \text{ ---(11)}

We can write P_i+1 as follows:

P_{i+1} = P_{i+1}  + (-P_i + P_i) + (-P_{i-1}+ P_{i-1}) …+(-P_3 + P_3)+(-P_2+P_2)+(-P_1+P_1)-P_0

Note -P_i + P_i = 0 and P₀ = 0. So, the equation is satisfied.

Let’s rearrange the above equation.

P_{i+1} = (P_{i+1} - P_i) + (P_i  –  P_{i-1}) …+( P_3-P_2)+(P_2-P_1)+(P_1-P_0)

We can replace (P_i+1 – P_i) with equation (11). We can do the same with the rest.

Thus, we can obtain:

P_{i+1} = P_1. \sum_{k=0}^ i (\frac{p}{q})^k \text{ ---(12)}

This function is the same as the sum of a geometric progression. A geometric progression is a sequence of numbers that we obtain by multiplying the previous number by a constant. The following is an example of a geometric progression.

2, 4, 8, 16, 32, 64, 128

Here the constant that is used to multiply the previous number is 2. This sequence of numbers can also be expressed as

ar^0, ar^1, ar^2, ar^3 …

Here, a is the first number in the sequence. In our example, a=2. r is the common ratio or the constant that is used to multiply the previous number. In our example, r=2.

We can find the sum of a geometric progression until number n in the sequence using the following equation.

\sum_{k=0}^{n-1} ar^k =

\begin{cases}

\frac{a(1-r^n)}{1-r} & \text{if r != 1}\\

an & \text{if r = 1}\\

\end{cases} \text{ ---(13)}

Now, we can see that this equation is very similar to equation (12). a can be replaced by P_i , r by (p/q), and (n-1) by i. So, we can rewrite equation (12) using equation 13.

P_{i+1}=

\begin{cases}

\frac{P_1(1-(\frac{p}{q})^{i+1})}{1-\frac{p}{q}} & \text{if $\frac{p}{q}$ != 1}\\

P_1(i+1) & \text{if $\frac{p}{q}$ = 1}\\

\end{cases}

(p/q) can be equal to one only if p and q are equal. Since p and q add up to 1, if p and q are to be both equal, then they should both be equal to 0.5. So, we can rewrite the above equation as,

P_{i+1}=

\begin{cases}

\frac{P_1(1-(\frac{p}{q})^{i+1})}{1-\frac{p}{q}} & \text{if $p$ != $q$}\\

P_1(i+1) & \text{if $p=q=0.5$ }\\

\end{cases} \text{ ---(14)}

Now, let (i + 1) be T. We know the probability P_T of the gambler winning when they have T dollars is 1. So,

P_T = 1

Let’s substitute (i + 1) in equation (14) with T.

P_T=

\begin{cases}

\frac{P_1(1-(\frac{p}{q})^T)}{1-\frac{p}{q}} & \text{if $p$ != $q$}\\

P_1.T & \text{if $p=q=0.5$ }\\

\end{cases}

Let’s solve the above equation for P₁

When p != q

\frac{P_1 (1-(\frac{p}{q})^T)}{(1-\frac{p}{q})}=1

\frac{1-(\frac{p}{q})^T}{(1-\frac{p}{q})}=\frac{1}{P_1 }

{P_1 } = \frac{(1-\frac{p}{q})}{1-(\frac{p}{q})^T}

When p = q = 0.5

P_1 . T = 1

P_1 = \frac{1}{T}

This can be summarized as

P_1 =

\begin{cases}

\frac{(1-\frac{p}{q})}{1-(\frac{p}{q})^T} & \text{if $p$ != $q$}\\

\frac{1}{T} & \text{if $p=q=0.5$}\\

\end{cases}

We can use this equation to replace the value of P₁ in equation (14).

When p != q

P_1 = \frac{1-\frac{p}{q}}{1-(\frac{p}{q})^T}.\frac{1-(\frac{p}{q})^{i+1}}{1-\frac{p}{q}}

P_1 = \frac{1-(\frac{p}{q})^{i+1}}{ 1-(\frac{p}{q})^T}

When p = q = 0.5

P_1 = \frac{1}{T} . (i+1)

P_1 = \frac{i+1}{T}

We can summarize this as follows,

P_{i+1} =

\begin{cases}

\frac{1-(\frac{p}{q})^{i+1}}{ 1-(\frac{p}{q})^T} & \text{$p$ != $q$}\\

\frac{i+1}{T} & \text{$ p = q = 0.5$}\\

\end{cases}

Since i doesn’t appear alone in the equation and it only appears as i + 1, we can replace i + 1 with i.

P_i =

\begin{cases}

\frac{1-(\frac{p}{q})^i}{ 1-(\frac{p}{q})^T} & \text{$p$ != $q$}\\

\frac{i}{T} & \text{$ p = q = 0.5$}\\

\end{cases}

We have now found a formula to find the probability of a gambler reaching T with i dollars in their hands. Now, let’s see how we can apply this solution to the gambler’s ruin problem to find the probability of an attacker catching up with an honest chain.