June 2006 - mathfun@mailman.xmission.com

[math-fun] Zipf, Harmonic series & Egyptian fractions
by Henry Baker 15 Jun '06

15 Jun '06

Zipf's Law says that the probability of the n'th most popular thingy is proportional to 1/n. Clearly this probability exists only if the universe of thingy's is finite. I'm interested in efficient encodings of thingy's. The Shannon-Fano code says to split the thingy's into two groups having approximately equal probabilities, assign on group an initial bit "0" and the other group an inital bit "1", and then recurse within the groups. This means to me that one must express the fraction 1/2 as a sum of probabilities, each of which is proportional to 1/k for some integer k. Is there a general way to do this for arbitrary m, where m is the number of thingy's ? I.e., is there a general scheme for splitting the infinite set {1/k} into two pieces that gives an optimal encoding for every m ? If such a general scheme isn't exactly optimal, what about a scheme that is within epsilon of being optimal ? I presume that this question has already been studied, so I'm primarily looking for a reference. Thanks in advance for any help on this. Henry Baker hbaker1(a)pipeline.com

3 2

[math-fun] coins in barrels
by James Propp 14 Jun '06

14 Jun '06

For a change of pace, here's a real probability question: Cheng Qian, an engineering student doing work on visual sensor networks, asks: >I throw n coins into m barrels randomly. (For a single coin, each barrel has >same chance to get it.) Then I count the number of coins in each barrel, say >k(i), i=1...m . > >My question: what is the probability that all the barrels have no more than K >coins, i.e. k(i)<=K, for i=1..m. Does anyone know any good off-the-shelf approximations to this? (I assume that an exact formula would be too much to ask for.) This isn't exactly "fun" math, but it's a simple and natural enough question that I thought it wouldn't be out of place in this group. Jim Propp

2 1

[math-fun] Re: hidden assumptions in word puzzles
by Steve Witham 13 Jun '06

13 Jun '06

>From: David Wolfe <wolfe(a)gustavus.edu> >Subject: Re: [math-fun] Error in Scientific American math puzzle. > >This brings up a point that has always troubled me a bit. > >It's challenging to state all of the assumptions required to solve >artificial "real-world" word problems. But in my view, stating these >assumptions should be left to the problem solver, and not the problem >poser. That reminds me of Marilyn vos Savant and the Monty Hall Problem. http://en.wikipedia.org/wiki/Monty_Hall_problem#The_General_Case In general there are situations where the common intuition is "proven" to be wrong by faulty logic. In this case the poser becomes the solver and I suppose that means David's preference applies to them too, but I find it particularly bad when the poser is in a position of authority or teacherhood with respect to an audience some of whom aren't prepared for this kind of abuse. --Steve ( First time posting to this list. What led me here was talking to Gosper about integer rotation transformations: http://www.tiac.net/~sw/chrono.html#2005.03 )

1 0

Re: [math-fun] Abelian group puzzle
by Michael Reid 13 Jun '06

13 Jun '06

) > in particular, its dimension would be independent of p . ) ... ) ) Why? a basis of A over Z maps (bijectively) to a basis of A/pA over Z/pZ . thus the dimension of A/pA over Z/pZ equals the rank of A , which is independent of p . > > 2A = { (a_n) in P | v(a_n) --> infinity and each a_n is > > even } > > > > so there is an obvious countable basis for A/2A over Z/2Z , namely > > { e_i } , where e_i is 0 in all coordinates, except for a single > > 1 > > in the i-th coordinate. thus the dimension of A/2A over Z/2Z is > > countably infinite. > > The e_i, regarded either as group generators or as a vector space > basis, generate only finite sums, i.e. sequences that are 0 for all but > finitely many coordinates. On the other hand, A/2A consists of > arbitrary 0,1 sequences. Thus A/2A is uncountably infinite, and so its > dimension over Z/2Z is also uncountably infinite. no, the condition on A (namely, v(a_n) --> infinity as n --> infinity ) shows that A/2A consists only of even-odd sequences that have only finitely many odd terms. mike

1 0

Re: [math-fun] Abelian group puzzle
by Michael Reid 13 Jun '06

13 Jun '06

> Let P denote the direct product of countably many copies of the integers Z. > > E.g., the set {f: Z+ --> Z | f is a function} under addition of functions. > > Puzzle: Is P a free abelian group? Prove your answer. P is not free abelian. i learned this many years ago, if memory serves, in a class of t. y. lam. i have been trying to remember the proof, which is much more likely than finding my notes. now i think i have it. i'm not sure this was the original proof that i saw, but it's probably close. any subgroup of a free abelian group is also free abelian, so it suffices to find a subgroup of P that is not free abelian. let A = { (a_n) in P | v(a_n) --> infinity as n --> infinity } where v(k) is the largest exponent of a power of 2 that divides k , v(0) = infinity . (here i've written elements of P as sequences, rather than functions.) we claim that A is not free abelian. if it were, then for any prime p , the group A/pA would be a vector space over the field Z/pZ , with the image of a basis of A being a basis of A/pA over Z/pZ . in particular, its dimension would be independent of p . first consider p = 2 . note that 2A = { (a_n) in P | v(a_n) --> infinity and each a_n is even } so there is an obvious countable basis for A/2A over Z/2Z , namely { e_i } , where e_i is 0 in all coordinates, except for a single 1 in the i-th coordinate. thus the dimension of A/2A over Z/2Z is countably infinite. now consider m = 3 . in this case, A/3A is uncountable: for any sequence (b_n) of 0's, 1's and 2's , we have the element (4^n b_n) in A , and all have different classes in A/3A . therefore the dimension of A/3A over Z/3Z is uncountable. this shows that A , and therefore, P is not free abelian. mike

3 2

Re: [math-fun] Abelian group puzzle
by dasimov＠earthlink.net 13 Jun '06

13 Jun '06

Btw, that's Bartholomew, not Bartholemew.

2 1

Re: [math-fun] Abelian group puzzle
by dasimov＠earthlink.net 13 Jun '06

13 Jun '06

Mike's right, I meant finitely generated, not finite.

1 0

Re: [math-fun] Abelian group puzzle
by dasimov＠earthlink.net 13 Jun '06

13 Jun '06

<< Am I missing something? According to mathworld, a free abelian group is an abelian group with no torsion, seemingly meaning that the only element with finite order is the identity (in this case the zero function). Clearly here, no function other than zero has finite order. Now if you ask for a set of generators, that could be a bit tricky. It's hard to list uncountably many things. >> I'll post a proof soon (along the lines of Michael's sketch). But the definition of free abelian group above is valid only for *finite* abelian groups. Here's an example: Let P (S) denote the countable direct product (sum) of Z's, say indexed by 1,2,3,.... Then it's easy to see that the quotient group P/S has no torsion. But the the coset class [(1,2,4,8,...,2^n,...)] is divisible by arbitrarily high integers (since we may ignore any finite initial string). But no free abelian group can have an element divisible by arbitrarily high integers. (Def. Given any set X, the free abelian group on X is all expressions of the form {sum{k=1 to N} of x_k : N is a nonnegative integer and all x_k belong to X (with the obvious identifications made for the zero element).) --Dan

1 0

RE: [math-fun] Re: Error in Scientific American math puzzle.
by Andy Latto 13 Jun '06

13 Jun '06

> -----Original Message----- > From: math-fun-bounces+andy.latto=pobox.com(a)mailman.xmission.com > On Behalf Of James Propp > Sent: Monday, June 12, 2006 11:11 PM > To: math-fun(a)mailman.xmission.com > Subject: [math-fun] Re: Error in Scientific American math puzzle. > > > The way I usually teach this topic in introductory probability > classes is that (under assumptions that need to be made explicit > but are very reasonable), the question > > "A family has two children, at least one of whom is a boy; what > is the probability that both are boys?" > > and > > "A family has two children, at least one of whom is a boy named > Bartholomew; what is the probability that both are boys?" > > have different answers. That's a really nice version of the puzzle. The (very slight) flaw is that in the second case, the answer is not "1/2", but "very slightly less than 1/2". It's important that you present the problem with an unusual name, like Bartholemew, since the more common the name, the greater the deviation from 1/2. Since I only know of one person named Bartholemew (and he has two sisters, Maggie and Lisa, so he doesn't affect the odds in this problem), the approximation is pretty good in this case. Andy Latto andy.latto(a)pobox.com > > I learned this gimmick (giving the boy a name) from Charles Grinstead > or Peter Doyle (I'm not sure which). > > Jim Propp >

2 1

[math-fun] misplaced concreteness
by James Propp 13 Jun '06

13 Jun '06

> "A family has two children, at least one of whom is a boy; what > is the probability that both are boys?" When I teach this material, I tell the students that one standard version of the question -- "A family has two children, one of whom is a boy; what is the probability that the other one is a boy?" -- is too incoherent to have a clear answer. The first half of the question seems to be saying "at least one of the children is a boy", but if so, then the second half commits the fallacy of misplaced concreteness by talking about a boy in particular. Another instance of misplaced concreteness is the fiction of an average person, an average family, etc. One can devise a situation in which the average family has four children, but the average child has five siblings! (Posit a three-family house: two of the families have 2 children each, and the third family has 8 children.) Or, say I have two cars, one of which gets 10 miles to the gallon and the other of which gets 40 miles to the gallon. Then my "average car" goes 25 miles on a gallon of gas, but uses 1/16 of a gallon per mile! Jim Propp

3 2