Subject: Poisson example

From: "Gary Lorden" <[email-masked]>
Date: Wed, 17 Jan 2007 20:42:30 -0800

I introduced the Poisson distribution today, and gave them the fact
that

-- the "worst case" difference between the binomial(n,p) and the Poisson
with lambda=n*p is for small p (p<.1 or so) is about p/4.   So regardless of
n, if p is small then the Poisson approximation to the Binomial is pretty
good.

-- "Law of Rare Events":  if A_1,....A_n are independent events (or "almost
independent"-- i.e. conditional probabilities are close to the unconditional
ones), and if their probabilities are p_1,...p_n, all "small", then the
probability
that the number of the A's that occur is in the interval [a b] differs from
the
Poisson probability of [a b] -- using lambda=p_1+,,,p_n---by about

(1/4) times  the sum of the squares of the p_i's divided by the sum of the
p_i's.

So the Poisson approximation, defining lambda this way (=expected number
of events that occur) is in some sense just as good for "generalized
Bernoulli
trials" (meaning different p's on different trials) as it is for Bernoulli
trials.
And "almost independent" is good enough.

So I mentioned examples of the application of the Poisson approximation to
 "almost independent" events--

-- the birthday problem (either pairs or triples of matching birthdays

-- putting lots of balls into cells (or boxes), like the baseball card
homework
problem, and looking at the probability that the number of "empty cells" is
0,1,2,... (Since this is on the homework, it's not a good example to do too
much with.)

-- the problem of a random permutation of n objects-- say, the numbers
1,2,...,n.   How many objects are in the same position after the random
permutation
is applied?   On average, the answer is =1, which I told them.  (Each object
has a 1/n chance...so the sum of the n probabilities is 1.  Technically,
since we
haven't defined expectation, we're just using the law of rare events, and so
lambda= sum of the probabilities= 1.)  So the Poisson distribution with
lambda=1
describes well (at least for large n) the distribution of the number of
"objects that
don't move" in the random permutation.

This last problem is a reasonable one to discuss in recitation.  Wish I knew
a nice
way to calculate the exact probabilities for comparison!

G.L.

---

From: "Gary Lorden" <[email-masked]>
Date: Wed, 17 Jan 2007 21:20:42 -0800

Just reacquainted myself with the subfactorial function at

http://en.wikipedia.org/wiki/Subfactorial

Turns out that there's a simple formula for !n=subfactorial(n),
defined as the number of permutations of n objects that fix
zero of them.

It's [n!/e], where the brackets denote "nearest integer".

It's easy to see that when a random  permutation is chosen
the number of outcomes that fix exactly k objects is

"n choose k" times !(n-k)

since once we choose which k of the objects 1,...,n to fix,
we have to permute the others without fixing any of them.
Using the formula for !n, we conclude that the number of
permutations that fix exactly k is

1/k! times n(n-1)...(n-k+1) times [(n-k)!/e]

If not for the "[ ]", this would be n! / k! times (exp(-1)).
Dividing by n!, we get that the probability of exactly
k objects fixed is exp(-1)/k!-- EXACTLY the Poisson
approximation.   So the only approximation going on
is replacing the [(n-k)!/e]  by (n-k)!/e.    If n is decently
large, then for interesting k (the Poisson mean=1, after all)
the exact answer is extremely close to the Poisson approximation.

G.

On 1/17/07, Gary Lorden <[email-masked]> wrote:
> that the number of the A's that occur is in the interval [a b] differs
> from the
> This last problem is a reasonable one to discuss in recitation.  Wish I
> knew a nice