Wikipedia:Reference desk/Archives/Mathematics/2010 December 20

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

December 20

Binomial distribution for small p, high right tails, mental calculation?

Suppose I'm interested in a quantity distributed as a binomial distribution with small p and large N, and I want to get an estimate of the probability that the quantity is, say, four standard deviations above the mean. According to binomial distribution, the skewness is (1-2p)/sqrt(np(1-p)), which will be positive, meaning fat right tails, if I have that right. So I probably can't just treat it as a normal variate with mean Np and variance Np. Is there any fast, mental-arithmetic-type way of estimating the probability of such an extreme value? --Trovatore (talk) 10:13, 20 December 2010 (UTC)

(P.S. for why I'm interested, see Talk:Congenital insensitivity to pain with anhidrosis#contradiction template.) --Trovatore (talk) 10:32, 20 December 2010 (UTC)

For small p and large n the appropriate approximation to the Binomial distribution Bin(n, p) is the Poisson distribution Poi(λ = np). See Binomial distribution#Poisson approximation. The cumulative distribution function of the Poisson appears a bit hard to evaluate using mental arithmetic, though you could investigate the asymptotics of the Incomplete gamma function. For your first case of interest (US), n = 3×10⁸ and p = 1/1.25×10⁸ giving np = 300/125 = 2.4. Stata and R then both give P(X ≥ 80) = 3.4×10^–90 for a Poisson with λ = 2.4. Your second case of interest (Japan) leads to arithmetic underflow. For the whole world n = 6×10⁹, np = 48 gives P(X ≥ 80) = 1.5×10^–5. --Qwfp (talk) 11:08, 20 December 2010 (UTC)

The probability that the quantity is four standard deviations above the mean is 1−e^−pNΣ[0≤i<pN+4√(pN)](pN)ⁱ/i!, where [] is an Iverson bracket. The finite sum can be computed for small values of pN, and otherwise the normal distribution approximation is excellent. Bo Jacoby (talk) 11:44, 20 December 2010 (UTC).

The Poisson distribution does seem appropriate to the context. Regardless of the skewness of the binomial distribution, for any non-negative valued random variable, Markov's inequality applies, and in this case that's enough to tell you that being that far above average is quite improbable. (Markov's inequality is what says no more that 1/n of the population can have more than n times the average income (if incomes are non-negative), etc.) Michael Hardy (talk) 19:33, 20 December 2010 (UTC)

Here's a handwaving version that gives approximately the right order of magnitude using only mental arithmetic: for a Poisson distribution, using of the third result under Incomplete gamma function#Asymptotic behavior and then Stirling's approximation:

$\operatorname {P} (X\geq x)\sim \operatorname {P} (X=x)={\frac {e^{-\lambda }\lambda ^{x}}{x!}}\sim {\frac {e^{-\lambda }\lambda ^{x}}{e^{-x}x^{x}}}=e^{-\lambda }(e\lambda /x)^{x}$

where ~ means something like "is asymptotically of approximately the order of magnitude of". With $\lambda =2.4$ and $x=80$,

$e^{-\lambda }(e\lambda /x)^{x}\approx 0.1\times 0.1^{80}=10^{-81}.$

--Qwfp (talk) 21:23, 20 December 2010 (UTC)

Table of marks

Hi all,

I'm trying to figure out how the table of marks is calculated. For those of you unfarmiliar with it it is defined on the wikipedia page

1. http://en.wikipedia.org/wiki/Burnside_ring here(under the section marks), the important bit being:

For each pair of subgroups $H,K\leq G$ define

$m(K,H)=\left|[G/K]^{H}\right|=\#\left\{gK\in G/K\mid HgK=gK\right\}.$ Then finding the groups subgroups, and then putting them into conjugacy classes of subgroups, we get a string of representative subgroups $G_{1},\dots ,G_{N}$ where $G_{1}$ is the trivial group and $G_{N}$ is the whole group. Then we can make a N x N matrix where the i,j th entry is $m(G_{i},G_{j})$

So for $S_{3}$ ${\begin{array}{ccccc}S_{3}&1&Z_{2}&Z_{3}&S_{3}\\S_{3}/1&6&.&.&.\\S_{3}/Z_{2}&3&1&.&.\\S_{3}/Z_{3}&2&0&2&.\\S_{3}/S_{3}&1&1&1&1\end{array}}$

I can calculate the top left entry obviously, and the bottom row, but I literally have no idea how to calculate the others. If someone could talk me through how to calculate another more difficult entry for S3, that is a difficult $m(G_{i},G_{j})$, it would be of great help.

Many thanks in advance for any help, and have a merry christmas everyone! —Preceding unsigned comment added by 86.139.252.252 (talk) 12:46, 20 December 2010 (UTC)

With groups as small as $S_{3}$, we can just do it directly from the definition. Say $S_{3}=\{e,(12),(13),(23),(123),(132)\}\$. Let $K=\langle (123)\rangle \$ and $H=\langle (12)\rangle \$. Then $m(K,H)$ is the number of left cosets of K that are fixed on the left by H. There are two left cosets of K, namely $\{e,(123),(132)\}\$ and $\{(12),(23),(13)\}\$. Multiply each of these on the left by H; in both cases you get the entire group $S_{3}$, so the number of left cosets of K that are fixed on the left by H is 0, so $m(K,H)=0$. Eric. 82.139.80.114 (talk) 01:10, 22 December 2010 (UTC)

Thanks!, I was just getting confused about cosets I think..

Resolved

Euclid's Algorithm

Can someone give me some advice on how you would use Euclid's algorithm to find the solutions in x for $ax\equiv b$ (mod m)? I have thought of two possible approaches, both of which seem useless as I end up using Bezout's Theorem rather than Euclid. For the first, I simply say we must have ax-b=km for some integer k, then rearrange to have ax-km=b, define k'=-k to give ax+k'm=b and apply Bezout (after checking that hcf(a,m) divides b). The second approach I thought of is simply find some t such that $ta\equiv b$ (mod m), which will allow me to multiply both sides of the original congruence to give $x\equiv bt$ (mod m). To find t, I would need to apply Bezout to ta-b=pm for some integer p, so these two methods are essentially the same. I don't see Euclid in either of them. Any ideas? Thanks 92.11.32.186 (talk) 21:49, 20 December 2010 (UTC)

Bezout's identity is a corollary of the extended Euclidean algorithm. Aenar (talk) 00:07, 21 December 2010 (UTC)