In Satoshi Nakamoto's paper : Bitcoin: A Peer-to-Peer Electronic Cash System, he describes a scenario where an attacker is trying to add falsified transactions to the blockchain.
He writes : "The race between the honest chain and an attacker chain can be characterized as a Binomial Random Walk. The success event is the honest chain being extended by one block, increasing its lead by $+1$, and the failure event is the attacker's chain being extended by one block, reducing the gap by $-1$.
We can calculate the probability he ever
reaches break-even, or that an attacker ever catches up with the honest chain, as follows" :
Let $p = $ probability an honest node finds the next block
Let $q = $ probability the attacker finds the next block
Let $q_z = $ probability the attacker will ever catch up from $z$ blocks behind
And so $q_z = 1$ if $p \leq q$, and $q_z = (q/p)^z$ if $p > q$.
I'm not sure how he arrived at this. Firstly, I have no idea why $q_z = 1$ if $p \leq q$.
Secondly, from what I understand from a binomial distribution, the probability of the attacker catching up from $z$ blocks from behind should be equal
to $z \choose z$ $q^z p^0 = q^z$. Any insights appreciated.
Best Answer
These are results of simple random walks on $\mathbb{Z}$. If you are more (or equally) likely to move right than move left, then you will with probability $1$ reach arbitrarily high values. Otherwise, the probability you ever reach $z\in\mathbb{N}$ units right of where you started is given by $(q/p)^z$, where $q$ is the probability of moving right on a step, and $p$ is the probability of moving left. See this for example for reading on simple random walks (beware that their $p$ and $q$ may be reversed from here though).