Probability Approximation

Probability Level 5

"A jar contains a large number ( n n ) of balls. m m of these balls are red. We draw a relatively small number of balls: k < < m k << m . What is the probability of drawing only red balls?"

The exact answer to this question is P = ( m k ) / ( n k ) . \mathbb P = \binom m k / \binom n k. To save calculation work, and using k < < m k << m , we may use the simple approximation P 1 ≈ ( μ ν ) k \mathbb P_1 \approx \left(\frac \mu \nu\right)^k with μ = m − 1 2 ( k − 1 ) \mu = m - \tfrac12(k-1) and ν = n − 1 2 ( k − 1 ) \nu = n - \tfrac12(k-1) . This approximation is not bad, but it can be improved by the following "correction": P 2 ≈ P 1 ⋅ ( 1 − 1 c ( 1 μ 2 − 1 ν 2 ) k ( k 2 − 1 ) ) . \mathbb P_2 \approx \mathbb P_1 \cdot \left(1 - \frac 1 c \left(\frac 1{\mu^2} - \frac 1{\nu^2}\right)k(k^2-1)\right). How great is the integer c c ?


The answer is 24.

Arjen Vreugdenhil by Arjen Vreugdenhil , 44, USA

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Assuming that k k is odd, let k = 2 δ + 1 k = 2\delta + 1 and start with P = ( μ + δ ) ( μ + δ − 1 ) ⋯ ( μ + 1 ) μ ( μ − 1 ) ⋯ ( μ − δ ) ( ν + δ ) ( ν + δ − 1 ) ⋯ ( ν + 1 ) ν ( ν − 1 ) ⋯ ( ν − δ ) . \mathbb P = \frac{(\mu + \delta)(\mu + \delta -1)\cdots(\mu+1)\mu(\mu-1)\cdots(\mu-\delta)}{(\nu + \delta)(\nu + \delta -1)\cdots(\nu+1)\nu(\nu-1)\cdots(\nu-\delta)}. Combining positives and negatives, this becomes = ( μ 2 − δ 2 ) ( μ 2 − ( δ − 1 ) 2 ) ⋯ ( μ 2 − 1 2 ) μ ( ν 2 − δ 2 ) ( ν 2 − ( δ − 1 ) 2 ) ⋯ ( ν 2 − 1 2 ) ν . = \frac{(\mu^2 - \delta^2)(\mu^2 - (\delta-1)^2)\cdots(\mu^2 - 1^2) \mu}{(\nu^2 - \delta^2)(\nu^2 - (\delta-1)^2)\cdots(\nu^2 - 1^2) \nu}. = μ k − ( δ 2 + ( δ − 1 ) 2 + ⋯ + 1 2 ) μ k − 2 + O ( μ k − 4 ) ν k − ( δ 2 + ( δ − 1 ) 2 + ⋯ + 1 2 ) ν k − 2 + O ( ν k − 4 ) = \frac{\mu^k - (\delta^2 + (\delta-1)^2 + \cdots + 1^2)\mu^{k-2} + O(\mu^{k-4})}{\nu^k - (\delta^2 + (\delta-1)^2 + \cdots + 1^2)\nu^{k-2} + O(\nu^{k-4})} = ( μ ν ) k ( 1 − C μ − 2 + O ( μ − 4 ) 1 − C ν − 2 + O ( ν − 4 ) ) , = \left(\frac{\mu}{\nu}\right)^k\left(\frac{1 - C \mu^{-2} + O(\mu^{-4})}{1 - C \nu^{-2} + O(\nu^{-4})}\right), with C : = δ 2 + ( δ − 1 ) 2 + ⋯ + 1 2 = δ ( δ + 1 ) ( 2 δ + 1 ) 6 = 1 2 ( k − 1 ) ⋅ 1 2 ( k + 1 ) ⋅ k 6 = k ( k 2 − 1 ) 24 . C := \delta^2 + (\delta-1)^2 + \cdots + 1^2 = \frac{\delta(\delta+1)(2\delta+1)}6 = \frac{\tfrac12(k-1)\cdot\tfrac12(k+1)\cdot k}6 = \frac{k(k^2-1)}{24}.

Now for the approximation, we drop the O ( ⋅ ) O(\cdot) terms and use 1 / ( 1 − x ) ≈ 1 + x 1/(1-x) \approx 1+x for sufficiently small x x ; thus P ≈ ( μ ν ) k ( 1 − C ( 1 μ 2 − 1 ν 2 ) ) . \mathbb P \approx \left(\frac{\mu}{\nu}\right)^k\left(1 - C \left(\frac 1{\mu^2} - \frac 1{\nu^2}\right) \right). This is almost the desired expression for P 2 \mathbb P_2 ; we see that C = 1 c ⋅ k ( k 2 − 1 ) = k ( k 2 − 1 ) 24 , C = \frac 1 c\cdot k(k^2-1) = \frac{k(k^2-1)}{24}, showing that c = 24 c = \boxed{24} .

An alternative solution is simply by trying the formula for a typical case, say n = 102 n = 102 , m = 52 m = 52 , and k = 5 k = 5 . On one hand, P = 52 ⋅ 51 ⋅ 50 ⋅ 49 ⋅ 48 102 ⋅ 101 ⋅ 100 ⋅ 99 ⋅ 98 = 52 ⋅ 48 2 ⋅ 101 ⋅ 2 ⋅ 99 ⋅ 2 = 2 3 ⋅ 13 3 ⋅ 11 ⋅ 101 = 104 3333 ; \mathbb P = \frac{52\cdot 51\cdot 50\cdot 49\cdot 48}{102\cdot 101\cdot 100\cdot 99\cdot 98} = \frac{52\cdot 48}{2\cdot 101\cdot 2\cdot 99 \cdot 2} =\frac{2^3\cdot 13}{3\cdot 11\cdot 101} = \frac{104}{3333}; on the other hand, with ν = 100 \nu = 100 , μ = 50 \mu = 50 , k = 5 k = 5 , we have P ≈ ( 50 100 ) 5 ⋅ ( 1 − 1 c ( 1 5 0 2 − 1 10 0 2 ) ⋅ 5 ⋅ ( 5 2 − 1 ) ) , \mathbb P \approx \left(\frac{50}{100}\right)^5\cdot\left(1 - \frac 1 c\left(\frac{1}{50^2} - \frac{1}{100^2}\right)\cdot 5\cdot (5^2-1)\right), 104 3333 ≈ 1 32 ⋅ ( 1 − 1 c ⋅ 3 10 000 ⋅ 120 ) = 250 − 9 / c 8000 ; \frac{104}{3333} \approx \frac{1}{32}\cdot\left(1 - \frac 1c \cdot \frac{3}{10\:000}\cdot 120\right) = \frac{250 - 9/c}{8000}; the solution is c = 3333 ⋅ 9 3333 ⋅ 250 − 104 ⋅ 8000 = 29 997 1250 ≈ 30 000 10 000 / 8 = 24 . c = \frac{3333\cdot 9}{3333\cdot 250 - 104\cdot 8000} = \frac{29\:997}{1250} \approx \frac{30\:000}{10\:000/8} = \boxed{24}.

4 Helpful 2 Interesting 2 Brilliant 0 Confused

Extension: What is the probability that, when drawing k + ℓ < < m k+\ell << m balls, precisely k k of them are red and ℓ \ell aren't?

First approximation: P 1 = κ k λ ℓ ν k + ℓ ( k ℓ ) , \mathbb P_1 = \frac{\kappa^k \lambda^\ell}{\nu^{k+\ell}}\ \binom k \ell, with κ = m − 1 2 ( k − 1 ) \kappa = m - \tfrac12(k-1) , λ = ( n − m ) − 1 2 ( ℓ − 1 ) \lambda = (n-m) - \tfrac12(\ell-1) , ν = n − 1 2 ( k + ℓ − 1 ) \nu = n - \tfrac12(k+\ell-1) ;

second approximation: P 2 = P 1 ⋅ ( 1 − 1 24 ( k ( k 2 − 1 ) κ 2 + ℓ ( ℓ 2 − 1 ) λ 2 − ( k + ℓ ) ( [ k + ℓ ] 2 − 1 ) ν 2 ) ) . \mathbb P_2 = \mathbb P_1\cdot \left(1 - \frac{1}{24}\left( \frac{k(k^2-1)}{\kappa^2} + \frac{\ell(\ell^2-1)}{\lambda^2} - \frac{(k+\ell)([k+\ell]^2-1)}{\nu^2}\right)\right).

See how well this approximation works with n = 100 n = 100 , m = 60 m = 60 , k = 5 k = 5 , ℓ = 15 \ell =15 : P = ( 60 5 ) ( 40 15 ) ( 100 20 ) = 4.09884 ⋅ 1 0 − 4 ; \mathbb P = \frac{\binom{60}{5} \binom{40}{15}}{\binom{100}{20}} = 4.09884\cdot 10^{-4}; P 1 = 5 8 5 ⋅ 3 3 15 ( 90 1 2 ) 20 ( 20 5 ) = 4.49077 ⋅ 1 0 − 4 ; \mathbb P_1 = \frac{58^5\cdot 33^{15}}{(90\tfrac12)^{20}}\binom{20}5 = 4.49077\cdot 10^{-4}; P 2 = P 1 ⋅ ( 1 − 0.08945 ) = 4.08909 ⋅ 1 0 − 4 . \mathbb P_2 = \mathbb P_1\cdot (1-0.08945) = 4.08909\cdot 10^{-4}. The first approximation is nearly 10% off; the second, less than 1 4 \tfrac14 %.

Arjen Vreugdenhil - 1 year, 11 months ago

Log in to reply

Thing is, with numbers this small, you can just work out the probabilities as you did. I would argue that what matters is how well the approximation works when the numbers are too big to do this.

Joe Mansley - 1 year, 11 months ago

Log in to reply

Try with n = 3000 n = 3000 , m = 1000 m = 1000 , ℓ = 100 \ell =100 , k = 200 k = 200 : you get P 1 = 1.13223 ⋅ 1 0 − 35 \mathbb P_1 = 1.13223\cdot 10^{-35} , P 2 = 0.811186 ⋅ 1 0 − 35 \mathbb P_2 = 0.811186\cdot 10^{-35} . The exact value is P = 0.851482 ⋅ 1 0 − 35 \mathbb P = 0.851482\cdot 10^{-35} , an error of approx. 5%.

Arjen Vreugdenhil - 1 year, 11 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...