NIST SP 800-90B 日本語訳

\(A=\{x_1,x_2,\ldots,x_k\}\) The alphabet, i.e., the set of all possible symbols that a (digitized) noise source produces.

\(H\) The min-entropy of the samples from a (digitized) noise source or of the output from an entropy source; the min-entropy assessment for a noise source or entropy source.

\(H_I\) Initial entropy estimate.

\(H_{\mathit{original}}\) Entropy estimate of the sequential dataset

\(H_{\mathit{submiter}}\) The entropy estimate provided by the submitter.

\(L\) The number of samples.

\(\log_b(x)\) The logarithm of \(x\) with respect to base \(b\).

\(\min(a, b)\) A function that returns the minimum of the two values \(a\) and \(b\).

\(\max(a, b)\) A function that returns the maximum of the two values \(a\) and \(b\).

\(M[i][j]\) The \(j\)th sample from the \(i\)th restart of the noise source.

\(n\) The length of \(x_i\) in bits.

\(\mathit{nw}\) Narrowest width of the conditioning component

\(k\) The number of possible symbols, i.e., the size of the alphabet.

\(\alpha\) The probability of falsely rejecting the null hypothesis (type I error).

A function that returns the absolute value of \(a\).

\(|a|\)

The probability for an observation (or occurrence) of the symbol \(x_i\) in \(A\).

\(p_i\)

\(p_{\mathit{max}}\) The probability of observing the most common symbol from a noise source.

\(S=(s_1,\ldots,s_L)\) A dataset that consists of an ordered collection of \(L\) samples, where \(s_i \in A\).

\(x_i\)

The interval of numbers between \(a\) and \(b\), including \(a\) and \(b\).

\([a, b]\)

A function that returns the smallest integer greater than or equal to \(x\); also known as the ceiling function.

\(\lceil x \rceil\)

A function that returns the largest integer less than or equal to \(x\); also known as the floor function.

\(\lfloor x \rfloor\)

\(\parallel\)

\(\oplus\)

The min-entropy of an independent discrete random variable \(X\) that takes values from the set \(A=\{x_1,x_2,\ldots,x_k\}\) with probability \(\Pr(X=x_i) = p_i\) for \(i=1,\ldots,k\) is defined as

If \(X\) has min-entropy \(H\), then the probability of observing any particular value for \(X\) is no greater than \(2^{-H}\). The maximum possible value for the min-entropy of a random variable with \(k\) distinct values is \(\log_2 k\), which is attained when the random variable has a uniform probability distribution, i.e., \(p_1 = p_2 = \ldots = p_k = 1/k\).

GetEntropy
Input:
\(\mathit{bits\_of\_entropy}\): the requested amount of entropy
Output:
\(\mathit{entropy\_bitstring}\): The string that provides the requested entropy.
\(\mathit{status}\): A Boolean value that is TRUE if the request has been satisfied, and is FALSE otherwise.

GetNoise
Input:
\(\mathit{number\_of\_samples\_requested}\): An integer value that indicates the requested number of samples to be returned from the noise source.
Output:
\(\mathit{noise\_source\_data}\): The sequence of samples from the noise source with a length of \(\mathit{number\_of\_samples\_requested}\).
\(\mathit{status}\): A Boolean value that is TRUE if the request has been satisfied, and is FALSE otherwise.

HealthTest
Input:
\(\mathit{type\_of\_test\_requested}\): A bitstring that indicates the type or suite of tests to be performed (this may vary from one entropy source to another).
Output:
\(\mathit{status}\): A Boolean value that is TRUE if the entropy source passed the requested test, and is FALSE otherwise.

3. For the restart tests (see Section 3.1.4), the entropy source must be restarted 1000 times; for each restart, 1000 consecutive samples shall be collected directly from the noise source. The restart data shall be extracted whenever the noise source is ready and able to provide data that can be used for producing entropy source output. This data is stored in a \(1000 \times 1000\) restart matrix \(M\), where \(M[i][j]\) represents the \(j^{\text{th}}\) sample from the \(i^{\text{th}}\) restart.

The submitter shall provide an entropy estimate for the noise source outputs, which is based on the submitter’s analysis of the noise source (see Requirement 3 in Section 3.2.2). This estimate is denoted as \(H_{\mathit{submitter}}\).

After determining the entropy estimation track, a min-entropy estimate per sample, denoted as \(H_{\mathit{original}}\), for the sequential dataset is calculated using the methods described in Section 6.1 (for the IID track) or Section 6.2 (for the non-IID track). If the alphabet size is greater than 256, it shall be reduced to at most 256 symbols (see Section 6.4).

If the sequential dataset is not binary, an additional entropy estimation (per bit), denoted \(H_{\mathit{bitstring}}\), is estimated. First, the sequential dataset that contains \(L\) samples (each having \(n\) bits) is considered as a bitstring of size \(nL\). The bits after the first 1 000 000 bits may be ignored. Then, the estimation is done based on the entropy estimation track, as specified in the previous paragraph, and \(H_{\mathit{bitstring}}\)

is calculated. Then, the entropy per sample is estimated to be \(n \times H_{\mathit{bitstring}}\).

The initial entropy estimate of the noise source is calculated as \(H_I = \min(H_{\mathit{original}}, n \times H_{\mathit{bitstring}}, H_{\mathit{submitter}})\) for non-binary sources and as \(H_I = \min(H_{\mathit{original}}, H_{\mathit{submitter}})\) for binary sources.

To construct restart data, the entropy source shall be restarted \(r = 1000\) times; for each restart, \(c = 1000\) consecutive samples shall be collected directly from the noise source. The collection of the data shall be done as soon as the entropy source is ready to produce outputs for real-world use (e.g., after start-up tests). Note that an entropy source, in its real-world use and during restart testing, may inhibit outputs for a time immediately after restarting in order to allow any transient weak behavior to pass. The output samples are stored in an \(r\) by \(c\) matrix \(M\), where \(M[i][j]\) represents the \(j\)^th sample from the \(i\)^th restart.

Two datasets are constructed using the matrix \(M\):

- The row dataset is constructed by concatenating the rows of the matrix \(M\), i.e., the row dataset is \(M[1][1] \parallel \ldots \parallel M[1][c] \parallel M[2][1] \parallel \ldots \parallel M[2][c] \parallel \ldots \parallel M[r][1] \parallel \ldots \parallel M[r][c]\).
- The column dataset is constructed by concatenating the columns of the matrix \(M\), i.e., the column dataset is \(M[1][1] \parallel \ldots \parallel M[r][1] \parallel M[1][2] \parallel \ldots \parallel M[r][2] \parallel \ldots \parallel M[1][\mathrm{c}] \parallel \ldots \parallel M[r][c]\).

The restart tests check the relations between noise source samples generated after restarting the entropy source, and compare the results to the initial entropy estimate, \(H_I\) (see Section 3.1.3).

First, the sanity check described in Section 3.1.4.3 is performed on the matrix \(M\). If the test fails, the validation fails and no entropy estimate is awarded.
If the noise source does not fail the sanity check, then the entropy estimation methods described in Section 6.1 (for the IID track) or Section 6.2 (for the non-IID track) are performed on the row and the column datasets, based on the track of the entropy source. Let \(H_{\mathrm{r}}\) and \(H_{\mathrm{c}}\) be the resulting entropy estimates of the row and the column datasets, respectively. The entropy estimates from the row and the column datasets are expected to be close to the initial entropy estimate \(H_I\). If the minimum of \(H_r\) and \(H_c\) is less than half of \(H_I\), the validation fails, and no entropy estimate is awarded. Otherwise, the entropy assessment of the noise source is taken as the minimum of the row, the column and the initial estimates, i.e., \(\min(H_{\mathrm{r}}, H_{\mathrm{c}}, \mathrm{H}_I)\).

If the noise source does not fail the restart tests, and the entropy source does not include a conditioning component, the entropy source will be validated at \(H = \min(H_{\mathrm{r}}, H_{\mathrm{c}}, \mathrm{H}_I)\). If the entropy source includes a conditioning component, the entropy assessment of the entropy source is updated as described in Section 3.1.5.

This test checks the frequency of the most common value in the rows and the columns of the matrix \(M\). If this frequency is significantly greater than the expected value, given the initial entropy estimate \(H_I\) calculated in Section 3.1.3, the restart test fails. In this case, the validation fails no entropy estimate is awarded.

This sanity check is based on a binomial test, where there are two possible outcomes for each trial: the most frequent value or any other value is observed. The purpose of the test is to determine whether the most frequent value appears more than would be expected, given the initial entropy estimate, \(H_I\). The probability of type I error, denoted \(\alpha\), is set at 0.01 over the entire sanity check, where each of the 2000 binomial experiments³ has type I error probability of 0.000 005.

Given the 1000 by 1000 restart matrix and the initial entropy estimate \(H_I\), the test is performed as follows:

1. Let \(p = 2^{-H_I}\). Let \(\alpha\) be 0.000 005.

2. For each row (\(1 \le i \le 1000\)) of the matrix, count the number of occurrences of each sample present in the row. Set \(X_{Ri}\) to the highest count value for row \(i\). Let \(X_R\) be the maximum count value for all the rows, i.e., \(X_R = \max(X_{R1}, \ldots, X_{R1000})\).

3. For each column (\(1 \le i \le 1000\)) of the matrix, count the number of occurrences of each sample present in the column. Set \(X_{Ci}\) to the highest count value for column \(i\). Let \(X_C\) be the maximum count value for all the columns, i.e., \(X_C = \max(X_{C1}, \ldots, X_{C1000})\).

4. Let \(X_{\mathit{max}} = \max(X_c, X_R)\).

5. Calculate \(\mathrm{P}(X \ge X_{\mathit{max}}) = \sum_{j=X_{\mathit{max}}}^{1000} \binom{1000}{j} p^j (1-p)^{1000-j}\). If \(\Pr(X \ge X_{\mathit{max}}) < \alpha\), the test fails. Otherwise, the test passes.

The optional conditioning component gets inputs from the noise source and generates the output of the entropy source. The size of the input and the output of the conditioning component in bits, denoted as \(n_{\mathit{in}}\) and \(n_{\mathit{out}}\), respectively, shall be fixed and shall be specified by the submitter. Noise source outputs are concatenated to construct \(n_{\mathit{in}}\)-bit input to the conditioning function. The entropy of the input, denoted \(h_{\mathit{in}}\), depends on the number of samples needed to construct the \(n_{\mathit{in}}\)-bit input. If \(w\) samples are needed, then \(h_{\mathit{in}}\) is estimated to be \(w \times h\) bits. The size of the conditioning component input shall be a multiple of the size of the noise source output.

Since the conditioning component is deterministic, the entropy of the output is at most \(h_{\mathit{in}}\). However, the conditioning component may reduce the entropy of the output. The entropy of the output from the conditioning component is denoted as \(h_{\mathit{out}}\), i.e., \(h_{\mathit{out}}\) bits of entropy are contained within the \(n_{\mathit{out}}\)-bit output. The entropy of the output also depends on the internals of the

For Hash_df and Block_cipher_df, the output length indicated in the table is used as the \(\mathit{no\_of\_bits\_to\_return}\) input parameter for the invocation of Hash_df and Block_Cipher_df (see SP 800-90A).

where \(\operatorname{Output\_Entropy}(n_{\mathit{in}}, n_{\mathit{out}}, \mathit{nw}, h_{\mathit{in}})\) is described as follows⁴:

1. Let \(P_{\mathit{high}} = 2^{-h_{\mathit{in}}}\) and \(P_{\mathit{low}} = \frac{(1 - P_{\mathit{high}})}{2^{n_{\mathit{in}}} - 1}\).

2. \(n = \min(n_{\mathit{out}}, \mathit{nw})\).

3. \(\psi = 2^{n_{\mathit{in}} - n} P_{\mathit{low}} + P_{\mathit{high}}\)

4. \(\mathrm{U} = 2^{n_{\mathit{in}} - n} + \sqrt{2\, n (2^{n_{\mathit{in}} - n}) \ln(2)}\)

5. \(\omega = U \times P_{\mathit{low}}\)

6. Return \(-\log_2(\max(\psi, \omega))\)

The entropy source will be assessed at the min-entropy per conditioned output, \(h_{\mathit{out}}\), computed above. Vetted conditioning components are permitted to claim full entropy outputs.

⁴ The formula used to generate Output_Entropy() is adapted from the formula \(k_\alpha = \frac{m}{n} + \alpha \sqrt{2 \frac{m}{n} \ln n}\) provided in Theorem 1 of [RaSt98], such that \(m\) is equal to \(2^{n_{\mathit{in}}}\), \(n\) is equal to \(2^n\) and \(\alpha\) is equal to 1.

Note that it is acceptable to truncate the outputs from a vetted conditioning component. If this is done, the entropy estimate is reduced to a proportion of the output (e.g., if there are six bits of entropy in an eight-bit output and the output is truncated to six bits, then the entropy is reduced to \(3/4 \mathbin{\mathrm{x}} 6 = 4.5\) bits).

When additional noise sources are available, the length of the input (\(n_{\mathit{in}}\)) shall only include the inputs from the primary noise source.

For non-vetted conditioning components, the entropy in the output depends on the entropy and size of the input (\(h_{\mathit{in}}\) and \(n_{\mathit{in}}\)), the size of the output (\(n_{\mathit{out}}\)), and the size of the narrowest internal width (\(\mathit{nw}\)) and the entropy of the conditioned sequential dataset (as described in item 2 of Section 3.1.1), which shall be computed using the methods described in either Section 6.1 (for IID data) or Section 6.2 (for non-IID data). Let the obtained entropy estimate per bit be \(h'\).

The output of the conditioning component (\(n_{\mathit{out}}\)) shall be treated as a binary string, for purposes of the entropy estimation.

The entropy of the conditioned output is estimated as

The description of \(\mathrm{Output\_Entropy}\) is given in Section 3.1.5.1.2. To avoid approving an entropy source having a non-vetted conditioning component with full entropy, \(n_{\mathit{out}}\) is multiplied by the constant 0.999. The entropy source will be validated at the min-entropy per conditioned output, \(h_{\mathit{out}}\), computed above.

1. The submitter shall document which conditioning component is used and the details about its implementation (e.g., the hash function and/or key size used). Documentation shall include the input and the output sizes (\(n_{\mathit{in}}\) and \(n_{\mathit{out}}\)).

4. Any value which is used to determine the key shall not be used as any other input to the conditioning component. The input entropy to the conditioning component (\(h_{\mathit{in}}\)) shall not include any entropy provided to the key of a keyed function.

Continuous health tests are run indefinitely on the outputs of the noise source⁷ while the noise source is operating. Continuous tests focus on the noise source behavior and aim to detect failures as the noise source produces outputs. The purpose of continuous tests is to allow the entropy source to detect many kinds of failures in its underlying noise source. These tests are run continuously on all digitized samples obtained from the noise source, and so tests must have a very low probability of raising a false alarm during the normal operation of the noise source. In many systems, a reasonable false positive probability will make it extremely unlikely that a properly functioning device will indicate a malfunction, even in a very long service life. Continuous tests are resource-constrained − this limits their ability to detect noise source failures – so they are usually designed so that only gross failures are likely to be detected. Note that continuous health tests operate over a stream of values. These sample values may be output from the entropy source as they are generated and (optionally) processed by a conditioning component; there is no need to inhibit output from the noise source or entropy source while running the test. It is important to understand that this may result in poor entropy source outputs for a time, since the error is only signaled once significant evidence has been accumulated, and these values may have already been output by the entropy source. As a result, it is important that the false positive probability be set to an acceptable level. In the following discussion, all calculations assume that a false positive probability of approximately one error in \(2^{20}\) samples generated by the noise source is acceptable; however, the formulas given can be adapted for different false positive probabilities selected by the submitter. On-demand health tests can be called at any time. This Recommendation does not require performing testing during operation. However, it does require that the entropy source be capable of performing on-demand health tests of the noise source output. Note that resetting, rebooting, or powering up are acceptable methods for initiating an on-demand test if the procedure results in the immediate execution of the start-up tests. Samples collected from the noise source during on-demand health tests shall not be available for use until the tests are completed, however these samples may be discarded at any time, or may be used after the completion of the tests providing that there are no errors.

3. The optimal value for the false positive probability may depend on the rate that the entropy source produces its outputs. For the approved continuous health tests, the false positive probability⁸ is recommended to be between \(2^{-20}\) and \(2^{-40}\). Lower probability values are acceptable. The submitter shall specify and document a false positive probability suitable for their application.

Like all statistical tests, both of these tests have a false positive probability − the probability that a correctly functioning noise source will fail the test on a given output. In many applications, a reasonable choice for the probability of type I error is \(\alpha = 2^{-20}\); this value will be used in all the calculations in the rest of this section. The developer of the entropy source shall determine a reasonable probability of type I error (and corresponding cutoff values), based the details of the entropy source and its consuming application.

The goal of the Repetition Count Test is to quickly detect catastrophic failures that cause the noise source to become "stuck" on a single output value for a long period of time. It can be considered as an update of the "stuck test" that was previously required for random number generators within FIPS-approved cryptographic modules. Note that this test is intended to detect a total failure of the noise source. Given the assessed min-entropy \(H\) of a noise source, the probability⁹ of that source generating \(n\) identical samples consecutively is at most \(2^{-H(n-1)}\). The test declares an error if a sample is repeated \(C\) or more times. The cutoff value \(C\) is determined by the acceptable false-positive probability \(\alpha\) and the entropy estimate \(H\) using the following formula

⁹ This probability can be obtained as follows. Let a random variable take possible values with probabilities \(p_i\), for \(i=1,..,k\), where \(p_1 \ge p_2 \ge \ldots \ge p_k\). Then, the probability of producing any \(C\) identical consecutive samples is \(\sum p_i^C\). Since, \(\sum p_i^C\) is less than or equal to \(p_1 . p_1^{C-1} + p_2 . p_1^{C-1} + \ldots + p_k . p_1^{C-1} = (p_1 + \ldots + p_k)\, p_1^{C-1} = p_1^{C-1} = 2^{-H(C-1)}\).

This value of \(C\) is the smallest integer satisfying the inequality \(\alpha \ge 2^{-H(C-1)}\), which ensures that the probability of obtaining a sequence of identical values from \(C\) consecutive noise source samples is at most \(\alpha\). For example, for \(\alpha = 2^{-20}\), an entropy source with \(H = 2.0\) bits per sample would have a repetition count test cutoff value of \(1 + \lceil 20/2.0 \rceil = 11\). Let \(\mathit{next}()\) yield the next sample from the noise source. Given a continuous sequence of noise source samples, and the cutoff value \(C\), the repetition count test is performed as follows:

1. \(\mathrm{A} = \mathit{next}()\)

2. \(B = 1\)

3. \(X = \mathit{next}()\)

4. If (\(X = \mathrm{A}\)),

\(B = B + 1\)

If (\(B \ge C\)), signal a failure. else:

\(A = X\)

\(B = 1\)

This test's cutoff value can be applied to any entropy estimate, \(H\), including very small and very large estimates. However, it is important to note that this test is not very powerful – it is able to detect only catastrophic failures of a noise source. For example, a noise source evaluated at eight bits of min-entropy per sample has a cutoff value of six repetitions to ensure a false-positive rate of approximately once per \(10^{12}\) samples generated. If that noise source somehow failed to the point that each sample had a \(1/16\) probability of being the same as the previous sample, so that it was providing only four bits of min-entropy per sample, it would still be expected to take about one million samples before the repetition count test would notice the problem.

The Adaptive Proportion Test is designed to detect a large loss of entropy that might occur as a result of some physical failure or environmental change affecting the noise source. The test continuously measures the local frequency of occurrence of a sample value in a sequence of noise source samples to determine if the sample occurs too frequently. Thus, the test is able to detect when some value begins to occur much more frequently than expected, given the source's assessed entropy per sample. Note that this test is intended to detect more subtle failures of the noise source, rather than the kind of total failure detected by the Repetition Count Test. The test takes a sample from the noise source, and then counts the number of times that the same value occurs within the next \(W-1\) samples. If that count reaches the cutoff value \(C\), the test declares an error. The window size \(W\) is selected based on the alphabet size, and shall be assigned to 1024 if the noise source is binary (that is, the noise source produces only two distinct values) and 512 if the noise source is not binary (that is, the noise source produces more than two distinct values).

Let \(\mathit{next}()\) yield the next sample from the noise source. Given a continuous sequence of noise samples, the cutoff value \(C\) and the window size \(W\), the adaptive proportion test is performed as follows:

1. \(\mathrm{A} = \mathit{next}()\)

2. \(B = 1\).

3. For \(i = 1\) to \(W-1\)
If (\(\mathrm{A} = \mathrm{next}()\)) \(B = B + 1\)
If (\(B \ge C\)) signal a failure

The cutoff value \(C\) is chosen such that the probability of observing \(C\) or more identical samples in a window size of \(W\) is at most \(\alpha\). Mathematically, \(C\) satisfies the following equation¹⁰:

For binary sources, the developer is allowed to extend the test by also checking that \(\mathrm{W} - B \ge C\), which would guarantee that a binary value occurring too frequently will be caught on the first test window.

For noise sources where the alphabet size is large (e.g., greater than 256), the submitter may reduce the alphabet size to a lower value, using the method described in Section 6.4.

The following table gives example cutoff values for various min-entropy estimates per sample and window sizes with \(\alpha = 2^{-20}\).

¹⁰ This probability can be computed using widely-available spreadsheet applications. In Microsoft Excel, Open Office Calc,and iWork Numbers, the calculation is done with the function =CRITBINOM(). For example, in Microsoft Excel, \(C\) would be computed as =1+CRITBINOM(W, power(2,( −H)),1−\(\alpha\)).

For concreteness, these are the criteria that are required for any alternative continuous health tests:
a. If a single value appears more than \(\lceil 100/H \rceil\) consecutive times in a row in the sequence of noise source samples, the test shall detect this with a probability of at least 99 %.
b. Let \(P = 2^{-H}\). If the noise source's behavior changes so that the probability of observing a specific sample value increases to at least \(P^{*} = 2^{-H/2}\), then the test shall detect this change with a probability of at least 50 % when examining 50 000 consecutive samples from this degraded source.
The use of one or more of the approved continuous health test described in Section 4.4 can be avoided by providing convincing evidence that the failure being considered will be reliably detected by the developer-defined continuous tests. This evidence may be a proof or the results of statistical simulations.

This section includes statistical tests that are designed to find evidence that the samples are not IID and if no evidence is found that the samples are non-IID, then it is assumed that the samples are IID (see Section 3.1.2). These tests take the sequence \(S = (s_1,\ldots,s_L)\), where \(s_i \in A = \{x_1,\ldots,x_k\}\), as input, and test the hypothesis that the values in \(S\) are IID. If the hypothesis is rejected by any of the tests, the values in \(S\) are assumed to be non-IID.

Input: \(S = (s_1,\ldots,s_L)\)
Output: Decision on the IID assumption
1. For each test \(i\)
1.1. Assign the counters \(C_{i,0}\) and \(C_{i,1}\) to zero.
1.2. Calculate the test statistic \(T_i\) on \(S\).
2. For \(j = 1\) to 10 000
2.1. Permute \(S\) using the Fisher-Yates shuffle algorithm.
2.2. For each test \(i\)
2.2.1. Calculate the test statistic \(T\) on the permuted data.
2.2.2. If (\(T > T_i\)), increment \(C_{i,0}\). If (\(T = T_i\)), increment \(C_{i,1}\).
3. If (\((C_{i,0}+C_{i,1} \le 5)\) or \((C_{i,0} \ge 9995)\)) for any \(i\), reject the IID assumption; else, assume that the noise source outputs are IID.

If the samples are IID, permuting the dataset is not expected to change the value of the test statistics significantly. In particular, the original dataset and permuted datasets are expected to be drawn from the same distribution; therefore, their test statistics should be similar. Unusually high or low test statistics are expected to occur infrequently. However, if the samples are not IID, then the original and permuted test statistics may be significantly different. The counters \(C_{i,0}\) and \(C_{i,1}\) are used to find the ranking of the original test statistics among the permuted test statistics (i.e., where a statistic for the original dataset fits within an ordered list of the permuted datasets). Extreme values for the counters suggest that the data samples are not IID. If the sum of \(C_{i,0}\) and \(C_{i,1}\) is less than 5, it means that the original test statistic has a very high rank; conversely, if \(C_{i,0}\) is greater than 9995, it means that the original test statistics has a very low rank. The cutoff values for \(C_{i,0}\) and \(C_{i,1}\) are calculated using a type I error probability of 0.001.

Input: \(S = (s_1,\ldots,s_L)\)
Output: Shuffled \(S = (s_1,\ldots,s_L)\)
1. for \(i\) from \(L\) downto 1 do
a. Generate a random integer \(j\) such that \(1 \le j \le i\).
b. Swap \(s_j\) and \(s_i\)

The tests are applicable to both binary and non-binary data, but for some of the tests, the number of distinct sample values, denoted \(k\) (the size of the set \(A\)), significantly affects the distribution of the test statistics, and thus the type I error. For such tests, one of the following conversions is applied to the input data, when the input is binary, i.e., \(k = 2\).

The excursion test statistic measures how far the running sum of sample values deviates from its average value at each point in the dataset. Given \(S = (s_1,\ldots,s_L)\), the test statistic \(T\) is the largest deviation from the average and is calculated as follows:

1. Calculate the average of the sample values, i.e., \(\bar{X} = (s_1 + s_2 + \ldots + s_L) / L\)

2. For \(i = 1\) to \(L\)

Calculate \(d_i = \left| \sum_{j=1}^{i} s_j - i \times \bar{X} \right|\).

3. \(T = \max(d_1, \ldots, d_L)\).

Example 1: Let the input sequence be \(S = (2, 15, 4, 10, 9)\). The average of the sample values is 8, and \(d_1 = |2 - 8| = 6\); \(d_2 = |(2+15) - (2 \times 8)| = 1\); \(d_3 = |(2+15+4) - (3 \times 8)| = 3\); \(d_4 = |(2+15+4+10) - (4 \times 8)| = 1\); and \(d_5 = |(2+15+4+10+9) - (5 \times 8)| = 0\). Then, \(T = \max(6, 1, 3, 1, 0) = 6\).

This test statistic determines the number of runs constructed using the relations between consecutive samples. Given \(S = (s_1, \ldots, s_L)\), the test statistic \(T\) is calculated as follows:

1. Construct the sequence \(S' = (s'_1, \ldots, s'_{L-1})\), where

for \(i = 1, \ldots, L-1\).

2. The test statistic \(T\) is the number of runs in \(S'\).

Example 2: Let the input sequence be \(S = (2, 2, 2, 5, 7, 7, 9, 3, 1, 4, 4)\); then \(S' = (+1, +1, +1, +1, +1, +1, -1, -1, +1, +1)\). There are three runs: \((+1, +1, +1, +1, +1, +1)\), \((-1, -1)\) and \((+1, +1)\), so \(T = 3\).

This test statistic determines the length of the longest run constructed using the relations between consecutive samples. Given \(S = (s_1, \ldots, s_L)\), the test statistic \(T\) is calculated as follows:

1. Construct the sequence \(S' = (s'_1, \ldots, s'_{L-1})\), where

for \(i = 1, \ldots, L-1\).

2. The test statistic \(T\) is the length of the longest run in \(S'\).

Example 3: Let the input sequence be \(S = (2, 2, 2, 5, 7, 7, 9, 3, 1, 4, 4)\); then \(\mathrm{S}' = (+1, +1, +1, +1, +1, +1, -1, -1, +1, +1)\). There are three runs: \((+1, +1, +1, +1, +1, +1)\), \((-1, -1)\) and \((+1, +1)\), so \(T = 6\).

This test statistic determines the maximum number of increases or decreases between consecutive sample values. Given \(S = (s_1, \ldots, s_L)\), the test statistic \(T\) is calculated as follows:

1. Construct the sequence \(S' = (s'_1, \ldots, s'_{L-1})\), where

for \(i = 1, \ldots, L-1\).

2. Calculate the number of \(-1\)’s and \(+1\)’s in \(S'\); the test statistic \(T\) is the maximum of these numbers, i.e., \(T = \max(\text{number of } -1\text{’s}, \text{number of } +1\text{’s})\).

Example 4: Let the input sequence be \(S = (2, 2, 2, 5, 7, 7, 9, 3, 1, 4, 4)\); then \(S' = (+1, +1, +1, +1, +1, +1, -1, -1, +1, +1)\). There are eight \(+1\)’s and two \(-1\)’s in \(\mathrm{S}'\), so \(T = \max(\text{number of } +1\text{s}, \text{number of } -1\text{s}) = \max(8, 2) = 8\).

This test statistic determines the number of runs that are constructed with respect to the median of the input data. Given \(S = (s_1, \ldots, s_L)\), the test statistic \(T\) is calculated as follows:

1. Find the median \(\tilde{X}\) of \(S = (s_1, \ldots, s_L)\).

2. Construct the sequence \(S' = (s'_1, \ldots, s'_L)\) where

for \(i = 1, \ldots, L\).

3. The test statistic \(T\) is the number of runs in \(S'\).

Example 5: Let the input sequence be \(S = (5, 15, 12, 1, 13, 9, 4)\). The median of the input sequence is 9. Then, \(S' = (-1, +1, +1, -1, +1, +1, -1)\). The runs are \((-1)\), \((+1, +1)\), \((-1)\), \((+1, +1)\), and \((-1)\). There are five runs, hence \(T = 5\).

1. Find the median \(\tilde{X}\) of \(S = (s_1, \ldots, s_L)\).

2. Construct a temporary sequence \(S' = (s'_1, \ldots, s'_L)\) from the input sequence \(S = (s_1, \ldots, s_L)\), as

for \(i = 1, \ldots, L\).

3. The test statistic \(T\) is the length of the longest run in \(S'\).

Example 6: Let the input sequence be \(S = (5, 15, 12, 1, 13, 9, 4)\). The median for this data subset is 9. Then, \(S' = (-1, +1, +1, -1, +1, +1, -1)\). The runs are \((-1)\), \((+1, +1)\), \((-1)\), \((+1, +1)\), and \((-1)\). The longest run has a length of 2; hence, \(T = 2\).

1. Let \(C\) be a list of the number of the samples observed to find two occurrences of the same value in the input sequence \(S = (s_1, \ldots, s_L)\). \(C\) is initially empty.

2. Let \(i = 1\).
3. While \(i < L\)
a. Find the smallest \(j\) such that \((s_i, \ldots, s_{i+j-1})\) contains two identical values. If no such \(j\) exists, break out of the while loop.
b. Add \(j\) to the list \(C\).
c. \(i = i + j\).
4. The test statistic \(T\) is the average of all values in the list \(C\).

Example 7: Let the input sequence be \(S = (2, 1, 1, 2, 0, 1, 0, 1, 1, 2)\). The first collision occurs for \(j = 3\), since the second and third values are the same. 3 is added to the list \(C\). Then, the first three samples are discarded, and the next sequence to be examined is \((2, 0, 1, 0, 1, 1, 2)\). The collision occurs for \(j = 4\). The third sequence to be examined is \((1,1,2)\), and the collision occurs for \(j = 2\). There are no collisions in the final sequence \((2)\). Hence, \(C = [3,4,2]\). The average of the values in \(C\) is \(T = 3\).

1. Let \(C\) be a list of the number of samples observed to find two occurrences of the same value in the input sequence \(S = (s_1, \ldots, s_L)\). \(C\) is initially empty.

2. Let \(i = 1\).

3. While \(i < L\)

a. Find the smallest \(j\) such that \((s_i, \ldots, s_{i+j-1})\) contains two identical values. If no such \(j\) exists, break out of the while loop.
b. Add \(j\) to the list \(C\).
c. \(i = i + j\).

4. The test statistic \(T\) is the maximum value in the list \(C\).

Example 8: Let the input data be \((2, 1, 1, 2, 0, 1, 0, 1, 1, 2)\). \(C = [3,4,2]\) is computed as in Example 7. \(T = \max(3,4,2) = 4\).

The periodicity test aims to determine the number of periodic structures in the data. The test takes a lag parameter \(p\) as input, where \(p < L\), and the test statistic \(T\) is calculated as follows:

1. Initialize \(T\) to zero.

2. For \(i = 1\) to \(L - p\)

If \((s_i = s_{i+p})\), increment \(T\) by one.

Example 9: Let the input data be \((2, 1, 2, 1, 0, 1, 0, 1, 1, 2)\), and let \(p = 2\). Since \(s_i = s_{i+p}\) for five values of \(i\) (1, 2, 4, 5 and 6), \(T = 5\).

The test is repeated for five different values of \(p\): 1, 2, 8, 16, and 32.

The covariance test measures the strength of the lagged correlation. The test takes a lag value \(p < L\) as input. The test statistic is calculated as follows:

1. Initialize \(T\) to zero.

2. For \(i = 1\) to \(L - p\)

\(T = T + (s_i \times s_{i+p})\).

Example 10: Let the input data be \((5, 2, 6, 10, 12, 3, 1)\), and let \(p\) be 2. \(T\) is calculated as \((5 \times 6) + (2 \times 10) + (6 \times 12) + (10 \times 3) + (12 \times 1) = 164\).

The test is repeated for five different values of \(p\): 1, 2, 8, 16, and 32.

1. Encode the input data as a character string containing a list of values separated by a single space, e.g., “\(S = (144, 21, 139, 0, 0, 15)\)” becomes “144 21 139 0 0 15”.

3. \(T\) is the length of the compressed string, in bytes.

Given the input \(S = (s_1, \ldots, s_L)\), where \(s_i \in A = \{x_1, \ldots, x_k\}\), the following steps are initially performed to determine the number of bins \(n_{\mathit{bin}}\) needed for the chi-square tests.

1. Find the proportion \(p_i\) of each \(x_i\) in \(S\), i.e., \(p_i = \frac{\text{number of } x_i \text{ in } S}{L}\). Calculate the expected number of occurrences of each possible pair \((z_i, z_j)\) in \(S\), as \(e_{i,j} = p_i p_j L/2\).

2. Allocate the possible \((z_i, z_j)\) pairs, starting from the smallest \(e_{i,j}\), into bins such that the expected value of each bin is at least five. The expected value of a bin is equal to the sum of the \(e_{i,j}\) values of the pairs that are included in the bin. After allocating all pairs, if the expected value of the last bin is less than five, merge the last two bins. Let \(n_{\mathit{bin}}\) be the number of bins constructed using this procedure.

1. Let \(o\) be a list of \(n_{\mathit{bin}}\) counts, each initialized to 0. For \(j = 1\) to \(L-1\):
a. If the pair \((s_j, s_{j+1})\) is in bin \(i\), increment \(o_i\) by 1.
b. Let \(j = j+2\).

2. The test statistic is calculated as \(T = \sum_{i=1}^{n_{\mathit{bin}}} \frac{(o_i - E(\mathit{Bin}_i))^2}{E(\mathit{Bin}_i)}\). The test fails if \(T\) is greater than the critical value of the Chi-square test statistic with \((n_{\mathit{bin}} - 1) - (k - 1) = n_{\mathit{bin}} - k\) degrees of freedom when the probability of type I error is chosen as 0.001. If the value of degrees of freedom is less than one, do not apply the test.

Example 11: Let \(S\) be (2, 2, 3, 1, 3, 2, 3, 2, 1, 3, 1, 1, 2, 3, 1, 1, 2, 2, 2, 3, 3, 2, 3, 2, 3, 1, 2, 2, 3, 3, 2, 2, 2, 1, 3, 3, 3, 2, 3, 2, 1, 3, 2, 3, 1, 2, 2, 3, 1, 1, 3, 2, 3, 2, 3, 1, 2, 2, 3, 3, 2, 2, 2, 1, 3, 3, 3, 2, 3, 2, 1, 2, 2, 3, 3, 3, 2, 3, 2, 1, 2, 2, 2, 1, 3, 3, 3, 2, 3, 2, 1, 3, 2, 3, 1, 2, 2, 3, 1, 1). The alphabet consists of \(k = 3\) values {1, 2, 3}; and \(p_1\), \(p_2\), and \(p_3\) are 0.21, 0.41 and 0.38, respectively. With \(L = 100\), the sorted expected values are calculated as:

The pairs can be allocated into \(n_{\mathit{bin}} = 6\) bins.

The test checks whether the distribution of samples is identical for different parts of the input. Given the input \(S = (s_1, \ldots, s_L)\), where \(s_i \in A = \{x_1, \ldots, x_k\}\), perform the following steps to calculate the number of bins \(n_{\mathit{bin}}\) for the test.

1. Let \(c_i\) be the number of occurrences of \(x_i\) in the entire dataset \(S\), and let \(e_i = c_i/10\), for \(1 \le i \le k\). Note that \(c_i\) is divided by ten because \(S\) will be partitioned into ten data subsets.

2. Let \(\mathit{List}[i]\) be the sample value with the \(i^{\text{th}}\) smallest \(e_i\) (e.g., \(\mathit{List}[1]\) has the smallest value for \(e_i\); \(\mathit{List}[2]\) has the next smallest value, etc.)

3. Starting from \(\mathit{List}[1]\), allocate the sample values into bins. Assign consecutive \(\mathit{List}[i]\) values to a bin until the sum of the \(e_i\) for those binned items is at least five, then begin assigning the following \(\mathit{List}[i]\) value(s) to the next bin. If the expected value of the last bin is less than five, merge the last two bins. Let \(n_{\mathit{bin}}\) be the number of bins constructed after this procedure.

4. Let \(E_i\) be the expected number of sample values in Bin \(i\); \(E_i\) is the sum of the \(e_i\) for the listed items in that bin. For example, if Bin 1 contains (\(x_1\), \(x_{10}\) and \(x_{50}\)), then \(E_1 = e_1 + e_{10} + e_{50}\).

Example 12: Let the number of distinct sample values \(k\) be 4; and let \(c_1 = 43\), \(c_2 = 55\), \(c_3 = 52\) and \(c_4 = 10\). After partitioning the entire input sequence into 10 parts, the expected value of each sample becomes \(e_1 = 4.3\), \(e_2 = 5.5\), \(e_3 = 5.2\) and \(e_4 = 1\). The sample list starting with the smallest expected value is formed as \(\mathrm{List} = [4, 1, 3, 2]\). The first bin contains sample 4 and 1, and the expected value of Bin 1 becomes 5.3 (\(= e_4 + e_1\)). The second bin contains sample 3, and the last bin contains sample 2. Since the expected value of the last bin is greater than five, no additional merging is necessary.

Given \(n_{\mathit{bin}}\), \(E_i\) and list of samples for each bin, the chi-square goodness-of-fit test is executed as follows:

1. Partition \(S\) into ten non-overlapping sequences of length \(\left\lfloor \frac{L}{10} \right\rfloor\), where \(S_d = (s_{d\lfloor L/10\rfloor+1}, \ldots, s_{(d+1)\lfloor L/10\rfloor})\) for \(d = 0, \ldots, 9\). If \(L\) is not a multiple of 10, the remaining samples are not used.

2. \(T = 0\).

3. For \(d = 0\) to \(9\)

3.1. For \(i = 1\) to \(n_{\mathit{bin}}\)

3.1.1. Let \(o_i\) be the total number of times the samples in Bin \(i\) appear in \(S_d\).

3.1.2. \(T = T + \frac{(o_i - E_i)^2}{E_i}\).

The test fails if the test statistic \(T\) is greater than the critical value of chi-square with \(9(n_{\mathit{bin}} - 1)\) degrees of freedom when the type I error is chosen as 0.001.

Given the input binary data \(S = (s_1, \ldots, s_L)\), the length of the tuples, \(m\), is determined as follows:

1. Let \(p_0\) and \(p_1\) be the proportion of zeroes and ones in \(S\), respectively, i.e., \(p_0 = \frac{\#\text{ 0's in }S}{L}\), and \(p_1 = \frac{\#\text{ 1's in }S}{L}\).

2. Find the maximum integer \(m\) such that \(\min(p_0, p_1)^m \left\lfloor \frac{L}{m} \right\rfloor \ge 5\). If \(m\) is greater than 11, set \(m = 11\). If \(m\) is 1, the test fails. For example, for \(p_0 = 0.14\), \(p_1 = 0.86\), and \(L = 1000\), \(m = 2\).

The test is applied if \(m \ge 2\).

1. Initialize \(T\) to 0.

2. Partition \(S\) into non-overlapping \(m\)-bit blocks, denoted as \(B = (B_1, \ldots, B_{\lfloor L/m \rfloor})\). If \(L\) is not a multiple of \(m\), discard the remaining bits.

3. For each possible \(m\)-bit tuple \((a_1, a_2, \ldots, a_m)\)

a. Let \(o\) be the number of times that the pattern \((a_1, a_2, \ldots, a_m)\) occurs in the input \(B\).

b. Let \(w\) be the number of ones in \((a_1, a_2, \ldots, a_m)\).

c. Let \(e = p_1^{w} (p_0)^{m-w} \left\lfloor \frac{L}{m} \right\rfloor\).

d. \(T = T + \frac{(o - e)^2}{e}\).

The test fails if the test statistic \(T\) is greater than the critical value of chi-square with \(2^m - 2\) degrees

This test checks the distribution of the number of ones in non-overlapping intervals of the input data to determine whether the distribution of the ones remains the same throughout the sequence. Given the input binary data \(S = (s_1, \ldots, s_L)\), the test description is as follows:

1. Let \(p\) be the proportion of ones in the entire sequence \(S\), i.e., \(p = (\text{the number of ones in } S)/L\).

2. Partition \(S\) into ten non-overlapping subsets of length \(\left\lfloor \frac{L}{10} \right\rfloor\), where \(S_d = (s_{d\lfloor L/10\rfloor+1}, \ldots, s_{(d+1)\lfloor L/10\rfloor})\) for \(d = 0, \ldots, 9\). If \(L\) is not a multiple of 10, the remaining bits are discarded.

3. Initialize \(T\) to 0.

4. Let the expected number of zeros and ones in each sub-sequence \(S_d\) be

5. For \(d = 0\) to 9

a. Let \(o_0\) and \(o_1\) be the number of zeros and ones in \(S_d\), respectively.

b. \(T = T + \frac{(o_0 - e_0)^2}{e_0} + \frac{(o_1 - e_1)^2}{e_1}\).

\(T\) is a chi-square random variable with nine degrees of freedom. The test fails if \(T\) is larger than the critical value at 0.001, which is 27.887.

Given the input \(S = (s_1, \ldots, s_L)\), where \(s_i \in A = \{x_1, \ldots, x_k\}\),

1. Find the proportion \(p_i\) of each possible input value \(x_i\) in \(S\), i.e., \(p_i = \frac{\text{number of } x_i \text{ in } S}{L}\).

2. Calculate the collision probability as \(p_{\mathit{col}} = \sum_{i=1}^{k} p_i^2\).

3. Find the length of the longest repeated substring \(W\), i.e., find the largest \(W\) such that, for at least one \(i \ne j\), \(s_i = s_j\), \(s_{i+1} = s_{j+1}\), ... , \(s_{i+W-1} = s_{j+W-1}\).

4. The number of overlapping subsequences of length \(W\) in \(S\) is \(L - W + 1\), and the number of pairs of overlapping subsequences is \(\binom{L - W + 1}{2}\).

5. Let \(X\) be a binomially distributed random variable with parameters \(N = \binom{L-W+1}{2}\) and a probability of success \(p_{\mathit{col}}^{W}\). Calculate the probability that \(X\) is greater than or equal to 1, i.e., \(\Pr(X \ge 1) = 1 - \Pr(X = 0) = 1 - (1 - p_{\mathit{col}}^{W})^{N}\).

The test fails if \(\Pr(X \ge 1)\) is less than 0.001.

Each estimator takes a sequence \(S = (s_1, \ldots, s_L)\) as its input, where each \(s_i\) comes from an output space \(A = \{x_1, \ldots, x_k\}\) that is specified by the submitter. The estimators presented in this Recommendation follow a variety of strategies, which cover a range of assumptions about the data. For further information about the theory and origins of these estimators, see Appendix G. The estimators that are to be applied to a sequence depend on whether the data has been determined to be IID or non-IID. For IID data, the min-entropy estimation is determined as specified in Section 6.1, whereas for non-IID data, the procedures in Section 6.2 are used.

¹¹ However, it is possible for this estimate to slightly underestimate the true min-entropy. It is believed that this underestimation is likely to not exceed one bit because of the relationship between min-entropy and the expected guessing work derived in Appendix D. Of course, such an underestimate would not indicate that a guessing attack that ignores dependencies could be less costly than one that takes the dependencies into account. As an example, consider a data sample consisting of pairs of bytes generated from the joint distribution on two bytes \(\mathrm{X}\) and \(\mathrm{Y}\), each having possible values \(\mathrm{A}\) and \(\mathrm{B}\), where \(\Pr(\mathrm{X}=\mathrm{A},\mathrm{Y}=\mathrm{A})=0.104\), \(\Pr(\mathrm{X}=\mathrm{A},\mathrm{Y}=\mathrm{B})=0.332\), \(\Pr(\mathrm{X}=\mathrm{B},\mathrm{Y}=\mathrm{A})=0.239\), and \(\Pr(\mathrm{X}=\mathrm{B},\mathrm{Y}=\mathrm{B})=0.325\). The min-entropy according to the MCV estimator is 0.712, while the true min-entropy is 0.795.

This method first finds the proportion \(\hat{p}\) of the most common value in the input dataset, and then constructs a confidence interval for this proportion. The upper bound of the confidence interval is used to estimate the min-entropy per sample of the source.

Given the input \(S = (s_1, \ldots, s_L)\), where \(s_i \in A = \{x_1, \ldots, x_k\}\),

1. Find the proportion of the most common value \(\hat{p}\) in the dataset, i.e.,

2. Calculate an upper bound on the probability of the most common value \(p_u\) as

where 2.576 corresponds to the \(Z_{(1-0.005)}\) value.

3. The estimated min-entropy is \(-\log_2(p_u)\).

Example: If the dataset is \(S = (0, 1, 1, 2, 0, 1, 2, 2, 0, 1, 0, 1, 1, 0, 2, 2, 1, 0, 2, 1)\), with \(L = 20\), the most common value is 1, with \(\hat{p} = 0.4\). \(p_u = 0.4 + 2.576\sqrt{0.012} = 0.6895\). The min-entropy estimate is \(-\log_2(0.6822) = 0.5363\).

Given the input \(S = (s_1, \ldots, s_L)\), where \(s_i \in A = \{0,1\}\),

1. Set \(v = 0\), \(\mathit{index} = 1\).

2. Beginning with \(s_{\mathit{index}}\), step through the input until any observed value is repeated; i.e., find the smallest \(j\) such that \(s_i = s_j\), for some \(i\) with \(\mathit{index} \le i < j\).

3. Set \(v = v + 1\), \(t_v = j - \mathit{index} + 1\) and \(\mathit{index} = j + 1\).

5. Calculate the sample mean \(\bar{X}\), and the sample standard deviation \(\hat{\sigma}\), of \(t_i\) as

6. Compute the lower-bound of the confidence interval for the mean, based on a normal distribution with a confidence level of 99 %,

7. Using a binary search, solve for the parameter \(p\), such that

and \(\Gamma(a, b)\) is the incomplete Gamma function defined as

\(\int_{b}^{\infty} t^{a-1}e^{-t}\,dt\). An efficient implementation of \(F(1/z)\) is provided in Appendix G.1.1. The bounds of the binary search should be 1/2 and 1.

8. If the binary search yields a solution, then the min-entropy estimation is the negative logarithm of the parameter, \(p\):

Example: Suppose that \(S = (1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0)\). The collisions of the sequence are \((1, 0, 0)\), \((0, 1, 1)\), \((1, 0, 0)\), \((1, 0, 1)\), \((0, 1, 0)\), \((1, 1)\), \((1, 0, 0)\), \((1, 1)\), \((0, 0)\), \((0, 1, 1)\), \((1, 0, 0)\), \((1, 0, 1)\), \((0, 1, 0)\), \((1, 1)\). After step 5, \(v = 14\), and the sequence \((t_1, \ldots\ t_v)\) is \((3, 3, 3, 3, 3, 2, 3, 2, 2, 3, 3, 3, 3, 2)\). Then \(\bar{X} = 2.7143\), \(\hat{\sigma} = 0.4688\), and \(\bar{X}' = 2.3915\). The solution to the equation is \(p = 0.7329\), giving an estimated min-entropy of 0.4483.

In a first-order Markov process, the next sample value depends only on the latest observed sample value; in an \(n^{\mathrm{th}}\)-order Markov process, the next sample value depends only on the previous \(n\) observed values. Therefore, a Markov model can be used as a template for testing sources with dependencies. The Markov estimate provides a min-entropy estimate by measuring the dependencies between consecutive values from the input dataset. The min-entropy estimate is based on the entropy present in any subsequence (i.e., chain) of outputs, instead of an estimate of the min-entropy per output.

Samples are collected from the noise source, and specified as \(d\)-long chains of samples. From this data, probabilities are determined for both the initial state and transitions between any two states. These probabilities are used to determine the highest probability of any particular \(d\)-long chain of samples. The corresponding maximum probability is used to determine the min-entropy present in all such chains generated by the noise source. This min-entropy value is particular to \(d\)-long chains and cannot be extrapolated linearly; i.e., chains of length \(wd\) will not necessarily have \(w\) times as much min-entropy present as a \(d\)-long chain. It may not be possible to know what a typical output length will be at the time of testing. Therefore, although not mathematically correct, in practice, calculating an entropy estimate per sample (extrapolated from that of the \(d\)-long chain) provides estimates that are close.

Given the input \(S = (s_1, \ldots, s_L)\), where \(s_i \in A = \{0,1\}\),

1. Estimate the initial probabilities for each output value, \(P_0 = \frac{\#\{0 \text{ in } S\}}{L}\) and \(P_1 = 1 - P_0\).

2. Let \(T\) be the \(2\times 2\) transition matrix of the form

4. Let \(\hat{p}_{\mathit{max}}\) be the maximum of the probabilities in the table given above. The min-entropy estimate is the negative logarithm of the probability of the most likely sequence of outputs, \(\hat{p}_{\mathit{max}}\):

Example: For the purpose of this example¹², suppose that, \(L = 40\) and \(S = (1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0)\). \(P_0 = 0.475\) and \(P_1 = 0.525\). The transition matrix is calculated as

¹² The test is designed for long sequences (i.e., \(\mathrm{L} \approx 1\,000\,000\)), for the purpose of the example, a very small value of \(L\) is used.

The resulting entropy estimate is \(\min(-\log_2(4.6288\times 10^{-30})/128, 1) = \min(0.761, 1) = 0.761\).

Given the input \(S = (s_1, \ldots, s_L)\), where \(s_i \in A = \{0,1\}\),

1. Let \(b = 6\). Create a new sequence, \(S' = (s'_1, \ldots, s'_{\lfloor L/b \rfloor})\), by dividing \(S\) into non-overlapping \(b\)-bit blocks. If \(L\) is not a multiple of \(b\), discard the extra data.

2. Partition the dataset, \(S'\), into two disjoint groups. These two groups will form the dictionary and the test data.

a. Create the dictionary from the first \(d = 1000\) elements of \(S'\), \((s'_1, \ldots, s'_d)\).

b. Use the remaining \(v = \lfloor L/b \rfloor - d\) observations, \((s'_{d+1}, \ldots, s'_{\lfloor L/b \rfloor})\), for testing.

3. Initialize the dictionary \(\mathit{dict}\) to an all zero array of size \(2^b\). For \(i\) from \(1\) to \(d\), let \(\mathit{dict}[s'_i] = i\). The value of \(\mathit{dict}[s'_i]\) is the index of the last occurrence of each \(s'_i\) in the dictionary.

4. Run the test data against the dictionary created in Step 2.
a. Let \(D\) be a list of length \(v\).

b. For \(i\) from \(d + 1\) to \(\lfloor L/b \rfloor\):

i. If \(\mathit{dict}[s'_i]\) is non-zero, then \(D_{i-d} = i - \mathit{dict}[s'_i]\). Update the dictionary with the index of the most recent observation, \(\mathit{dict}[s'_i] = i\).

ii. If \(\mathit{dict}[s_i]\) is zero, add that value to the dictionary, i.e., \(\mathit{dict}[s'_i] = i\). Let \(D_{i-d} = i\).

5. Calculate the sample mean, \(\bar{X}\), and sample standard deviation¹³, \(\hat{\sigma}\), of \((\log_2(D_1), \ldots, \log_2(D_v))\).

7. Using a binary search, solve for the parameter \(p\), such that the following equation is true:

¹³ Note that a correction factor is applied to the standard deviation, as described in [Mau92] and computed with higher accuracy in [CoNa98]. This correction factor reduces the standard deviation to account for dependencies in the \(D_i\) values.

The bounds of the binary search should be \(2^{-b}\) and 1.

8. If the binary search yields a solution, then the min-entropy is the negative logarithm of the parameter, \(p\):

Example: For illustrative purposes, suppose that \(d = 4\) (instead of 1000), \(L = 48\) and \(S\) = (1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1 ,1, 1, 0, 0, 0, 1, 1). After step 1, the new blocked sequence is \(S'\) = (100011, 100101, 010111, 001100, 011100, 101010, 111011, 100011). The dictionary sequence is (100011, 100101, 010111, 001100), and the testing sequence is (011100, 101010, 111011, 100011). \(v = 4\). After the dictionary is initialized in step 3, it has the following values (only non-zero values are shown):

After Step 4, the resulting \(D_1 = 5\), \(D_2 = 6\), \(D_3 = 7\), and \(D_4 = 7\). The values computed in step 5 are \(\bar{X} = 2.6304\) and \(\hat{\sigma} = 0.9074\), and the value for step 6 is \(\bar{X}' = 1.4617\). The value of \(p\) that solves the equation in step 7 is 0.5715, and the min-entropy estimate is 0.1345.

6.3.5 \(t\)-Tuple Estimate

This method examines the frequency of \(t\)-tuples (pairs, triples, etc.) that appears in the input dataset and produces an estimate of the entropy per sample, based on the frequency of those \(t\)-tuples. The frequency of the \(t\)-tuple \((r_1, r_2, \ldots, r_t)\) in \(S = (s_1, \ldots, s_L)\) is the number of \(i\)’s such that \(s_i = r_1\), \(s_{i+1} = r_2\), \(\ldots\), \(s_{i+t-1} = r_t\). It should be noted that the tuples can overlap.

Given the input \(S = (s_1, \ldots, s_L)\), where \(s_i \in A = \{x_1, \ldots, x_k\}\),

1. Find the largest \(t\) such that the number of occurrences of the most common \(t\)-tuple in \(S\) is at least 35.

2. Let \(Q[i]\) store the number of occurrences of the most common \(i\)-tuple in \(S\) for \(i = 1, \ldots, t\). For example, in \(S\)=(2, 2, 0, 1, 0, 2, 0, 1, 2, 1, 2, 0, 1, 2, 1, 0, 0, 1, 0, 0, 0), \(Q[1] = \max(\#0\text{’s},\#1\text{’s},\#2\text{’s}) = \#0\text{’s} = 9\), and \(Q[2] = 4\) is obtained by the number of the tuple 01 in \(S\).

3. For \(i = 1\) to \(t\), let \(\mathrm{P}[i] = Q[i] / (L-i+1)\), and compute an estimate on the maximum individual sample value probability as \(P_{\mathit{max}}[i] = P[i]^{1/i}\). Let \(\hat{p}_{\mathit{max}} = \max(P_{\mathit{max}}[1], \ldots, P_{\mathit{max}}[t])\).

4. Calculate an upper bound on the probability of the most common value \(p_u\) as

5. The entropy estimate is calculated as \(-\log_2(p_u)\).

Example: For the purpose of this example, suppose that the cutoff is 3 instead of 35 in step one. Suppose that \(S\) = (2, 2, 0, 1, 0, 2, 0, 1, 2, 1, 2, 0, 1, 2, 1, 0, 0, 1, 0, 0, 0), and \(L = 21\). The number of occurrences of the most common 4-tuple is 2, which falls below the threshold, and therefore \(t = 3\). In step 2, \(Q[1] = 9\), \(\mathrm{Q}[2] = 4\), and \(Q[3] = 3\). \(\mathrm{P}[1] = 0.4286\), \(\mathrm{P}[2] = 0.2\), \(\mathrm{P}[3] = 0.1579\). \(P_{\mathit{max}}[1] = 0.4286\), \(P_{\mathit{max}}[2] = 0.4472\), \(P_{\mathit{max}}[3] = 0.5405\), and \(\hat{p}_{\mathit{max}} = 0.5405\). The upper bound of a 99 % confidence interval is 0.8276. The min-entropy estimate is \(-\log_2(0.8276) = 0.273\).

This method estimates the collision entropy (sampling without replacement) of the source, based on the number of repeated substrings (tuples) within the input dataset. Although this method estimates collision entropy (an upper bound on min-entropy), this estimate handles tuple sizes that are too large for the \(t\)-tuple estimate, and is therefore a complementary estimate.

Given the input \(S = (s_1, \ldots, s_L)\), where \(s_i \in A = \{x_1, \ldots, x_k\}\),

1. Find the smallest \(u\) such that the number of occurrences of the most common \(u\)-tuple in \(S\) is less than 35.

2. Find the largest \(v\) such that the number of occurrences of the most common \(v\)-tuple in \(S\) is at least 2, and the most common \((v+1)\)-tuple in \(S\) occurs once. In other words, \(v\) is the largest length that a tuple repeat occurs. If \(v < u\), this estimate cannot be computed.

3. For \(W = u\) to \(v\), compute the estimated \(W\)-tuple collision probability

where \(C_i\) is the number of occurrences of the \(i^{\mathit{th}}\) unique \(W\)-tuple. Compute the estimated average collision probability per string symbol as \(P_{\mathit{max},W} = {P_W}^{1/W}\). Let \(\hat{p} = \max(P_{\mathit{max},u}, \ldots, P_{\mathit{max},v})\).

4. Calculate an upper bound on the probability of the most common value \(p_u\) as

5. The entropy estimate is calculated as \(-\log_2(p_u)\).

Example: For the purpose of this example, suppose that the cutoff is 3 instead of 35 in step 1. Suppose that \(S = (2, 2, 0, 1, 0, 2, 0, 1, 2, 1, 2, 0, 1, 2, 1, 0, 0, 1, 0, 0, 0)\), and \(L = 21\). In step 1, \(u\) is calculated as 4, as the frequency of the most common 4-tuple is 2. In step 2, \(v\) is calculated as 5. After step 3, \(P_4 = 0.0131\), \(P_5 = 0.0074\), \(P_{\mathit{max},4} = 0.3381\), \(P_{\mathit{max},5} = 0.3744\), and \(\hat{p} = \max(0.3381, 0.3744) = 0.3744\). After step 4, \(p_u = 0.6531\). The min-entropy estimate is \(-\log_2(0.6531) = 0.6146\).

The Multi Most Common in Window (MultiMCW) predictor contains several subpredictors, each of which aims to guess the next output, based on the last \(w\) outputs. Each subpredictor predicts the value that occurs most often in that window of \(w\) previous outputs. The MultiMCW predictor keeps a scoreboard that records the number of times that each subpredictor was correct, and uses the subpredictor with the most correct predictions to predict the next value. In the event of a tie, the most common sample value that has appeared most recently is predicted. This predictor was designed for cases where the most common value changes over time, but still remains relatively stationary over reasonable lengths of the sequence.

Given the input \(S = (s_1, \ldots, s_L)\), where \(s_i \in A = \{x_1, \ldots, x_k\}\),

1. Let window sizes be \(w_1 = 63\), \(w_2 = 255\), \(w_3 = 1023\), \(w_4 = 4095\), and \(N = L - w_1\). Let \(\mathit{correct}\) be an array of \(N\) Boolean values, each initialized to 0.

2. Let \(\mathit{scoreboard}\) be a list of four counters, each initialized to 0. Let \(\mathit{frequent}\) be a list of four values, each initialized to \(\mathit{Null}\). Let \(\mathit{winner} = 1\).

3. For \(i = w_1 + 1\) to \(L\):

a. For \(j = 1\) to 4,

i. If \(i > w_{\mathrm{j}}\), let \(\mathit{frequent}_{\mathrm{j}}\) be the most frequent value in \((s_{i-w_{\mathrm{j}}}, s_{i-w_{\mathrm{j}}+1}, \ldots, s_{i-1})\). If there is a tie, then the most frequent value that has appeared most recently is assigned to \(\mathit{frequent}_{\mathrm{j}}\).

ii. Else, let \(\mathit{frequent}_{\mathrm{j}} = \mathit{Null}\).

b. Let \(\mathit{prediction} = \mathit{frequent}_{\mathit{winner}}\).

c. If (\(\mathit{prediction} = s_i\)), let \(\mathit{correct}_{i-w_1} = 1\).

d. Update the \(\mathit{scoreboard}\). For \(j = 1\) to 4,
i. If (\(\mathit{frequent}_j = s_i\))

1. Let \(\mathit{scoreboard}_j = \mathit{scoreboard}_j + 1\)

2. If \(\mathit{scoreboard}_j \ge \mathit{scoreboard}_{\mathit{winner}}\), let \(\mathit{winner} = j\)

4. Let \(C\) be the number of ones in \(\mathit{correct}\).

5. Calculate the predictor’s global performance as \(P_{\mathit{global}} = \frac{C}{N}\). The upper bound of the 99 % confidence interval on \(P_{\mathit{global}}\), denoted \(P'_{\mathit{global}}\) is calculated as:

where 2.576 corresponds to the \(Z_{(1-0.005)}\) value.

6. Calculate the predictor’s local performance, based on the longest run of correct predictions. Let \(r\) be one greater than the length of the longest run of ones in \(\mathit{correct}\). Use a binary search to solve the following for \(P_{\mathit{local}}\):

where \(q = 1 - P_{\mathit{local}}\) and \(x = x_{10}\), derived by iterating the recurrence relation

for \(j\) from 1 to 10, and \(x_0 = 1\). Note that solving for \(P_{\mathit{local}}\) using the logarithm of these equations is robust against overflows. Table 3 given in Appendix G.2 provides some pre-calculated values of \(P_{\mathit{local}}\).

7. The min-entropy is the negative logarithm of the greater performance metric

Example: Suppose that \(S = (1, 2, 1, 0, 2, 1, 1, 2, 2, 0, 0, 0)\), so that \(L = 12\). For the purpose of this example, suppose that \(w_1 = 3\), \(w_2 = 5\), \(w_3 = 7\), \(w_4 = 9\) (instead of \(w_1 = 63\), \(w_2 = 255\), \(w_3 = 1023\), \(w_4 = 4095\)). Then \(N = 9\). In step 3, the values are as follows:

After all of the predictions are made, \(\mathit{correct} = (0, 0, 0, 1, 0, 1, 0, 0, 1)\). Then, \(P_{\mathit{global}} = 0.3333\), \(P'_{\mathit{global}} = 0.7627\), \(P_{\mathit{local}} = 0.036\), and the resulting min-entropy estimate is 0.3908.

Given the input \(S = (s_1, \ldots, s_L)\), where \(s_i \in A = \{x_1, \ldots, x_k\}\),

1. Let \(D = 128\), and \(N = L - 1\). Let \(\mathit{lag}\) be a list of \(D\) values, each initialized to \(\mathit{Null}\). Let \(\mathit{correct}\) be a list of \(N\) Boolean values, each initialized to 0.

2. Let \(\mathit{scoreboard}\) be a list of \(D\) counters, each initialized to 0. Let \(\mathit{winner} = 1\).

3. For \(i = 2\) to \(L\):

a. For \(d = 1\) to \(D\):

i. If (\(d < i\)), \(\mathit{lag}_d = s_{i-d}\),
ii. Else \(\mathit{lag}_d = \mathit{Null}\).
b. Let \(\mathit{prediction} = \mathit{lag}_{\mathit{winner}}\).

c. If (\(\mathit{prediction} = s_i\)) let \(\mathit{correct}_{i-1} = 1\).

d. Update the \(\mathit{scoreboard}\). For \(d = 1\) to \(D\):
i. If (\(\mathit{lag}_d = s_i\))

1. Let \(\mathit{scoreboard}_d = \mathit{scoreboard}_d + 1\).

2. If \(\mathit{scoreboard}_d \ge \mathit{scoreboard}_{\mathit{winner}}\), let \(\mathit{winner} = d\).

4. Let \(C\) be the number of ones in \(\mathit{correct}\).

5. Calculate the predictor’s global performance as \(P_{\mathit{global}} = \frac{C}{N}\). The upper bound of the 99 % confidence interval on \(P_{\mathit{global}}\), denoted \(P'_{\mathit{global}}\) is calculated as:

where 2.576 corresponds to the \(Z_{(1-0.005)}\) value.

6. Calculate the predictor’s local performance, based on the longest run of correct predictions. Let \(r\) be one greater than the length of the longest run of ones in \(\mathit{correct}\). Use a binary search to solve the following for \(P_{\mathit{local}}\):

where

and \(x = x_{10}\), derived by iterating the recurrence relation

for \(j\) from 1 to 10, and \(x_0 = 1\). Note that solving for \(P_{\mathit{local}}\) using the logarithm of these equations is robust against overflows. Table 3 in Appendix G.2 provides some pre-calculated values of \(P_{\mathit{local}}\).

7. The min-entropy is the negative logarithm of the greater performance metric

Example: Suppose that \(S = (2, 1, 3, 2, 1, 3, 1, 3, 1, 2)\), so that \(L = 10\) and \(N = 9\). For the purpose of this example, suppose that \(D = 3\) (instead of 128). The following table shows the values in step 3.

After all of the predictions are made, \(\mathit{correct} = (0, 0, 0, 1, 1, 0, 0, 0, 0)\). Then, \(P_{global} = 0.2222\), \(P'_{global} = 0.6008\), \(P_{local} = 0.1167\), and the resulting min-entropy estimate is 0.735.

The MultiMMC predictor is composed of multiple Markov Model with Counting (MMC) subpredictors. Each MMC predictor records the observed frequencies for transitions from one output to a subsequent output (rather than the probability of a transition, as in a typical Markov model), and makes a prediction, based on the most frequently observed transition from the current output. MultiMMC contains \(D\) MMC subpredictors running in parallel, one for each depth from 1 to \(D\). For example, the MMC with depth 1 creates a first-order model, while the MMC with depth \(D\) creates a \(D^{\text{th}}\)-order model. MultiMMC keeps a scoreboard that records the number of times that each MMC subpredictor was correct, and uses the subpredictor with the most correct predictions to predict the next value.

Given the input \(S = (s_1, \ldots, s_L)\), where \(s_i \in A = \{x_1, \ldots, x_k\}\),

1. Let \(D = 16\), and \(N = L - 2\). Let \(\mathit{subpredict}\) be a list of \(D\) values, each initialized to \(\mathit{Null}\). Let \(\mathit{correct}\) be an array of \(N\) values, each initialized to 0. Let \(\mathit{entries}\) be an array of \(D\) values, each initialized to 0, and let \(\mathit{maxEntries} = 100\,000\).

2. For \(d = 1\) to \(D\), let \(M_d\) be a set of counters, where \(M_d[x, y]\) denotes the number of observed transitions from output \(x\) to output \(y\) for the \(d^{\mathit{th}}\)-order MMC.

3. Let \(\mathit{scoreboard}\) be a list of \(D\) counters, each initialized to 0. Let \(\mathit{winner} = 1\).

4. For \(i = 3\) to \(L\):

a. For \(d = 1\) to \(D\):
i. If \(d < i - 1\):

1. If \([(s_{i-d-1}, \ldots, s_{i-2}), s_{i-1}]\) is in \(M_d\), increment \(M_d[(s_{i-d-1}, \ldots, s_{i-2}), s_{i-1}]\) by 1.

2. Else if \(\mathit{entries}_d < \mathit{maxEntries}\), add a counter for \([(s_{i-d-1}, \ldots, s_{i-2}), s_{i-1}]\) to the set, let \(M_d[(s_{i-d-1}, \ldots, s_{i-2}), s_{i-1}] = 1\) and increment \(\mathit{entries}_d\) by 1.

b. For \(d = 1\) to \(D\):

i. If \(d < i\), find the \(y\) value that corresponds to the highest \(M_d[(s_{i-d}, \ldots, s_{i-1}), y]\) value, and denote that \(y\) as \(\mathit{ymax}\). If there is a tie, let \(\mathit{ymax}\) be the greatest \(y\) in the tie. Let \(\mathit{subpredict}_d = \mathit{ymax}\). If all possible values of \(M_d[(s_{i-d}, \ldots, s_{i-1}), y]\) are 0, then let \(\mathit{subpredict}_d = \mathit{Null}\).

c. Let \(\mathit{prediction} = \mathit{subpredict}_{\mathit{winner}}\).

d. If (\(\mathit{prediction} = s_i\)), let \(\mathit{correct}_{i-2} = 1\).

e. Update the scoreboard. For \(d = 1\) to \(D\):
i. If (\(\mathit{subpredict}_d = s_i\))

1. Let \(\mathit{scoreboard}_d = \mathit{scoreboard}_d + 1\).

2. If \(\mathit{scoreboard}_d \ge \mathit{scoreboard}_{\mathit{winner}}\), let \(\mathit{winner} = d\).

5. Let \(C\) be the number of ones in \(\mathit{correct}\).

6. Calculate the predictor’s global performance as \(P_{\mathit{global}} = \frac{C}{N}\). The upper bound of the 99 % confidence interval on \(P_{\mathit{global}}\), denoted \(P'_{\mathit{global}}\) is calculated as:

where 2.576 corresponds to the \(Z_{(1-0.005)}\) value.

7. Calculate the predictor’s local performance, based on the longest run of correct predictions. Let \(r\) be one greater than the length of the longest run of ones in correct. Use a binary search to solve the following for \(P_{\mathit{local}}\):

where

and \(x = x_{10}\), derived by iterating the recurrence relation

for \(j\) from 1 to 10, and \(x_0 = 1\). Note that solving for \(P_{\mathit{local}}\) using the logarithm of these equations is robust against overflows. Table 3 in Appendix G.2 provides some pre-calculated values of \(P_{\mathit{local}}\).

8. The min-entropy is the negative logarithm of the greater performance metric

Example: Suppose that \(S = (2, 1, 3, 2, 1, 3, 1, 3, 1)\), so that \(L = 9\) and \(N = 7\). For the purpose of this example, further suppose that \(D = 3\) (instead of 16). After each iteration of step 4 is completed, the values are:

Let \(\{x \rightarrow y{:}c\}\) denote a nonzero count \(c\) for the transition from \(x\) to \(y\). Models \(M_1\), \(M_2\), and \(M_3\) are shown below after step 4a (the model update step) for each value of \(i\).

After the predictions are all made, \(\mathit{correct} = (0, 0, 1, 1, 0, 1, 0)\). Then, \(P_{\mathit{global}} = 0.4286\), \(P'_{\mathit{global}} = 0.9490\), \(P_{\mathit{local}} = 0.1307\), and the resulting min-entropy estimate is 0.0755.

The LZ78Y predictor is loosely based on LZ78 encoding with Bernstein's Yabba scheme [Sal07] for adding strings to the dictionary. The predictor keeps a dictionary of strings that have been added to the dictionary so far, and continues adding new strings to the dictionary until the dictionary has reached its maximum capacity. Each time that a sample is processed, every substring in the most recent \(B\) samples updates the dictionary or is added to the dictionary.

Given the input \(S = (s_1, \ldots, s_L)\), where \(s_i \in A = \{x_1, \ldots, x_k\}\),

1. Let \(B = 16\), and \(N = L - B - 1\). Let \(\mathit{correct}\) be an array of \(N\) Boolean values, each initialized to 0. Let \(\mathit{maxDictionarySize} = 65\,536\).
2. Let \(D\) be an empty dictionary. Let \(\mathit{dictionarySize} = 0\).
3. For \(i = B+2\) to \(L\):

a. For \(j = B\) down to 1:

i. If \((s_{i-j-1}, \ldots, s_{i-2})\) is not in \(D\), and \(\mathit{dictionarySize} < \mathit{maxDictionarySize}\):

1. Let \(D[s_{i-j-1}, \ldots, s_{i-2}]\) be added to the dictionary.

2. Let \(D[s_{i-j-1}, \ldots, s_{i-2}][s_{i-1}] = 0\).

3. \(\mathit{dictionarySize} = \mathit{dictionarySize} + 1\)

ii. If \((s_{i-j-1}, \ldots, s_{i-2})\) is in \(D\),

1. Let \(D[s_{i-j-1}, \ldots, s_{i-2}][s_{i-1}] = D[s_{i-j-1}, \ldots, s_{i-2}][s_{i-1}] + 1\).

b. Use the dictionary to predict the next value, \(s_i\). Let \(\mathit{prediction} = \mathit{Null}\), and let \(\mathit{maxcount} = 0\). For \(j = B\) down to 1:

i. Let \(\mathit{prev} = (s_{i-j}, \ldots s_{i-1})\).
ii. If \(\mathit{prev}\) is in the dictionary, find the \(y \in \{x_1, \ldots, x_k\}\) that has the highest \(D[\mathit{prev}][y]\) value. In the event of a tie, let the \(y\) be the symbol with the higher byte value. For example, if \(D[\mathrm{prev}][1]\) and \(D[\mathrm{prev}][5]\) both have the highest value, then \(y = 5\).
iii. If \(D[\mathit{prev}][y] > \mathit{maxcount}\):

1. \(\mathit{prediction} = y\).

2. \(\mathit{maxcount} = D[\mathit{prev}][y]\).

c. If (\(\mathit{prediction} = s_i\)), let \(\mathit{correct}_{i-B-1} = 1\).

4. Calculate the predictor’s global performance as \(P_{\mathit{global}} = \frac{C}{N}\). The upper bound of the 99 % confidence interval on \(P_{\mathit{global}}\), denoted \(P'_{\mathit{global}}\) is calculated as:

where 2.576 corresponds to the \(Z_{(1-0.005)}\) value.

5. Calculate the predictor’s local performance, based on the longest run of correct predictions. Let \(r\) be one greater than the length of the longest run of ones in \(\mathit{correct}\). Use a binary search to solve the following for \(P_{\mathit{local}}\):

where \(q = 1 - P_{\mathit{local}}\) and \(x = x_{10}\), derived by iterating the recurrence relation

for \(j\) from 1 to 10, and \(x_0 = 1\). Note that solving for \(P_{\mathit{local}}\) using the logarithm of these equations is robust against overflows. Table 3 given in Appendix G.2 provides some pre-calculated values of \(P_{\mathit{local}}\).

6. The min-entropy is the negative logarithm of the greater performance metric

Example: Suppose that \(S = (2, 1, 3, 2, 1, 3, 1, 3, 1, 2, 1, 3, 2)\), and \(L = 13\). For the purpose of this example, suppose that \(B = 4\) (instead of 16), then \(N = 8\).

After the predictions are all made, \(\mathit{correct} = (0, 0, 1, 1, 0, 1, 1, 0)\). Then, \(P_{\mathit{global}} = 0.5\), \(P'_{\mathit{global}} = 0.9868\), \(P_{\mathit{local}} = 0.1229\), and the resulting min-entropy estimate is 0.0191.

It is often the case that the data requirements for a test on noise source samples depends on the number of possible different symbols from the noise source (i.e., the size of the alphabet \(A\), denoted \(k\)). For example, consider two different noise sources. The first source outputs 4-bit samples, and thus has a possible total of \(2^4 = 16\) different symbols, and the second source outputs 32-bit samples, for a possible total of \(2^{32}\) different symbols.

The algorithm given below provides an example of a method for mapping the \(n\)-bit samples, collected as specified in Section 3.1.1, to \(m\)-bit samples, where \(n \ge m\). The resulting strings can be used as input to tests that may have infeasible data requirements if the mapping were not performed. Note that after the mapping is performed, the maximum amount of entropy possible per \(n\)-bit sample is \(m\) bits.

Given a noise source that produces \(n\)-bit samples, where \(n\) exceeds the bit-length that can be handled by the test, the submitter may provide the tester with an ordered ranking of the bits in the \(n\)-bit samples (see Section 3.2.2). The rank of ‘1’ corresponds to the bit assumed to be contributing the most entropy to the sample, and the rank of \(n\) corresponds to the bit contributing the least amount. If multiple bits contribute the same amount of entropy, the ranks can be assigned arbitrarily among those bits. The following algorithm, or its equivalent, is used to assign ranks.