Testing Goodness of Fit with Discrete Data | 离散数据拟合优度检验

📚 Testing Goodness of Fit with Discrete Data | 离散数据拟合优度检验

In computer science, we frequently work with discrete data: hash values, dice-roll simulations, packet types, or labels produced by a classifier. Goodness-of-fit testing tells us whether the observed frequencies of these categories match a claimed theoretical distribution, such as a uniform distribution or a given probability mass function.

在计算机科学中，我们经常处理离散数据：哈希值、模拟掷骰子、数据包类型或分类器生成的标签。拟合优度检验可以告诉我们这些类别的观察频率是否与声称的理论分布相匹配，例如均匀分布或给定的概率质量函数。

For Edexcel A-Level Computer Science, this topic connects statistical reasoning with algorithm testing, random number generation, and data validation. The most common tool is the chi-squared goodness-of-fit test for discrete categories.

对于 Edexcel A-Level 计算机科学，该主题将统计推理与算法测试、随机数生成和数据验证联系起来。最常用的工具是面向离散类别的卡方拟合优度检验。

---

1. Discrete Data and Categorical Outcomes | 离散数据与分类结果

Discrete data takes values from a finite or countably infinite set. In goodness-of-fit testing, each observation falls into exactly one category, so we record integer counts rather than continuous measurements.

离散数据取自有限或可数无限集合。在拟合优度检验中，每个观测值恰好落入一个类别，因此我们记录的是整数计数，而不是连续测量值。

For example, if we simulate rolling a fair six-sided die 600 times, the expected count for each side is 100. Observed counts such as 98, 102, 95, 105, 97, 103 can be checked against this expectation.

例如，如果我们模拟掷一个公平的六面骰子 600 次，每一面的期望计数是 100。98、102、95、105、97、103 这样的观察计数可以与这个期望值进行对比。

---

2. Observed and Expected Frequencies | 观察频率与期望频率

The chi-squared test compares observed frequencies, written as Oᵢ, with expected frequencies, written as Eᵢ. Expected frequencies come from the null hypothesis, which usually states that the data follow a particular distribution.

卡方检验将观察频率 Oᵢ 与期望频率 Eᵢ 进行比较。期望频率来自零假设，该假设通常声称数据遵循某个特定分布。

• Oᵢ = actual count in category i
• ᵢ = n × pᵢ, where n is total observations and pᵢ is the claimed probability for category i

• Oᵢ = 类别 i 中的实际计数
• Eᵢ = n × pᵢ，其中 n 是总观测数，pᵢ 是类别 i 的声称概率

If every category has the same claimed probability, the expected frequency is simply n divided by the number of categories. This is common when testing whether a hash function distributes keys uniformly.

如果每个类别具有相同的声称概率，则期望频率就是 n 除以类别数。这在测试哈希函数是否均匀分布键值时很常见。

---

3. The Chi-Squared Test Statistic | 卡方检验统计量

We measure the total discrepancy between observed and expected counts with the chi-squared statistic. The formula sums over all k categories:

我们用卡方统计量衡量观察计数与期望计数之间的总偏差。该公式对所有 k 个类别求和：

χ² = Σ (Oᵢ - Eᵢ)² / Eᵢ

arge χ² value means observed counts differ greatly from what the null hypothesis predicts.

其中 Oᵢ 是观察频率，Eᵢ 是期望频率，求和从 i = 1 到 k。χ² 值越大，说明观察计数与零假设预测的差异越大。

Each term (Oᵢ - Eᵢ)² / Eᵢ is non-negative, so χ² is always at least zero. It equals zero only when every observed count exactly matches its expected count.

每一项 (Oᵢ - Eᵢ)² / Eᵢ 都是非负的，因此 χ² 始终至少为零。只有当每个观察计数都恰好等于其期望计数时，它才等于零。

---

4. Degrees of Freedom and Critical Values | 自由度与临界值

r ν. For a goodness-of-fit test with k categories and no estimated parameters, df = k - 1.

卡方分布有一个称为自由度的参数，通常记作 df 或 ν。对于具有 k 个类别且没有估计参数的拟合优度检验，df = k - 1。

We compare the calculated χ² statistic with a critical value from the chi-squared table at a chosen significance level, commonly 5% or 1%. If χ² exceeds the critical value, we reject the null hypothesis.

我们将计算得到的 χ² 统计量与卡方表中选定显著性水平（通常为 5% 或 1%）下的临界值进行比较。如果 χ² 超过临界值，则拒绝零假设。

For example, with df = 5 at the 5% ical value is 11.07. The more categories there are, the larger the critical value becomes.

例如，在 5% 水平下，自由度 df = 5 的临界值是 11.07。类别越多，临界值就越大。

---

5. Step-by-Step Calculation Process | 逐步计算过程

To carry out a goodness-of-fit test, follow these steps:

要执行拟合优度检验，请按照以下步骤操作：

• State the null hypothesis H₀: the data follow the claimed distribution, and H₁: they do not.
• Record the observed frequencies Oᵢ for each category.
• Calculate expected frequencies Eᵢ = n × pᵢ.
• Compute χ² using the formula.
• Find the degrees of freedom df = k - 1.
• Compare χ² with the critical value from tables, or use a p-value.
• Draw a conclusion in context.

• 陈述零假设 H₀：数据遵循声称的分布；以及备择假设 H₁：数据不遵循该分布。
• 记录每个类别的观察频率 Oᵢ。
• 计算期望频率 Eᵢ = n × pᵢ。
• 使用公式计算 χ²。
• 求出自由度 df = k - 1。
• 将 χ² 与表中的临界值比较，或使用 p 值。
• 结合上下文得出结论。

In a programming context, these steps can be implemented as a function that takes an array of observed counts and returns the test statistic and result.

在编程环境中，这些步骤可以实现为一个函数，该函数接收观察计数数组并返回检验统计量和结论。

---

6. Worked Example: Testing a Pseudorandom Dice Roller | 实例：测试伪随机掷骰子程序

Suppose a programmer writes a random number generator intended to simulate a fair six-sided die. The program is run 600 times, and the observed counts are shown below.

假设一名程序员编写了一个用于模拟公平六面骰子的随机数生成器。该程序运行 600 次，观察计数如下表所示。

Side	Observed O	Expected E
1	88	100
2	96	100
3	102	100
4	108	100
5	99	100
6	107	100

de. For side 1: (88 - 100)² / 100 = 144 / 100 = 1.44. Performing this for all sides gives:

我们计算每一面的贡献。对于面 1：(88 - 100)² / 100 = 144 / 100 = 1.44。对所有面进行计算得到：

χ² = 1.44 + 0.16 + 0.04 + 0.64 + 0.01 + 0.49 = 2.78

There are k = 6 categories, so df = 5. From chi-squared tables, the 5% ce 2.78 < 11.07, we do not reject H₀. The observed data are consistent with a fair die.

共有 k = 6 个类别，因此 df = 5。查卡方表，df = 5 时 5% 临界值为 11.07。由于 2.78 < 11.07，我们不拒绝 H₀。观察数据与公平骰子一致。

---

广告 / Sponsored

7. Using p-Values in Automated Testing | 在自动化测试中使用 p 值

Instead of comparing with critical values, many programs compute a p-value. The p-value is the probability of obtaining a χ² statistic at least as extreme as the one observed, assuming H₀ is true.

许多程序并不与临界值比较，而是计算 p 值。p 值是在 H₀ 为真的条件下，获得至少与观察值同样极端的 χ² 统计量的概率。

If the p-value is smaller than the significance level α, we reject H₀. A small p-value indicates strong evidence that the observed distribution does not match the expected distribution.

如果 p 值小于显著性水平 α，我们就拒绝 H₀。p 值较小说明有很强证据表明观察分布与期望分布不匹配。

imately 0.734, much larger than 0.05. This further confirms the generator passes the test.

对于上面的骰子示例，χ² = 2.78、df = 5 时，p 值约为 0.734，远大于 0.05。这进一步证实该生成器通过了检验。

---

8. Conditions and Limitations | 条件与局限性

The chi-squared goodness-of-fit test relies on a few important conditions. First, observations must be independent. Second, expected frequencies should generally be at least 5 for each category.

卡方拟合优度检验依赖于几个重要条件。首先，观测值必须相互独立。其次，每个类别的期望频率通常应至少为 5。

If some expected counts are below 5, adjacent categories may be combined until the minimum is met. This ensures the chi-squared approximation is valid.

如果某些期望计数低于 5，可以将相邻类别合并，直到满足最小值。这样可以确保卡方近似的有效性。

It is also important to remember that failing to reject H₀ does not prove the distribution is exactly correct; it only means there is insufficient evidence to say it is wrong.

还必须记住，未能拒绝 H₀ 并不能证明分布完全正确；它只是意味着没有足够证据表明该分布是错误的。

---

9. Pseudocode Implementation | 伪代码实现

In A-Level Computer Science, you may be asked to design an algorithm that tests the uniformity of discrete outputs. The following pseudocode computes the chi-squared statistic.

在 A-Level 计算机科学中，你可能需要设计一个算法来检验离散输出的均匀性。以下伪代码计算卡方统计量。

FUNCTION chiSquared(observed, expected)
    total ← 0
    FOR i ← 0 TO LEN(observed) - 1
        diff ← observed[i] - expected[i]
        total ← total + (diff * diff) / expected[i]
    NEXT i
    RETURN total
END FUNCTION

The function expects arrays of equal length. In real programs, expected values can be computed from the total count and the claimed probabilities to avoid hard-coding.

该函数要求两个数组长度相同。在实际程序中，期望值可以根据总计数和声称的概率计算出来，从而避免硬编码。

This algorithm is straightforward to translate into Python, Java, or C#. Always guard against division by zero when an expected frequency is zero.

该算法可以很容易地翻译为 Python、Java 或 C#。当期望频率为零时，务必防止除以零。

---

10. Applications in Computer Science | 计算机科学中的应用

Goodness-of-fit testing appears in several computing contexts. One major application is evaluating random number generators, which should produce uniform discrete outputs over their range.

拟合优度检验出现在多个计算场景中。一个主要应用是评估随机数生成器，它们应在其范围内产生均匀的离散输出。

Another application is validating hash function performance. If a hash table claims to distribute keys evenly across buckets, a chi-squared test can check whether observed bucket counts match a uniform distribution.

另一个应用是验证哈希函数的性能。如果哈希表声称将键均匀分布到各个桶中，卡方检验可以检查观察到的桶计数是否与均匀分布匹配。

The test can also be used to compare classifier output frequencies with expected class proportions, helping detect bias in machine learning pipelines.

该检验还可用于将分类器输出频率与期望的类别比例进行比较，帮助检测机器学习管道中的偏差。

---

11. Common Pitfalls | 常见错误

One common mistake is using percentages instead of actual counts. The chi-squared statistic requires frequencies, not proportions or percentages, because the variance depends on sample size.

一个常见错误是使用百分比而不是实际计数。卡方统计量需要的是频率，而不是比例或百分比，因为方差取决于样本大小。

rong conclusion. Always compute df = k - 1 when no parameters are estimated from the data.

另一个错误是忽略自由度。使用错误的 df 会导致错误的临界值和错误结论。在没有从数据中估计参数时，始终计算 df = k - 1。

Finally, do not claim that a non-significant result proves the distribution is correct. It is better to say the data provide no evidence against the claimed distribution.

最后，不要声称不显著的结果证明了分布是正确的。更好的说法是数据没有提供反对声称分布的证据。

---

12. Summary and Exam Tips | 总结与考试提示

rved and expected category counts. The formula is χ² = Σ (Oᵢ - Eᵢ)² / Eᵢ, with df = k - 1.

离散数据拟合优度检验使用卡方统计量来比较观察和期望的类别计数。公式为 χ² = Σ (Oᵢ - Eᵢ)² / Eᵢ，自由度 df = k - 1。

In an exam, show all calculations clearly, state both hypotheses, and write a conclusion in context. Be prepared to interpret p-values and to explain when the test is appropriate.

在考试中，要清晰地展示所有计算过程，陈述两个假设，并结合上下文写出结论。准备好解释 p 值，并说明何时适合使用该检验。

For computer science questions, link the test to algorithms such as random number generation, hash tables, or simulation outputs. This demonstrates both statistical understanding and computational thinking.

对于计算机科学题目，要将该检验与随机数生成、哈希表或模拟输出等算法联系起来。这既能展示统计理解，也能展示计算思维。

Published by TutorHao | Computer Science Revision Series | aleveler.com

更多咨询请联系16621398022（同微信）