Problem 34 - A Computational Introduction to Number Theory and Algebra

Question

You are given three biased coins, where for \(i=1,2,3, \operatorname{coin} i\) comes up heads with probability \(p_{i} .\) The coins look identical, and all you know is the following: (1) \(\left|p_{1}-p_{2}\right|>0.01\) and (2) either \(p_{3}=p_{1}\) or \(p_{3}=p_{2}\). Your goal is to determine whether \(p_{3}\) is equal to \(p_{1}\), or to \(p_{2}\). Design a random experiment to determine this. The experiment may produce an incorrect result, but this should happen with probability at most \(10^{-12}\). Try to use a reasonable number of coin tosses.

Step-by-Step Solution

Answer

Answer: To determine this, we need to: 1. Toss the coins at least 109042 times, relying on the law of large numbers and Hoeffding's inequality. 2. Perform a hypothesis test using the number of heads obtained and an error tolerance of 0.005. 3. Determine whether the bias of coin 3 is equal to coin 1 or coin 2 based on the results of the hypothesis test, thereby reaching a conclusion with an error probability of at most \(10^{-12}\).

Step 1: Toss the coins the required number of times

To minimize the number of coin tosses, we will use the Hoeffding's inequality to estimate how many coin tosses are needed. Hoeffding's inequality states that for any \(\epsilon > 0\), the probability that the sum of independent binary random variables deviates from its expected value \(\operatorname{E}[X]\) by more than a constant \(\epsilon\) is bounded by: $$\operatorname{P}\left(\left|\sum_{i=1}^n X_i - n\operatorname{E}[X]\right| \geq n\epsilon \right) \leq 2 \exp{-2n\epsilon^2}$$ By setting the nominal bound \(\frac{1}{2}\epsilon^2\) equal to \(10^{-12}\) and solving for \(n\) we have: $$n \geq \frac{- \ln 2 \cdot 10^{-12}}{\frac{1}{2} \epsilon^2}$$ Since the coins have different biases by at least \(|p_1 - p_2| > 0.01\), we can set \(\epsilon\) to half that value (i.e., \(\epsilon = 0.005\)). Using the bound above, we find: $$n \geq \frac{- \ln 2 \cdot 10^{-12}}{\frac{1}{2} \cdot (0.005)^2} \approx 109042$$ We need at least \(n = 109042\) tosses for each coin to achieve the desired level of confidence.

Step 2: Perform a hypothesis test

Compute the number of heads obtained for each coin using the \(n\) coin tosses. Using these empirical values and an error tolerance \(\epsilon = 0.005\), we can perform the hypothesis test. - Null hypothesis: \(p_3 = p_1\) - Alternative hypothesis: \(p_3 = p_2\) Then, we can compute the test statistic as: $$Z = \frac{\frac{\text{number of heads of coin}_3}{n} - \frac{\text{number of heads of coin}_1}{n}}{\sqrt{\frac{\text{number of heads of coin}_1 + \text{number of heads of coin}_3}{n^2}}}$$ If \(|Z| > 6.91\) (which corresponds to a one-tailed test with \(p\)-value of \(10^{-12}\)), we reject the null hypothesis. Otherwise, we cannot reject it.

Step 3: Determine whether \(p_3\) is equal to \(p_1\) or \(p_2\)

If we reject the null hypothesis (\(p_3 = p_1\)), we conclude that \(p_3 = p_2\) with at least probability \(1 - 10^{-12}\). If we cannot reject the null hypothesis, we conclude that \(p_3 = p_1\) with at least probability \(1 - 10^{-12}\). This allows us to identify which coin's bias coin \(3\) shares with an error probability of at most \(10^{-12}\).

Key Concepts

Biased Coins

Coins don't always have an equal chance of landing on heads or tails. These are known as biased coins. In this exercise, we are given three such biased coins, each with different probabilities of landing on heads. The challenge here isn't just identifying whether a coin is biased, but rather comparing these biases to determine if the third coin's probability matches either the first or the second coin.

Here are some key concepts related to biased coins:

• Probability: The likelihood that a particular event will occur. For a fair coin, this would be 0.5 for heads and 0.5 for tails. For biased coins, these probabilities differ.
• Identical Appearance: Despite looking the same, the coins may perform differently. Hence, we need a strategic approach, often involving experiments, to determine the differences.

In the given problem, the term \(\left|p_1 - p_2\right| > 0.01\) indicates that the difference between the probabilities of heads coming up for coins 1 and 2 is greater than 0.01. This small but significant difference forms the basis for our experimental approach to determine the bias of coin 3.

Hypothesis Testing

Hypothesis testing is a critical statistical process used to infer the characteristics of a population from a sample. In our exercise context, it helps us decide whether coin 3's bias matches coin 1 or coin 2's bias.

Key components include:

• Null Hypothesis ( H₀ ): This is a statement of no effect or no difference. Here, it assumes coin 3 is akin to coin 1 ( H₀: p₃ = p₁ ).
• Alternative Hypothesis: This states something different from the null hypothesis, positing that coin 3 actually matches coin 2 ( H₁: p₃ = p₂ ).
• Test Statistic: An indicator calculated from sample data, which allows you to assess the validity of the null hypothesis. If the test statistic falls within a critical region, we reject H₀ .

In our exercise, if the computed test statistic exceeds a critical value, we would reject the null hypothesis, therefore determining the true bias of coin 3. The probability that we mistakenly reject a true null hypothesis is set to be extremely low, at 10^{-12}.

Probability Bounds

Probability bounds provide a mathematical limit on how much the actual outcome can deviate from the expected result. This idea is crucial when we need reliable results from experiments, especially when experimenting with random processes like coin tossing.

In this problem, Hoeffding's inequality is used. It's a form of concentration inequality that offers a probability bound for sums of independent random variables. Understanding these elements can help:

• Hoeffding's Inequality: Binds the probability that the sum of random variables deviates more than a specific amount from its mean. This deviation probability decreases exponentially with the number of trials.
• Parameter ε: Determines the acceptable level of deviation. We choose it based on known bias limits, here set to 0.005 for our confidence level.

By effectively using these bounds, we determine the number of trials ( 109042 in our case ) necessary to achieve results with the confidence that the error probability is no more than 10^{-12} . This ensures our hypothesis testing is grounded on solid, reliable data.