Let . Using a probabilistic method, evaluate: .

Probability Theory Solution – Problem 24: Let

Question

Let $p \in (0.5,1)$ . Using a probabilistic method, evaluate: $\displaystyle \lim_{n \to \infty} (2n+1)\cdot \sum_{k = 0}^n \binom{2n+1}{k} p^k(1-p)^{2n+1-k}$ .

Step-by-step solution

Let $S_{2n+1} \sim \text{Binomial}(2n+1, p)$ . Then $\sum_{k=0}^n \binom{2n+1}{k} p^k (1-p)^{2n+1-k} = P(S_{2n+1} \le n).$ Since $p > 0.5$ , the expectation $E[S_{2n+1}] = (2n+1)p > n + 0.5$ for large $n$ , so $P(S_{2n+1} \le n)$ is small.

Step 1. Standardization: $\mu = E[S_{2n+1}] = (2n+1)p,$ $\sigma^2 = \mathrm{Var}(S_{2n+1}) = (2n+1)p(1-p).$ Let $Z_n = \frac{S_{2n+1} - \mu}{\sigma}.$ The event $\{S_{2n+1} \le n\}$ is equivalent to $Z_n \le \frac{n - (2n+1)p}{\sqrt{(2n+1)p(1-p)}}.$ Let $q = 1-p$ , so that $p > 0.5$ implies $q < 0.5$ .

$n - (2n+1)p = n - 2np - p = - (2p-1)n - p.$ Since $2p-1 > 0$ , for large $n$ this quantity is negative and of order $\approx -(2p-1)n$ .

Step 2. More precisely: $\frac{n - (2n+1)p}{\sigma} = \frac{- (2p-1)n - p}{\sqrt{(2n+1)pq}}.$ Setting $\delta = 2p-1 > 0$ , we obtain $\frac{n - \mu}{\sigma} \approx -\frac{\delta n}{\sqrt{2n pq}} = -\frac{\delta}{\sqrt{2pq}} \cdot \sqrt{n}.$ Hence this tends to $-\infty$ at rate $-c\sqrt{n}$ , where $c = \frac{\delta}{\sqrt{2pq}} > 0$ .

Step 3. For the standard normal distribution, as $x \to -\infty$ , the Mills ratio estimate gives: $\frac{\phi(x)}{\Phi(x)} \sim -x, \quad x \to -\infty.$ More precisely, as $x \to -\infty$ : $\Phi(x) \sim \frac{\phi(x)}{|x|}.$ Here $x_n \approx -c\sqrt{n}$ , so $\phi(x_n) = \frac{1}{\sqrt{2\pi}} e^{-x_n^2/2} \approx \frac{1}{\sqrt{2\pi}} e^{-c^2 n/2}.$ Thus $\Phi(x_n) \sim \frac{\phi(x_n)}{c\sqrt{n}}.$

Step 4. Therefore $P(S_{2n+1} \le n) \sim \frac{1}{c\sqrt{n}} \cdot \frac{1}{\sqrt{2\pi}} e^{-c^2 n/2}.$

$(2n+1) P(S_{2n+1} \le n) \sim \frac{2n}{c\sqrt{n}} \cdot \frac{1}{\sqrt{2\pi}} e^{-c^2 n/2} = \frac{2\sqrt{n}}{c\sqrt{2\pi}} e^{-c^2 n/2}.$ As $n \to \infty$ , the exponential decay $e^{-c^2 n/2}$ dominates the $\sqrt{n}$ growth, so $(2n+1) P(S_{2n+1} \le n) \to 0.$ Therefore $\lim_{n \to \infty} (2n+1)\sum_{k=0}^{n}\binom{2n+1}{k}p^{k}(1-p)^{2n+1-k} =0.$ QED.

Final answer

Marking scheme

The following is the undergraduate-level marking scheme for this probability limit problem (total: 7 points).

1. Key Checkpoints (max 7 pts total)

Group 1: Probabilistic Model Formulation [cumulative]

Recognize that the summation $\sum \binom{2n+1}{k} p^k(1-p)^{2n+1-k}$ equals the cumulative probability $P(S_{2n+1} \le n)$ of a binomial distribution (or an equivalent random variable representation). (1 pt)
*Note: If no random variable is introduced but subsequent calculations correctly follow the normal approximation framework, credit may be awarded retroactively.*

Group 2: Core Analysis and Decay Estimate (score exactly one chain)

*For different solution paths, score according to one of the following; if methods are mixed, take the highest-scoring path.*

Path A: Normal Approximation and Asymptotic Analysis (standard solution)
Standardization parameters: Write down or use the correct mean $\mu=(2n+1)p$ and variance $\sigma^2=(2n+1)p(1-p)$ , and attempt standardization $Z = \frac{S-\mu}{\sigma}$ . (1 pt)
Boundary asymptotic behavior: Analyze the standardized upper bound $x_n = \frac{n-\mu}{\sigma}$ and explicitly identify that its order as $n\to\infty$ is $-c\sqrt{n}$ (i.e., it tends to negative infinity proportionally to $\sqrt{n}$ ). (2 pts)
*If only the algebraic expression is written without simplification or without identifying the $\sqrt{n}$ relationship, no credit is awarded for this item.*
Tail probability estimate: Invoke the Mills ratio or the normal distribution tail asymptotic formula ( $\Phi(x) \sim \frac{1}{|x|\sqrt{2\pi}}e^{-x^2/2}$ ) and explicitly establish that the probability term exhibits exponential decay (e.g., $e^{-cn}$ or $e^{-c^2 n/2}$ ). (2 pts)
Path B: Large Deviations / Concentration Inequalities (Hoeffding/Chernoff Bound)
Inequality setup: Correctly set up the inequality parameters, identifying the deviation $\epsilon = p - 0.5 > 0$ (or noting that the distance between the expected value and $n$ is linear, i.e., $O(n)$ ). (2 pts)
Exponential upper bound: Apply the inequality to obtain an exponential upper bound of the form $P(S_{2n+1} \le n) \le C e^{-kn}$ . (3 pts)

Group 3: Limit Conclusion [cumulative]

Resolving the indeterminate form: Combine the linear growth of the prefactor $(2n+1)$ with the exponential decay of the probability term to conclude that the limit is 0. (1 pt)
*Requirement: The argument must reflect the reasoning that exponential decay dominates polynomial/linear growth. If the conclusion is drawn solely from the probability tending to 0 without comparing rates, no credit is awarded for this item.*

Total (max 7) check: 1 + 5 + 1 = 7.

2. Zero-Credit Items

Merely copying the problem statement or listing the binomial expansion formula without any substantive computation.
Stating only the answer "0" with no supporting work.
Misapplying Chebyshev's Inequality to prove the limit is 0:
Chebyshev's inequality yields only an $O(1/n)$ upper bound; multiplying by $(2n+1)$ gives a constant, which is insufficient to prove the limit is 0. If this path claims to have completed the proof, it constitutes a logical error, and only the model formulation points (if any) are awarded.
Computing with a specific value such as $p=0.5$ or other particular numerical values.

3. Deductions

Logic gap cap (capped at 2/7):
If the student uses the Central Limit Theorem (CLT) only to conclude $P(S \le n) \to \Phi(-\infty) = 0$ without analyzing the rate of convergence (i.e., without explaining why the $0 \cdot \infty$ indeterminate form resolves to 0 rather than some other value), the total score shall not exceed 2 points (model formulation and parameter points only).
Computational/notational error (-1):
Coefficient errors in the mean or variance computation (e.g., omitting $2n+1$ ) that do not affect the core qualitative conclusion of exponential decay.
Inequality direction error (-1):
In Path B, writing the inequality in the wrong direction (e.g., $P \ge \dots$ ) while the subsequent reasoning assumes the correct direction.
Maximum deduction principle: Errors within the same logical chain are not penalized more than once; the total score after deductions shall not fall below 0.

Probability Theory – Problem 24: Let