April 2013 - mathfun@mailman.xmission.com

[math-fun] how many records?
by Warren D Smith 16 Apr '13

16 Apr '13

Here's a cute and useful fact. Let S be a set of N numbers. Permute them into random order. Scan thru the elements in that order. Each time you encounter a new record max, ring a bell. So for example, if S={7*,8*,5,3,4,9*} you would ring the bell 3 times at the *s. EASY CLAIM: expected number of times the bell rings, equals HarmonicNumber(N) = 1+1/2+1/3+...+1/N. HARDER QUESTIONS, which I have not looked at: What about the variance? What about tail bounds? Can you write a formula for the whole probability distribution for the number of bell-rings: Prob(R) = xxx?

4 5

[math-fun] April Fool from Euclid and Mma
by Bill Gosper 16 Apr '13

16 Apr '13

In[1472]:= {Re[#], Im[#]} & /@ (I^(1/4 + Range[8]/2)) Out[1472]= {{Sin[\[Pi]/8], Cos[\[Pi]/8]}, {-Sin[\[Pi]/8], Cos[\[Pi]/8]}, {-Cos[\[Pi]/8], Sin[\[Pi]/ 8]}, {-Cos[\[Pi]/8], -Sin[\[Pi]/8]}, {-Sin[\[Pi]/8], -Cos[\[Pi]/ 8]}, {Sin[\[Pi]/8], -Cos[\[Pi]/8]}, {Cos[\[Pi]/ 8], -Sin[\[Pi]/8]}, {Cos[\[Pi]/8], Sin[\[Pi]/8]}} In[1473]:= Graphics[Polygon[%]] makes a STOP sign. But I'm in a hurry. Can't I just get a YIELD sign (equilateral triangle) with In[1474]:= Graphics[Polygon[%% /. 1/8 -> 1/3]] ?-) --rwg

1 0

[math-fun] how many records?
by Warren D Smith 16 Apr '13

16 Apr '13

> Let S be a set of N numbers. > Permute them into random order. Scan thru the elements in that order. > Each time you encounter a new record max, ring a bell. > So for example, if S={7*,8*,5,3,4,9*} > you would ring the bell 3 times at the *s. > > EASY CLAIM: > expected number of times the bell rings, equals > HarmonicNumber(N) = 1+1/2+1/3+...+1/N. > > HARDER QUESTIONS, which I have not looked at: > What about the variance? What about tail bounds? > Can you write a formula for the whole probability distribution > for the number of bell-rings? --ok, thanks to Victor Miller's hint, we have expected # bell rings = ha(N) = 1 + 1/2 + 1/3 + ... + 1/N. probability of exactly R rings = |s(N,R)| / N! where s(N,R) = Stirling Numbers of the first kind. variance of #bell rings = SUM(R=0..N)OF [R-ha(N)]^2 * |s(N,R)|/N! Of course, when N is large, ha(N) approaches ln(N)+gamma where gamma= 0.5772156649 is the Euler-Mascheroni constant. The variance appears numerically to approach ha(N)-1.645 which if so would mean that the probability distribution is sharply peaked around its expectation, e.g. when N--> infinity the probability-->100% that #bellrings lies within the interval [0.999, 1.001]*ha(N). That's remarkably predictable.

2 2

[math-fun] Sequence of polynomials with largest real root approaching e?
by Warren D Smith 16 Apr '13

16 Apr '13

Mike Stay wants polynomials p_n(x) of degree n so that 1. p_n(x) is degree n 2. p_{n+1}(x) = x * p_n(x) + k_n, where k_n is an integer 3. Largest real roots approach e as n -> infinity. --I argue that such polynomials exist, not only for e=2.71828..., but in fact for ANY desired real number e>1. Clearly, if e=A^(1/B) for any integers A,B>0 one can hit it exactly using the polynomial x^B - A. Then all subsequent k_n=0 so you stay there forever after. These numbers seem obviously dense within the reals>=1 (one can in fact prove that by showing within any subinterval one exists...) so you clearly can approximate any e>1 as closely as you like. However that is not quite good enough to satisfy Stay's desire. But let us say you have found some A,B>0 giving you accuracy 10 decimals and yielding a number slightly BELOW e. Now you can find C,D>0 so that x^C * (x^B-A) - D gives you accuracy 100 decimals and still below e. Then find E,F>0 so x^E * [x^C * (x^B-A) - D] - F gives you 1000 decimals... still below e... etc. I claim it is fairly obvious that you can keep doing this forever (a full proof would need various details here... which I omit since I am lazy...). So the answer to Stay's question is "yes." -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

2 1

[math-fun] A grid with MAX (dynamic programming solution?)
by Warren D Smith 16 Apr '13

16 Apr '13

RCS expressed doubt WDS's dynamic programming algorithm would actually work. --WDS: oh dear. Not quite as simple as I at first thought. The algorithm makes a table of all subgraphs of the graph. (The original problem used the king-adjacency graph in a chessboard.) There are 2^V subgraphs for a V-vertex graph. Actually with fixed startpoint, you only need subgraphs including it (2^(V-1)) and if the graph has symmetries then further savings possible, and only doing connected subgraphs is another saving,... For each subgraph, original plan was to tabulate the max attainable entry in it. However, this is not good enough. Really, you'd need to tabulate much more. The whole algorithm concept seems to break, or become impractical.

1 0

Re: [math-fun] how many records?
by Adam P. Goucher 16 Apr '13

16 Apr '13

Warren, It's Question 10 on the Part IA Probability sheet 2, therefore well known: http://www.statslab.cam.ac.uk/~frank/PROB/sheet2.pdf Sincerely, Adam P. Goucher http://cp4space.wordpress.com > ----- Original Message ----- > From: Warren D Smith > Sent: 04/16/13 05:13 PM > To: math-fun(a)mailman.xmission.com > Subject: [math-fun] how many records? > > Here's a cute and useful fact. > > Let S be a set of N numbers. > Permute them into random order. Scan thru the elements in that order. > Each time you encounter a new record max, ring a bell. > So for example, if S={7*,8*,5,3,4,9*} > you would ring the bell 3 times at the *s. > > EASY CLAIM: > expected number of times the bell rings, equals > HarmonicNumber(N) = 1+1/2+1/3+...+1/N. > > HARDER QUESTIONS, which I have not looked at: > What about the variance? What about tail bounds? > Can you write a formula for the whole probability distribution > for the number of bell-rings: > Prob(R) = xxx? > > _______________________________________________ > math-fun mailing list > math-fun(a)mailman.xmission.com > http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

1 0

[math-fun] Sequence of polynomials with largest real root approaching e?
by Mike Stay 16 Apr '13

16 Apr '13

Is there a sequence of polynomials p_n(x) such that p_n(x) is degree n p_{n+1}(x) = p_n(x) + k_n and the largest root of p_n approaches e as n -> infinity? -- Mike Stay - metaweta(a)gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com

2 3

[math-fun] A grid with MAX
by Warren D Smith 15 Apr '13

15 Apr '13

The problem can be generalized to arbitrary graphs instead of the 2D grid graphs (with or without starting point specified). It was claimed the 6x6 grid is not feasible to solve. I claim it is feasible to solve. Use "dynamic programming," tabulating the max on every (king-connected?) subgraph of the original graph which includes the startpoint. For a 6x6 grid graph this would require a table with 2^35 = 32 billion entries, but if you have enough memory for that, then it should be feasible to solve it pretty quickly, I would guess in <=10 minutes. (Also you can trade off space for time in some hopefully obvious ways if this is a bit too much memory.)

2 1

[math-fun] 3D printing of mathematical objects ??
by Mike Stay 09 Apr '13

09 Apr '13

Google Sketchup comes with a scriptable interface and can export to STL files. I don't know if it would be easier to generate the STL files directly. http://www.cerebralmeltdown.com/cncstuff/stl/index.htm http://www.youtube.com/watch?v=FALvwBN5-hc -- Mike Stay - metaweta(a)gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com

1 0

[math-fun] Generating function for inverse catalan numbers?
by Mike Stay 09 Apr '13

09 Apr '13

The ordinary generating function for the Catalan numbers {C_n} is (1-sqrt(1-4z))/2z. How would I go about finding the OGF of {1/C_n} ? -- Mike Stay - metaweta(a)gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com

1 1