The end of privacy

New technologies will reduce privacy even more.

I can enter my club with my finger print.

http://www.economist.com/displaystory.cfm?story_id=10059596
http://www.economist.com/science/tq/displaystory.cfm?story_id=9719045

there is soooo much on line

Actually I am quite impressed by how much can be found
on-line. For instance, yesterday I found that
Abramowitz and Stegun is on-line:
http://www.math.sfu.ca/~cbm/aands/
When I started math in 1978, this was THE reference
for numerical results. For many years I had a
copy of the table with prime numbers with me.
Apparently this part was not copied; only the formulas
are.

coin or change problem

I also wanted to write about the coin problem
or change problem. When I read about this in CM
I *had* to buy the book. Turns out that a
fair discussion is available on line,
but not in Wikipedia though. See
http://www.cut-the-knot.org/ctk/GeneratingFunctions.shtml

In fact the whole business is somewhat less surprising
if you think about binomial coefficients in a symbolic
way: in (A+B)^4 we have that there are (4 choose 2) = 6
combinations of AABB. This is also the coefficient
of X^2 in (1+x)^4. Likewise, we find that the number
of ways to give change for t cents is the exponent
of (1+X+X^2+ ...)(1+5X+25X^2+ ...)(1+10X+100X^2+ ...)(1+25X+625X^2+ ...)
if the nominations are 1, 5, 20 and 25 cents (the old Dutch system)
Surprising is that these expressions can be changed for
1/1-X, 1-5X, 1-10X and 1-25X, and that we can
multiply those, without running into trouble.

Derangements

One problem that always interested me is related
to permutations: if you choose an arbitrary permutation,
what is the probability that no number stays in the same place.
In the text books this is known as the hat problem,
but I know it from Sinterklaas parties in which people
must make a surprise for somebody else.
So all names are written on a piece of paper
and everybody must draw a name. What is the
probability that this process succeeds the first time.

The problem is discussed various times in Sheldon Ross's
book, in section 5m. In this approach the
inclusion exclusion principle is used to establish
the sum
1 - 1 + 1/2! - 1/3! + (-1)**N/N! which approached 1/e ~ .36788
See also example 3.5c.

Daniel Marcus also discusses the problem. Permutations
that move all its elements are called derangements,
and he give the first values.

Then in F he gives two recurrence relations:
D_n = (n-1) (D_{n-1} + D_{n-2}) ; n >=3
D_n = n D_{n-1} + (-1)^n ; n>= 2

Today I found a piece of paper which made me remember that
Knuth also discusses this problem [193].
He uses h(n,k), where n is the number of hat owners
and k the number of people that get there hat back,
so D_n = h(n,0).

The following formula is also pretty obvious:
h(n, k) = (n choose k) h(n-k, 0).

He also gives a table which is loaded with structure

n h(n,0) 1 2 3 4 5 6
0 - 1
1 - 0 1
2 - 1 0 1
3 2 3 0 1
4 9 8 6 0 1
5 44 45 20 10 0 1
6 265 264 135 40 15 0 1
(I should program this)

They say that
h(n, 0) - h(n, 1) = (-1)^n and
h(n, n-2) = (n choose 2)
But it also seems that
h(n, 1) = n h(n-1, 0)
and that
h(n, 2) = n/2 h(n-1, 1)
and maybe
h(n, 3) = n/3 h(n-1, 2)
10 = 5/3 * 6
40 = 6/3 * 20
and maybe
h(n, 4) = n/4 h(n-1, 3)
15 = 6/4 * 10

Another observation is that these tables make me thin of
the poisson distribution with lambda=1,
where the values for n=0=1 equals 1/e ~.36788
For n=6 we get
264.87
132.43
44.14
11.03
2.21
so that is close enough


Aah, this is certainly true and it is surprising
that itś not mentioned. Now I only need to figure
out why.

Anyway, what I really liked is that GKP estimate the
error of D_n = h(n, 0) within one integer,
meaning that they can calculate it as
floor( n!/e + .5 )


Buuh, all this stuff is already available on line.
It is actually impressive. See
http://en.wikipedia.org/wiki/Derangement
http://www.research.att.com/~njas/sequences/A000166
http://en.wikipedia.org/wiki/Rencontres_numbers

This thing about the exact approximation is listed also,
anmd my observation about the Poisson distribution
is too. But the relation within the table I have not
found yet.