On TB epoch length

# On TB epoch length Parameters: * $s$, number of slots (currently 7000) * $c$, blocks per cycle (8192 or 16384) * $e$, blocks per epoch Let $f$ be a delegate's stake fraction. ## Warm-up: current status How often (in number of levels) will a delegate with one roll have at least one slot? (VB said that's once every 10 levels. Is this true?) Currently (at cycle 544), the total active stake is: 718530826543983 mutez. To simplify: `7 * 10^8` tez. So at given level a baker with 6000 tez has probability: $f = \frac{6* 10^3}{7 * 10^8}$ to be a given slot's owner. A delegate has no slot at a given level with proba $(1-f)^s$. So the probability to have at least one slot at a given level is $1-(1-f)^s$. In other words, they have on average a slot every $\frac{1}{1-(1-f)^s}$ levels. For a delegate with one roll we get proba .058236 to have at least one slot. In other words, they have a slot approximatively every $17$ levels. Such a delegate has on average 492 slots per cycle (before M), or 983 slots per cycle (in M).  ## Variance of number of slots per cycle Afterthought: this analysis is not very useful, because the rewards are not per included endorsement (slots), but are depending on the expected number of slots per cycle, precisely in order to ignore the variance.  NB: the average is the same in all cases: $fsc = fse\frac{c}{e}$. Let $X$ be the random variable corresponding to the current case. This defines a binomial distribution: we have $sc$ independent draws of a random biased coin with probability $f$. Let $Y_e$ be the random variable corresponding to the new setting. We have $s\frac{c}{e}$ independent draws, each with output $0$ or $e$. It is [well-known](https://en.wikipedia.org/wiki/Variance#Commonly_used_probability_distributions) that $Var(X) = scf(1-f)$. Next, we derive $Var[Y_e]$. We have $Var(Y_e) := E[(Y_e - E[Y_e])^2] = E[Y_e^2] - E[Y_e]^2$. Let $Z_i$ be the random variable with * $Z_i=e$ if draw $i$ is a success, * $Z_i=0$ if draw $i$ is a failure. We have $E[Z_i]=fe$. We have $(Z_i-E[Z_i])^2$ is * $(e-fe)^2$ with proba $f$, * $(0-fe)^2$ with proba $1-f$. So $Var(Z_i) = e^2 (1-f)^2 f + f^2 e^2 (1-f) = e^2f(1-f)(1-f + f) = e^2f(1-f)$. We have $Y_e = \sum_{i=1}^{\frac{sc}{e}}Z_i$. It follows that $E[Y_e] = \frac{sc}{e}fe = fsc$. And $Var(Y_e) = \frac{sc}{e}e^2f(1-f) = scef(1-f)$. So, to recover the same variance, we'd need $e$ times more slots! NB: the standard deviation for $e=1$ is $21.5$ slots per cycle. (TODO: what does this mean intuitively?) The standard deviation increases by $\sqrt{e}$ with $e$.  ## Main question Given a rate (say 1%) of "accidental endorsement misses" in terms of slots (or levels?!) per cycle, how much can $e$ be increased such that the probability of a delegate with minimal stake losing its rewards is "negligeable" (say once per century)? Recall that a delegate loses its rewards if it misses one third of its *expected* slots in a cycle.  What if we ignore the "error late" of 1%, and focus on the variance alone, at least in a first step. We can compute the probability that a delegate does not receive enough slots (just due to bad luck!) to reach 66% of the expected participation, and that depending on $e$. How? The probability that a delegate has exactly $n$ slots in a cycle is $$P[Y_e=n]=\sum_{n_1+\dots+n_{k}=n}\Pi_{i=1}^kP[Z'_i=n_i]$$ where $k:=\frac{c}{e}$ and $Z'_i$ is the random variable giving the number of slots in epoch $i$. We have: * $P[Z=ne] = BD(s,n) := C_s^nf^n(1-f)^{s-n}$, * $P[Z=m]=0$ for $m$ not a multiple of $e$. ### Case $e=1$ (just to check) Hm, I don't know how to justify that $P(X=n) = BD(sc,n)$. ### Case $e=c$ This is intuitively the worst case. We have $P(X=ne) = BD(s,n)$. Now, we're interested in $$\sum_{i=0}^{b} P(X=i) = \sum_{i=0}^{b} C^i_s f^i(1-f)^{s-i}$$ where $b := \lfloor\frac{fsc}{3c}\rfloor = \lfloor\frac{fs}{3}\rfloor$. When $e=c$, if a delegate has at least 1 slot, then it has at least $c$ slots! For a delegate with one roll, $b=\lfloor7000\frac{6}{7*10^5}\rfloor=0$. So the sum equals the probability that currently such a delegate has no slot at a given level (when $e=1$). That's actually very high: .941764. So not an interesting case! ### General case TODO... | $e$ | proba | frequency | | -------- | -------- | --- | | $1$ | $3.882 * 10^{-15}$ | | | $2$ | $7.694 * 10^{-8}$ | once every 100000 years | | $4$ | $1.035 * 10^{-4}$ | once every 75 years | | $8$ | 0.004346 | once every 2 years | | $16$ | 0.03178 | once every 3 months | | $32$ | 0.09478 | once per month | For the frequency: there are 100 * 365 * 24 * 60 * 2 / 8192 = 12832 cycles per century --- - Le protocol calcule $E_d$ qui donne le nombre d'endorsement attendus pour le cycle pour le délégué $d$. Du coup, quel est la probabilité qu'effectivement, ce délégué lui soit attribué moins de $\frac{2\times E_d}{3}$? Puisque dans ce cas, il serait dans l'impossibilité de toucher ces rewards. Dans ce cas là, $E_d=\frac{fsc}{e}$ où $e=1$ pour le moment. Dans le pire cas, on a $f=\frac{6000}{700000000}$ La probabilité d'avoir *au moins* $1$ slot dans un bloc c'est $x=1-(1-f)^s$.  La probabilité que son slot apparaisse dans exactement $i$ blocs c'est $C^i_c x^i(1-x)^{c-i}$. Donc la probabilité que ce délégué ait moins de $E_d$ blocs est $$\sum_{i=0}^{\frac{2E_d}{3} - 1} C^i_c x^i(1-x)^{c-i}$$. ce qui équivalent à $$\sum_{i=0}^{\frac{E_d}{3}} C^i_c ((1-f)^s)^{c-i}((1-(1-f)^s))^{i}$$. $$E_d=492$$ --- - 1 % of endorsements is lost - Given n blocks with at least one slot for a delegate $d$, what is the probability that this delegate lose its rewards because it missed $\frac{n}{3}$ endorsements? It is $\frac{1}{100}^{\frac{n}{3}} < 10^{-6}$. - Likely for small value of $n$ its unlikely - If $E(Y_e)$, what is the probability that $Y_e < n$   --- ## Attic