summaryrefslogtreecommitdiff
path: root/source/know/concept/von-neumann-extractor
diff options
context:
space:
mode:
Diffstat (limited to 'source/know/concept/von-neumann-extractor')
-rw-r--r--source/know/concept/von-neumann-extractor/index.md36
1 files changed, 18 insertions, 18 deletions
diff --git a/source/know/concept/von-neumann-extractor/index.md b/source/know/concept/von-neumann-extractor/index.md
index 59566f1..3c54196 100644
--- a/source/know/concept/von-neumann-extractor/index.md
+++ b/source/know/concept/von-neumann-extractor/index.md
@@ -14,20 +14,20 @@ it extracts the entropy, and outputs a "perfectly random" stream.
As input, the Von Neumann extractor expects
a stream of independent (uncorrelated) bits,
i.e. the result of a [Bernoulli process](/know/concept/binomial-distribution/),
-where each bit is $0$ with probability $p$,
-and $1$ with probability $1 \!-\! p$.
-Crucially, $p$ does not need to be $1/2$;
+where each bit is $$0$$ with probability $$p$$,
+and $$1$$ with probability $$1 \!-\! p$$.
+Crucially, $$p$$ does not need to be $$1/2$$;
there may be a bias.
-The extractor will output a uniformly random stream with $p = 1/2$.
-Given input bits $a_1, a_2, ...$, it achieves this
-by looking at the bits in pairs $(a_1, a_2)$, $(a_3, a_4)$, etc.
+The extractor will output a uniformly random stream with $$p = 1/2$$.
+Given input bits $$a_1, a_2, ...$$, it achieves this
+by looking at the bits in pairs $$(a_1, a_2)$$, $$(a_3, a_4)$$, etc.
Then:
-+ If $a_n = a_{n+1}$, it discards both bits.
-+ If $a_n \neq a_{n+1}$, it keeps the first bit $a_n$, and discards $a_{n+1}$.
++ If $$a_n = a_{n+1}$$, it discards both bits.
++ If $$a_n \neq a_{n+1}$$, it keeps the first bit $$a_n$$, and discards $$a_{n+1}$$.
-Evidently, the first case $a_n = a_{n+1}$ occurs with the following probabilities:
+Evidently, the first case $$a_n = a_{n+1}$$ occurs with the following probabilities:
$$\begin{aligned}
P(0, 0)
@@ -37,7 +37,7 @@ $$\begin{aligned}
= (1 - p)^2
\end{aligned}$$
-Meanwhile, the second case $a_n \neq a_{n+1}$ occurs with probabilities given by:
+Meanwhile, the second case $$a_n \neq a_{n+1}$$ occurs with probabilities given by:
$$\begin{aligned}
P(0, 1)
@@ -47,18 +47,18 @@ $$\begin{aligned}
= (p - 1) p
\end{aligned}$$
-Crucially, they are equal; $P(0, 1) = P(1, 0)$.
-Therefore, if the extractor encounters an input pair satisfying $a_n \neq a_{n+1}$,
-the first bit $a_n$ is $0$ or $1$ with a 50-50 probability,
-regardless of $p$.
+Crucially, they are equal; $$P(0, 1) = P(1, 0)$$.
+Therefore, if the extractor encounters an input pair satisfying $$a_n \neq a_{n+1}$$,
+the first bit $$a_n$$ is $$0$$ or $$1$$ with a 50-50 probability,
+regardless of $$p$$.
Since the extractor only keeps those bits,
its output is guaranteed to be "perfectly random".
Clearly, because it discards many of the bits,
-the output stream will have a length $N_\mathrm{out} < N_\mathrm{in}$.
-The exact value of $N_\mathrm{out}$ is as follows,
-where $P(0, 1) + P(1, 0)$ is the probability that we keep a bit,
-and the factor $1/2$ is due to us discarding half of the pair even in that case:
+the output stream will have a length $$N_\mathrm{out} < N_\mathrm{in}$$.
+The exact value of $$N_\mathrm{out}$$ is as follows,
+where $$P(0, 1) + P(1, 0)$$ is the probability that we keep a bit,
+and the factor $$1/2$$ is due to us discarding half of the pair even in that case:
$$\begin{aligned}
N_\mathrm{out}