# Sample reconstruction estimate Assume $n \cdot n$ samples ($n$ per row and column), $v$ validators, and each validator being able to repopulate $s$ samples (because their rows and columns intersect at $s$ points). What we want: Very high probability that at least 50% of the samples on each row and column can be repopulated from *orthogonal* rows/columns. ## Probability computation For each given sample, the probability that one of the validators can make it available as one of their reconstructed samples is $$ p = 1 - (1 - q) ^ {s v} $$ where $q = \frac{1}{n^2}$. Let's look at one line (row or column). The distribution of the number of available samples is distributed binomially with $\mathrm{Binom}(n, p)$ (approximately; the probabilities are not independent, but given the large number of samples they are very close to being independent). This distribution can be approximated using the normal distribution $\mathrm{Binom}(n, p) \approx \mathrm{Normal}(np, np(1-p))$. We want to have a small probability that less than 50% of this line is available. We can quantify this using multiples of $\alpha \sigma$; e.g. $6\sigma$ means a ca. 1 in 1 billion chance that a row cannot be reconstructed. To compute the value of $p$ where this occurs, we set $$ \frac{n}{2} = np - \alpha \sqrt{n p (1-p)} $$ thus $$ n - 2np = -2\alpha \sqrt{n p (1-p)} \\ 2np - n = 2\alpha \sqrt{n p (1-p)} \\ n^2 (4 p^2 - 4p + 1) = 4\alpha^2 n p (1-p) \\ 4( n^2 + \alpha^2 n) p^2 - 4(n^2 + \alpha^2 n)p + n^2 = 0 \\ p^2 - p + \frac{n^2}{4 (n^2 + \alpha^2 n)} = 0 $$ Solving the quadratic equation (we want the positive root), we get $$ p = \frac{1}{2} + \frac{1}{2}\sqrt{1 - \frac{n^2}{ n^2 + \alpha^2 n}} \\ p = \frac{1}{2}\left(1 + \sqrt{1 - \frac{n^2}{ n^2 + \alpha^2 n}}\right)\\ = \frac{1}{2} + \frac{1}{2}\sqrt{\frac{n^2 + \alpha^2 n - n^2}{n^2 + \alpha^2 n}} \\ = \frac{1}{2} + \frac{1}{2}\sqrt{\frac{\alpha^2 n }{n^2 + \alpha^2 n}} \\ = \frac{1}{2} \left(1+ \alpha\sqrt{\frac{ n }{ n^2 + \alpha^2 n}} \right) $$ So $$ p = 1 - (1 - q) ^ {s v} = \frac{1}{2} \left(1+ \alpha\sqrt{\frac{ n }{n^2 + \alpha^2 n}} \right)\\ (1 - q) ^ {s v} = \frac{1}{2} \left(1- \alpha\sqrt{\frac{ n }{n^2 + \alpha^2 n}} \right) $$ and thus $$ v = \frac{1}{s}\frac{\log\frac{1}{2} \left(1- \alpha\sqrt{\frac{ n }{n^2 + \alpha^2 n}} \right)}{\log (1-q)} $$ For $s=4$, $\alpha=6$ and $n=512$, we get $v=64833$ validators which are necessary for safe reconstruction.