Modelling question regarding 99th percentiles/confidence intervals

Question

I'm currently trying to implement the simulation results from Roughgarden et al. (Stanford University), i.e. his paper from 2017 named "Incentive Compatibility of Bitcoin Mining Pool Reward Functions" (link: https://www.ifca.ai/fc16/preproceedings/28_Schrijvers.pdf, pages 13 and 14).

Short intro to the problem: in Bitcoin mining we have to solve a computationally difficult problem which shortly after its inception has become too difficult for a single miner to solve economically. This was the reason for the foundation of "bitcoin mining pools", where different single miners brought together their computation capacity in order to decrease the volatility of their payouts would they mine solo.

Now in the model of the paper we are acting as a bitcoin pool manager who tries to distribute the bitcoin block rewards among the participants in the pool regarding the computational power they brought into the system. Because the pool operators don't know what exactly that amount of computational power the individual miners brought into the pool is, they have to estimate it. This is done by miners participating in the pool committing so called "shares" (= partial solutions) to the pool operator which are computationally easier to solve than the actual full solution. Now the question is: how does the pool operator distribute the rewards among the miners participating in the pool?

Variables and definitions in this model:

• $\alpha_i $ = an individual miner i's computational capacity (only known to him)
• $D$ = each partial solution constitutes a full solution with prob. $\frac{1}{D}$
• $b_i$ = the number of shares (= partial solutions) committed to the pool operator by miner i
• one round starts with the computational puzzle and ends with a miner finding a solution for it.

The two most basic answers to that question are the PPS ("pay-per-share") and proportional payoff methods. I am only describing the prop reward function because it is suffice for my question.

• The proportional reward function is $R_i^{(prop)}(\boldsymbol{b}) = \frac{\boldsymbol{b_i}}{K}$, where $K$ is the sum of all shares committed by the miners in the pool in the respective round, i.e. $K = \| \boldsymbol{b} \|_1 = \sum_{i = 1}^ n \boldsymbol{b_i}$. This method in the end has an expected value for each individual miner participating in the pool of exactly $\alpha_i$, the true mining capacity of an individual miner.

Now we want to model the time it takes for a given miner to gain a given number of bitcoins with 99% certainty. In the simulations we assume the miner's capacity is $\alpha_i$ = 0.001, D = 1.000.000 and we normalize the block reward to 1 BTC per round. What my question is: how can I model the 99th percentile to earn rewards? Especially the comparison between solo mining and proportional mining. Roughgarden's results are that it takes much more rounds until you get a certain amount of bitcoins with 99% certainty if you mine sole than with the proportional pool mining rewards. My guess and experiments were to run different bernoulli distributions with parameter $p = 0.001$ and running it in a for loop several thousand times. But I'm really not sure what the approach is like to compute the 99% certainty (maybe the confidence interval?) in this case. We expect, because $\alpha_i$ = 0.001, that in around 1000 rounds we will be lucky enough to find the solution one time. But I can't relate the modeling to quantifying the certainty. Would be great if someone could explain to me what and how to calculate. Appreciate your time.

Answer 1

A way to think of this: what is the distribution of the number of trials you need before your first success?

Let's think step by step.

What is the probability that you will need $n$ trials before your first success, if your probability of success per round is $\alpha_i = 0.001$?

Well, for that to happen you would need $n-1$ failures and then a success. It is straighforward to compute this probability:

$$ P(N=n | \alpha_i) = (1-\alpha_i)^{n-1} \alpha_i $$

This is a geometric distribution, whose quantiles we can compute numerically.

import scipy.stats as stats
import matplotlib.pyplot as plt
import numpy as np
alpha = 0.001

q99 = stats.geom.ppf(0.99, alpha)

print(f"The 99th percentile is {q99}")

x = np.linspace(0,5000,10000)
cdf = stats.geom.cdf
plt.plot(x,cdf(x, alpha))
plt.show()

The code above outputs:

The 99th percentile is 4603.0