March 2016 - mathfun@mailman.xmission.com

[math-fun] Ray Tomlinson, 74
by Mike Beeler 08 Mar '16

08 Mar '16

Ray Tomlinson died Saturday at his home in Lincoln, Massachusetts. He was 74. He studied at RPI and MIT, and worked at BBN until his death. He is especially famous as the inventor of email, and for choosing the at-sign in email addresses. He also worked on many other computer projects. I worked with Ray at BBN. A few years ago I phoned him to ask about something. I told him I am retired, and asked whether he was thinking of retiring. No, he said, he wanted to keep working as long as he could. http://www.nytimes.com/2016/03/08/technology/raymond-tomlinson-email-obitua… <http://www.nytimes.com/2016/03/08/technology/raymond-tomlinson-email-obitua…> — Mike

3 2

[math-fun] How good are "Galois Hash" functions as hash functions?
by Henry Baker 07 Mar '16

07 Mar '16

[I apologize for this possible duplicate: I was inadvertently disconnected from math-fun for the past few weeks, so I missed any answers.] So-called "Galois Hash" ("GHASH") functions are used in some MAC codes today, and run reasonably fast due to new instructions on Intel & other processors. To a zero-th order approximation, GHASH(k,M)=M(k), where M is a vector of polynomial coefficients, M(k) denotes polynomial evaluation of M(x) at x=k, for secret key k, and algebra is performed over various interesting rings. (I'm purposely staying away from the actual NIST GHASH, because it has been optimized in a number of ways for both security and performance that I'm not worried about for the purpose of this email.) Since the "message" is encoded in the poly coefficients, we have a huge amount of machinery to bring to bear in any analysis, all the way up to and including FFT's. Depending upon the chosen ring, these poly coefficients might be fixed-size blocks of bits from the message. So how good are these types of hash functions in performing hashes such as the kinds of things that SHA1 & SHA-256 are used for -- e.g., detecting changes in movie-length (4 GByte) files ? For my purposes right now, I'm not at all worried about CPU performance, but performance in the sense of detecting changes, given a particular number of hash output bits.

2 1

[math-fun] This is just a test
by Henry Baker 07 Mar '16

07 Mar '16

If it weren't a test, you would not have received this message.

1 0

[math-fun] testing coins (and actresses and bishops?)
by Warren D Smith 06 Mar '16

06 Mar '16

> From: Eugene Salamin <gene_salamin(a)yahoo.com> > That's a complete misrepresentation of what I said. The number N of tosses > is not fixed.? You can toss all you want, until your decision procedure > returns fair, unfair, or undecided. > > ? --? Gene --if you, say, apply your test for some N, then 2N, then 4N, then 8N, ... (or maybe N+1, N+2, N+3,...; whatever), until some test says "unfair", then that was not a legitimate testing procedure in the sense that the claimed confidence will be incorrect. Any repeated test whatever, where individual test has confidence C of being right, and you repeat until get some sought result, will no longer have confidence C for that result. Repetition of tests ruins confidences. This is a well known banana peel in statistics. Now you could try to correct for that by altering confidences to try to restore safety, but then you'd be inefficient. Or you could not-do that, in which case you'd be incorrect. So hopefully you now see why I want a procedure designed from the start to involve N continually incrementing, and with confidences correctly based on the failed-termination probability from that whole infinite sequence of experiments.

3 4

Re: [math-fun] coin tossing forever until you die
by Warren D Smith 06 Mar '16

06 Mar '16

It is correct that, if handed a truly-fair coin, then any tester of fairness would need to keep tossing it forever and would never be able to announce it is fair. Of course, any such test is necessarily at best one-sided, meaning it can detect unfair coins (and it should do so with probability=1) but it can never detect fair coins. It can and will make 1-sided errors, i.e sometimes branding truly-fair coins as unfair. But by design of the test we can make that 1-sided error probability be <=K for user-specified K>0. Re somebody criticizing me criticizing Salamin's coin test -- well, my criticism had asked him whether his intended scheme was really the one I refuted. He has not responded to my question, so far.

2 1

[math-fun] Salamin's "Bayesian" coin-tester
by Warren D Smith 06 Mar '16

06 Mar '16

> From: Eugene Salamin <gene_salamin(a)yahoo.com> > It's beginning to look like we don't agree on what Bayesian analysis is. I'm > saying that the posterior probability after n tosses updates and supersedes > the posterior after k < n tosses.? The posterior provides everything that > can be known about x, the probability that the coin comes up heads.? Bayes > can't tell you if the coin is fair; that's for you to decide knowing the > posterior. > > ? --? Gene --so: your idea is this(?): initial ("prior") distribution of the coin-bias x is uniform on (0,1). After T+H coin tosses, the posterior is a beta(1+T,1+H) distribution on (0,1). One keeps tossing coins and as we do so the posterior keeps changing. If at any moment the CDF of the beta(1+T, 1+H) distribution at 1/2, is either less than K/2 or greater than 1-K/2, then we stop and declare "coin appears unfair, with confidence>=1-K." Is that right? If so, that was wrong. Why? Well it is good in the sense that if the coin were unfair, then this test would (with probability=1) ultimately indeed terminate and say so (regardless of the K with 0<K<1). But it is no good in the sense that if the coin genuinely were fair, then by the "law of iterated logarithm" with probability=1 an infinite number of days will come, during which |T-H| > sqrt(1.99 * N * lnlnN) where N=T+H. Therefore, it is guaranteed (with probability=1) this procedure will terminate and announce the coin is unfair. Regardless of the value of K with 0<K<1. Because (in Wolfram notation) Beta[ 1/2, N/2-Sqrt[N*0.49*Log[Log[N]]], N/2+Sqrt[N*0.49*Log[Log[N]]] ] goes to 0 when N-->infinity. Here is a table for N=10^k k | Beta value 1 | 0.00369675 2 | 1.73794*10^-30 3 | 9.6119*10^-302 4 | 2.1738412136*10^-3011 5 | 1.715030375*10^-30104 6 | 6.5603975*10^-301032 7 | 2.6446880*10^-3010302 8 | 2.344465*10^-30103002 9 | 6.6534*10^-301029999 In short: this procedure always claims coin is unfair, whether it is or not. After 10^9 tosses it typically will report enormous confidence a fair coin is unfair, like 0.9999...9 with about 300 million nines. The root cause of the problem here was the standard "repeated test banana peel" that I'd mentioned previously.

4 5

[math-fun] How good are "Galois Hash" functions as hash functions?
by Henry Baker 05 Mar '16

05 Mar '16

So-called "Galois Hash" ("GHASH") functions are used in some MAC codes today, and run reasonably fast due to new instructions on Intel & other processors. To a zero-th order approximation, GHASH(k,M)=M(k), where M is a vector of polynomial coefficients, M(k) denotes polynomial evaluation of M(x) at x=k, for secret key k, and algebra is performed over various interesting rings. (I'm purposely staying away from the actual NIST GHASH, because it has been optimized in a number of ways for both security and performance that I'm not worried about for the purpose of this email.) Since the "message" is encoded in the poly coefficients, we have a huge amount of machinery to bring to bear in any analysis, all the way up to and including FFT's. Depending upon the chosen ring, these poly coefficients might be fixed-size blocks of bits from the message. So how good are these types of hash functions in performing hashes such as the kinds of things that SHA1 & SHA-256 are used for -- e.g., detecting changes in movie-length (4 GByte) files ? For my purposes right now, I'm not at all worried about CPU performance, but performance in the sense of detecting changes, given a particular number of hash output bits.

1 0

[math-fun] Minsky memorial events at Stanford and MIT
by Mike Beeler 05 Mar '16

05 Mar '16

For those who knew (or wish you had) Marvin Minsky, there are two remembrance events, one at MIT on Thursday March 17, and one at Stanford on Tuesday March 22, details below. - - - - - Received from Henry Lieberman ( lieber(a)media.mit.edu <mailto:lieber@media.mit.edu> ) : There will be a memorial event for Marvin at the MIT Media Lab, 75 Amherst St., Cambridge, 17 March 2016, 3-9p. - - - - - Received from Ted Selker ( ted.selker(a)gmail.com <mailto:ted.selker@gmail.com> ) : Marvin Minsky Remembrance at AAAI Spring Symposia Building 420 room 040 (Jordan Hall) Stanford University Tuesday March 22, 2016, 7 PM - 9 PM Open to all This Symposium is organized to give a place for people who knew and learned from Marvin Minsky’s work to share memories of how he touched them. We will focus on some of the specialness he shared: - Personal / relationship stories that teach us how to think, do research and play with others - Professional experience stories of getting inspiration from Marvin - Scientific stories that tell what Marvin accomplished - Historical stories that help us understand legacy and paths that occurred Ted mentions he "will give special time for people that really had relationships with him on the schedule”, from which I take it he is running the event, and if you have a special story you want to share, maybe you should contact him. - - - - - — Mike

1 0

[math-fun] coin-toss reply to M.Stay re wikipedia & Salamin
by Warren D Smith 05 Mar '16

05 Mar '16

Wikipedia's coin fairness test uses one fixed N. So does Salamin. Therefore it is incapable of detecting unfairnesses which are too small. The only way to do that is to use unboundedly large N, keep tossing coins literally forever until some test passes. If you are going to do that, then take the attitude you are going to do that, and design the best criterion you can. Not a criterion for one particular N, a criterion designed for re-use throughout an unbounded and a priori unknown number of tosses, and without hurting either correctness or efficiency. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

3 2

[math-fun] how to test whether a coin is fair
by Warren D Smith 04 Mar '16

04 Mar '16

The definition of a "fair coin" is exactly 1/2 probability of heads and of tails. No "opinion" is involved. I am allowing you to assume all coin tosses are truly independent. Clearly, an unfair coin, no matter how tiny its unfairness, could be detected with confidence 1-K, for given K as small as one would like, after a large enough number of tosses. A fair coin, however, could never be proven fair, and then the testing procedure will simply keep going (or, with probability<=K, terminate and wrongly report coin is unfair -- that is what "confidence" means). Gene Salamin's remark about using another (H,T) is not correct, or at least highly inefficient, because previous experiment was subset of new experiment, and his formulas ignore that. So the question is a simple one: how should we best test the fairness of a coin? (With some specified confidence?) But it is not so easy to answer. In fact so far no math-funner besides me even seems to have comprehended the question... But I believe there probably is a unique answer, i.e. a uniquely optimal statistical test, and have sketched how to characterize that answer as a certain constrained variational problem. This characterization is unsatisfying as matters presently stand.

6 7