February 2012 - mathfun@mailman.xmission.com

[math-fun] Warren D Smith video lecture: How I broke AES -- if I did it
by Warren Smith 10 Feb '12

10 Feb '12

hmm. Did not realize I'd been videod+internetted. Hope it came out well. The paper that lecture was based on, can be read here: http://rangevoting.org/WarrenSmithPages/homepage/works.html paper#100 and it described what I called an alleged "nonconstructive break" of the AES cryptosystem. Later an alleged "genuine break" of AES was produced: http://research.microsoft.com/en-us/projects/cryptanalysis/aesbc.pdf but both theirs and mine have no real practical impact. My paper however also cited a "(cheating) break" of AES by Daniel J. Bernstein which I think is very serious practically speaking.

2 1

[math-fun] Modelling human skill ...
by Guy Haworth 10 Feb '12

10 Feb '12

Arpad Elo suggested that a 200-pt rating difference on the ELO chess scale should mean that the higher-rated player's expected score in a game should be 0.75 and the lower-rated player should expect 0.25. Not sure that translates to a probability of the poorer player winning of 1 in 4. The appropriate cumulative distribution or logistic distribution curve can be consulted to see what the expectations are for larger Elo differences. Elo ratings are calculated on the basis of competitive results. In contrast, my work with Giuseppe Di Fatta and Ken Regan ranks players on the basis of their choice of moves. q.v. http://centaur.reading.ac.uk/view/creators/90000763.default.html and in particular ... (working backwards) ... http://centaur.reading.ac.uk/23800/, http://centaur.reading.ac.uk/19778/, http://centaur.reading.ac.uk/4517/, ... Maybe worth mentioning at this point the concept of 'Fischer Distance': Anyone who has beaten Fischer at chess has Fischer-distance 1 Anyone who has beaten someone who has beaten Fischer has Fischer distance 2 (or less), etc. Guy Haworth

2 1

Re: [math-fun] Vague question about modeling human skill at specific activities
by Bill Gosper 10 Feb '12

10 Feb '12

TomR>I think the number of "levels" depends largely on how much variance we expect in performance from game to game, and how much the game counteracts that variance through "repeated measurement". >In Go, for instance, there are a lot of moves, and the poorer player thus has many more opportunities to make the mistakes that the stronger player can exploit. (I believe Go has many many more levels than almost any other board game.) >In the 50 meter dash, there is probably very little variance and thus one would also expect many levels. >In heads-up Texas Hold'em, on the other hand, the cards themselves introduce a far amount of variance, so there are probably fewer levels. >Tennis I know very little about; how hard is it for a random punter to steal a game from a much superior player? Elwyn Berlekamp (world class) says that your level in Dots & Boxes is how many theorems you know. TomR>Things get fun when the "is-better-than" relation is not transitive; here, linear rating systems start to fail. >From personal experience in club-level table tennis, intransitivities are a fairly common consequence of incomplete "skill vectors" (e.g., loop, chop, sidespin, power, mobility,...), with the usual problem (e.g., Efron dice) of comparing incomparable vectors. This is also why the idea if IQ is bogus. --rwg On Fri, Feb 10, 2012 at 10:19 AM, <rcs(a)xmission.com> wrote: > I'll add one more vaguely-specified question to Thane's list: > He estimated that the spread of tennis skill is at least six > steps of 'near certain victory', and maybe much higher. > > What's the story for other games? > > I think Chess has a smaller spread: IIRC, 400 Elo rating points > is one Plambeck step, and the Elo spread is 1200 - 2900, only > 4.25 Pbk. I'll guess that Go has a bigger spread, while > soliciting more information from real players. > > Rich > > ---------- > > Quoting Thane Plambeck <tplambeck(a)gmail.com>: > >> I'd welcome pointers to statistical models of the following >> vaguely-specified situation >> >> I play tennis. There are probably plenty of people who also play >> tennis whom I could defeat, if they were chosen at random amongst all >> players who know how to play and have a racket. >> >> However, I could easily point to a tennis player X whom I would little >> chance (essentially zero) of defeating. (S)he in turn could point >> to a player Y with the same property. And Y could point to player Z. >> >> I'm sure that for a middling tennis player such as me, there must be >> at least five levels, and perhaps many more, of players with this >> transitive "I'd have little chance of defeating that person" property >> >> Eventually we'd reach Novak Djokovic at the top of the world tennis >> rankings. There are probably only ten players who have any >> reasonable chance of beating him in a match today. >> >> What I'm looking for is a statistical model of such a situation, which >> I view as somewhat in common in competitive sports. The closest >> thing I can think of is the ELO chess rating system. >> >> I'm interested in answering questions like this. >> >> Say I have two randomly chosen worldwide tennis players X and Y. >> Let's say X defeats Y twice in two matches. What is the chance X >> will defeat Y in a third match, if no other information is provided? >> >> I'm also interested in (again vaguely-defined) "churn" parameter (ie >> the mixing of player skill levels over time). For example, in chess >> it seems to be possible for a player to play at specific level for >> many years. In tennis, most players begin to fade by their thirties >> if not sooner

1 0

[math-fun] random k-element subsets in sublinear time
by Warren Smith 10 Feb '12

10 Feb '12

Task: Produce one of the Binomial(n,k) k-element subsets of an N-element universe uniformly at random. It's pretty easy to figure out how to do that in O(k) steps if 0<k<=n/2, e.g. j=0; i=0; LoopForever{ if( rand01()*n <= k ){ k--; A[j]=i; j++; if(k==0){ return(); } } i++; n--; } will generate the k-element sorted subset A[0]<A[1]<A[2]<...<A[k-1] of {0,1,2,...,n-1}. A more interesting task, which I have not seen before, is to do this in sublinear time. Of course that is only possible with wordwide parallelism. So on a 64-bit machine, if 0<=k<=n<=64, how do we generate a random word whose first n bits contain k ones? We assume computer can do "popcount," "and" and "or" instructions on words in 1 step. Elegant solution: /** This routine, given two 64-bit words L and U, where L is a subset of U (that is, (L and U)==L) and a number k with popcount(L)<=k<=popcount(U), will output a word X which is a random subset of U and superset of L having popcount(X)=k. You can call with L=0 to make a random k-element subset of U, and call with U=complement(0) to get random k-element subsets of 64-element universe. The runtime is O(log(1+popcountU-popcountL)) in expectation. **/ uint64 RandomSubset(int k, uint64 L, uint64 U){ int p; uint64 X; if( k <= popcount(L) ) return(L); if( popcount(U) <= k ) return(U); LoopForever{ X = (randword() and U) or L; p = popcount(X); if( k == p ) return(X); if(k<p){ U=X; }else{ L=X; } } }

1 0

[math-fun] Vague question about modeling human skill at specific activities
by Thane Plambeck 10 Feb '12

10 Feb '12

I'd welcome pointers to statistical models of the following vaguely-specified situation I play tennis. There are probably plenty of people who also play tennis whom I could defeat, if they were chosen at random amongst all players who know how to play and have a racket. However, I could easily point to a tennis player X whom I would little chance (essentially zero) of defeating. (S)he in turn could point to a player Y with the same property. And Y could point to player Z. I'm sure that for a middling tennis player such as me, there must be at least five levels, and perhaps many more, of players with this transitive "I'd have little chance of defeating that person" property Eventually we'd reach Novak Djokovic at the top of the world tennis rankings. There are probably only ten players who have any reasonable chance of beating him in a match today. What I'm looking for is a statistical model of such a situation, which I view as somewhat in common in competitive sports. The closest thing I can think of is the ELO chess rating system. I'm interested in answering questions like this. Say I have two randomly chosen worldwide tennis players X and Y. Let's say X defeats Y twice in two matches. What is the chance X will defeat Y in a third match, if no other information is provided? I'm also interested in (again vaguely-defined) "churn" parameter (ie the mixing of player skill levels over time). For example, in chess it seems to be possible for a player to play at specific level for many years. In tennis, most players begin to fade by their thirties if not sooner -- Thane Plambeck tplambeck(a)gmail.com http://counterwave.com/

6 6

[math-fun] "Cylindrical" chess ?
by Henry Baker 10 Feb '12

10 Feb '12

In thinking about "continuous" chess, I started thinking about pawn lines as a continuous line across a board of width 8 units. I then started thinking about Fourier transforms of that line, and it seemed natural to paste the left chess board boundary to the right one (without a twist!) -- hence a cylindrical chess board. (It makes a lot less sense to consider a toroidal chess board for a number of reasons.) I think thought -- let's go back to the "regular"/discrete chess board & consider a cylindrical board with the left & right boundaries pasted together. What do the chess moves look like? Pawns on either the left or right boundary can attack the other boundary. Bishops' diagonal lines extend beyond the left & right boundaries & continue on the other side. Knights aren't trapped next to the left & right boundaries, but can jump across them. A rook can attack a piece from both sides, if it and the other piece are the only ones on its rank! A Queen can also attack from both sides on its rank, as well as follow diagonals like bishops. A King can't be pinned against one of the sides of the chess board, although it can still be pinned against the top or the bottom. Q: Is cylindrical chess still pretty even for white & black? I can imagine that the answer is still yes, because while all the pieces have a bit more freedom, so does the King, so it is harder to trap him. Perhaps there would be a larger number of draws?

2 1

[math-fun] Turning discrete games into continuous games ??
by Phil Carmody 10 Feb '12

10 Feb '12

From: Henry Baker > Are there any examples of an obviously discrete game -- > e.g., tic-tac-toe, checkers, chess, go, etc. -- that can be > converted into a continuous game ? ... > In the case of chess, it is a discretized version of an > obviously continuous game of war, so perhaps a continuous > version might be made. The modern adult game of tiddlywinks was once described by a world champion (and huge chess fan) as "chess on an infinite granularity board", but I suspect the use of "chess" was metonymy for some kind of abstract strategy game. It is a spacially continuous game, but alas it's not exactly analogue to any particular discrete game. It's got a dvonn-like "sit on opponents to trap them" aspect, though perhaps it's more backgammon-like (at least the Greek variant that I prefer to play) in that you can come off and release the opponents that you've trapped. However, unlike those two games there are no limitations where you may attempt to play your piece. Phil

1 0

[math-fun] random numbers.
by Simon Plouffe 09 Feb '12

09 Feb '12

I think this image gives the proper look at it : http://www.random.org/analysis/dilbert.jpg Best regards, Simon Plouffe

1 0

[math-fun] Turning discrete games into continuous games ??
by Henry Baker 09 Feb '12

09 Feb '12

Are there any examples of an obviously discrete game -- e.g., tic-tac-toe, checkers, chess, go, etc. -- that can be converted into a continuous game ? The first goal might be to make time continuous, and a subsequent goal might be to make space continuous. Making time continuous is a problem, because how do the two sides "take their turn" ? But "taking turns" is really a discrete version of continually synchronizing time between two agents. In the case of chess, it is a discretized version of an obviously continuous game of war, so perhaps a continuous version might be made.

6 6

[math-fun] Limit puzzle (Was: (further) generalized Lambert series with Theta-convergence)
by Bill Gosper 09 Feb '12

09 Feb '12

On Wed, Feb 8, 2012 at 12:01 AM, Bill Gosper <billgosper(a)gmail.com> wrote: > Puzzle: Assuming[0 < q < 1, > Limit[QPochhammer[a*c, q]/QPochhammer[b*c, q], c -> \[Infinity]]] > > Or maybe Assuming[0 < q < 1, > Limit[QPochhammer[a*x, q]* > QPochhammer[b*x, q]/QPochhammer[c*x, q]/QPochhammer[a*b*x/c, q], > x -> \[Infinity]]] > Wisely, no one touched this. Obviously, for a,b,c >0, the limit doesn't exist. For typical numbers, the plot from x=9^69 to 9^70 resembles cot(sqrt x), i.e. poles at decreasing frequency. For a,b,c <0, things are less clear. For huge x (~9^99) there is a persistent, smooth, tiny ripple of decaying frequency and amazingly slowly decaying amplitude. Mma's plot seems to show the sudden disappearance of this ripple as q increases beyond some threshold, but this is an artifact. At least in 8.04, Plot[QPochhammer[a*x, q]*QPochhammer[b*x, q]/QPochhammer[c*x, q]/QPochhammer[a*b/c*x, q] - 509719561642/10^12 /. {a -> -1/2, b -> -1/2, c -> -1/4, q -> 25/51}, Evaluate[N[{x, 9^96, 97}, 105]]] shows just the tips of these ripples, with the rest of the wave clipped to 0. Assuming the ripples eventually die, converting the limit to a bilaterally infinite product suggests the answer is Assuming[0 < q < 1&&a<0&&b<0&&c<0, Limit[QPochhammer[a*x, q]* QPochhammer[b*x, q]/QPochhammer[c*x, q]/QPochhammer[a*b*x/c, q],x -> Infinity]] == ((QPochhammer[a, q] * QPochhammer[b, q] * QPochhammer[q/a, q] * QPochhammer[q/b, q])/ (QPochhammer[((a * b)/c), q] * QPochhammer[c, q] * QPochhammer[q/c, q] * QPochhammer[((c * q)/(a * b)), q])) Testing, In[56]:= N[% /. {a -> -1/2, b -> -1/2, c -> -1/4, q -> 25/51}] Out[56]= 0.509719561642272 in agreement with the offset in the clipped plot. --rwg As for that QPochhammer generating function, Mma does nothing with FunctionExpand[QHypergeometricPFQ[{x, q}, {0}, q, t] == Sum[QPochhammer[x, q, n]*t^n, {n, 0, Infinity}]] and yet it knows the q-binomial thm: In[55]:= FunctionExpand[QHypergeometricPFQ[{x}, {}, q, t] -> Sum[QPochhammer[x, q, n]/QPochhammer[q, q, n]*t^n, {n, 0, Infinity}]] Out[55]= QPochhammer[t x, q]/QPochhammer[t, q] -> QPochhammer[t x, q]/QPochhammer[t, q] So maybe that simple-looking g.f. is unknown.

1 0