Barry Mazur as an Applied Mathematician
Diaconis, Persi
Mathematicians are sometimes asked to help ‘outsiders’with applied problems. I'll report three of Barry's deviations in this direction. The first is about shuffling cards (OK, OK and random walk on finite groups of Lie type). The second is about wanderingaround on the streets of Paris (OK and random walk with reinforcement and the sigma model). The third is about Tomography (OK there IS an elliptic curve).
 So of all the accolades we've heard, wonderful things we've heard about Barry, applied mathematics I don't think has been mentioned in the first bunch of talks. And the theme of this talk is the following. Anybody who does mathematics, no matter how focused, no matter how abstract, runs into outsiders. And you're at a faculty meeting, you're at a dinner, and some chemists are social scientists, who you're a mathematician, I have a question. Can I ask you, and every once in a while you get interested and do a little something, and some applied math comes out of it. It's hard of course to, how do you keep track of somebody's output in that dimension. And I'm going to take advantage of the fact that the outsider that asks Barry the things that I'm going to talk about is me. So over close to 50 year period, I've talked to Barry, we're friends and talk about all kinds of things. And I tricked him, whatever, into thinking about various things, and I'm going to tell you three of them. And these are three stories. The first is about shuffling cards. And that's going to be my favorite story about stories. And the second is about the books of Plano. And the third is about walking on the streets of Paris. And okay, so most of my mathematical adventures start with some real world problem. And let me set the scene for the first instance. So I was working at Bell Labs, and I was trying to figure out the optimal strategy in a certain card game. And it was much too complicated to solve or get to the end of it. So we were doing it by simulation. Try to make certain choices in how many cards each point is worth, and then have it play against itself and optimize, that sort of thing. And so in order to do that, we needed lots and lots of random permutations of 52 cards. Let me remind you how you generate a random order in the deck of cards. Suppose you had 52 cards as memory registers or in a stack. Then you get the computer to generate a random number between 1 and 52, say 17, and you transpose cards 1 and 17. And then between 2 and 52, say 5, and you transpose 2 and 5. Then between 3 and 52, maybe 3, so you do nothing to 3, etc. So you do that, and assuming that the random number generator works, or that you're happy with that, that generates a random permutation, right? Because any card can be on top, and then any card next, etc. OK, so we ran the simulations, and they took, well, I don't know, 30 hours of CPU time on big machines. So it was a lot of effort. And after that was all done, and we're looking at something was wrong. I don't know what does it mean something is wrong when you're looking at pages and pages of simulations, but something was wrong. Something wasn't monotone. And so we start looking at the code. I mean, there's no more painful thing to do than that, looking at somebody else's code. And after two days, I sent to the lady, Mary, and get over there, well, I'm desperate. How did you generate your random permutations? And she said, oh yeah, you said that fussy thing, transpose random with 1 random. She said, I made them more random. I transpose random with random. And I said, ha. And you have to redo the simulations. You have to rerun the code. And she actually cried, I remember, and said, you know, but it can't make any difference. She went to her boss, and he went to his boss, and he came down and yelled at me, your mathematicians are crazy. You know, she did 100 random transpositions. That has to be enough to mix up 52 cards. And so I really wanted to know the answer to the question, how many random transpositions does it take to mix up 52 cards? I mean, that's the background for this story. And so just to put it in context, so you're with me. So suppose a deck of cards starts out on the table, 1 up to 52 in order of card 1, card 2 up to 52. You pick a card at random with your left hand, you pick a card at random with your right hand, and you switch them. And you do that a lot. And you allow your left hand to equal your right hand, because otherwise there'd be a parity problem after an even number of switches would be in an even position. And I want to know how many transpositions does it take to mix up cards. In my instance, the lady did 100. The first time that the Bridge League went from hand shuffle cards to computer shuffle cards, they did 60 random transpositions. Not knowing the usual algorithm. How many does it take? So let me make math of that for a second. So I'm working on all permutations of N is 52. And the probability thing that I just waved my hands about, you can code it up this way. It's a probability distribution. The probability of a permutation sigma is, well, 1 over N of sigma is the identity, and it's 2 over N squared if sigma is a transposition, and 0 otherwise. That's my basic step in my switches. And then repeated transpositions we model as convolution. So I write it down just for a second p star p of sigma. The chance of being at a given arrangement of a deck of cards after shuffling twice is equal to the sum of p of eta p of, I guess, it's sigma a. Here summed over eta. So that's just ordinary convolution. And p star k of sigma is the chance of being at the arrangement sigma after k switches. So there I've written it down. And then there's the uniform distribution u of sigma, which is 1 over N factorial. All permutations equally likely. And I want to know how large this, well, Pankeray actually was the first one to show. The 1890s that p star k converges to u. And k gets large, which just says if you shuffle a deck of cards a lot, it gets all mixed up. And you already knew that. And I want to know how fast. And so in order to tell you that, I have to say one more definition, stop for a second too. And so the distance between shuffling k times and uniform, this is one good way of defining it. P star k of a minus u of a. And maximum over a in Sn. And so here's what this says. A is some set of arrangements of the deck of cards. Maybe all arrangements of the deck of cards with the ace of spades is in the top half. And p star k of a is what's the chance that the deck is in that set of arrangements after k shuffles. And u of a is if the cards are perfectly mixed, what's the chance? Take the difference between those two numbers and then you take the worst case of that. That's the distance that we often use, total variation. And with all of this specified, there's now a math problem, finally. Given epsilon bigger than zero, how large k, except so that the distance of k is, you know, the distance of k is less than epsilon. That's now a math problem. And. I have a question. What about just choosing one part of it and putting it in for choosing? There are a lot of algorithms for generating a random. Does that work? I don't want to answer that right now. I'd be happy to discuss it offline. Not the right time for that question, but I'd be happy to discuss. There are lots of algorithms. I just try to say the standard one. I'm just wondering why it doesn't matter if you've got a system. Well, I don't know either, but I told you the one that they used. So that's yet another question. So with Miradat Shashahani, another longtime friend of Barry's, we figured this out. And the way theorem comes out is this way. If k is one half n log n plus cn, c is bigger than zero. I'll explain this. Then the distance of shuffling to random is less than or equal to 2 e to the minus c. And this c is the same as this c. And what that means, well, that means if you want to know how many times to shuffle to make this less than 1 in 100, you write equals 1 in 100. You solve for c and then put that into here and that gives you the answer. And there's a lower bound that matches this. So that was a, now if you want to do that, I want to learn how to do this and then learn how to do that. And so that's what a theorem looks like in the subject. I think this was the first such theorem in the sense of a short quantitative bound. And I, in 1985, I gave this same talk in this same room. Barry and David Mumford were interested in having somebody in the math department who knew about combinatorics and probability and asked me to give the job talk. Although I didn't know it was a job talk, but anyway, I did talk about this because I just written it all down. And I should say by the way, the answer's around 400, I mean, or something like that in order to, and we know why it's not random when it's not random. And that did explain the anomalies in our results. And after my talk, Barry, as usual, I saw him talk after talk, came up and said, that was great, and thank you, man, a lot to me, still does. And he said, but the reason your argument works is because the set of transpositions is a conjugacy class in the group. And what you're really doing is taking the element in the group algebra, which is the sub of all transpositions plus the identity, and then raising it to a high power. Well, you could do that for any group, you know, any lead type group. And he was going on and kind of sketching out a program of research. And we're friends, and after about five minutes or something, I said, yeah, but what's the story? Why would anybody care about doing whatever I was just doing on a lead type group? And Barry didn't know what I was talking about. And after another five minutes of my trying to explain, he said, I see. He said, what you don't understand is that in mathematics, somebody else makes up the story. There's some truth to that, and there's a wonderful history. The character theory that I needed in order to prove this theorem was done by Formanius for just the craziest reason. The determinant of a circulant is a product of linear forms in the entries. And I mean, who would care about that? And character theory came out of that. So stranger things have happened now. But Barry's thought stayed with me, even though I told you why I was doing this problem. But I just came. Sometimes takes a while for the ideas to mature. I just came from six months at MSRI, where a group of us are doing exactly what Barry laid out, that is, take a lead type group, say GLM over a finite field, and take a conjugacy class like something like transfections or any conjugacy class. In fact, these are all simple groups, and almost anything will generate. And then you can do the analog, make the random walk. And with a group of very wonderful group theorists who I've corrupted, it's his fault, but I've corrupted them, there's a kind of unifying result which is more or less, but really more or less, that is essentially always. For any lead type group, any conjugacy class, the identity, etc., the rank of the group is necessary and sufficient in order to have things be random. So took a while, but I did finally follow. And I have no idea why we're doing it. It's just the math is nice. And now I want to say, what else do I want to say about this particular thing? Really the reason I told it to you is it is my favorite story about stories, but one thing that came out of this result, just a lot of smart people here, this particular thing, if I graph it. So this is K, the number of shuffles, and this is the distance of p star K minus u, how close we are. And this distance that I'm working in is the difference between two numbers which are between zero and one. So it's between zero and one. And it's zero if the measures are the same, and it's one if the measures are completely distrubly supported, and what this theorem says is something a little surprising. It says that this distance behaves with a sharp cutoff, and this cutoff happens at a half n log n. That's where this cut, that is this going to zero happens in the second term of the asymptotics. So if you were to make a plot, and it's an outstanding conjecture in the field, let me say it twice, take any set of permutations that generate the symmetric group, any wave shuffling that you like, and start shuffling with them. There is a sharp cutoff, that is there is this cutoff phenomena happens for any generating set, and a marvelous development that came from this, we made a theory following what I told you about, which says if you know all about one way of shuffling, if you have very, very sharp answers for one way of mixing things, then you can get good answers for essentially any way of shuffling. It's called comparison theory, and that's now a machine on its own. Using comparison theory, Rijuk, Shirash, and Helfkart, I think an inverse order, proved that you know if you pick two permutations at random, they generate either Sn or An with probability, well, one, and they generate Sn with probability three quarters. So pick two permutations at random, say a transposition in an encycl, but any two permutations, pick two permutations at random. The mixing time is of order NQ blog N, and that's the worst, and we conjecture that there's a sharp cutoff of this sort, and in fact we conjecture it for any set of generators for any finite simple group, but there's just a handful of examples, and this is one of them where we've been able to prove that there are cutoffs, in particular for a transposition in an encycl, we don't know. I believe that there's an explicit constant such that NQ blog N plus C is the right answer, but we don't know. So those are math problems that come from this development. But more than that, it is a typical example of how I get involved in a problem and what happens from it. So that's enough without shuffling cards, and you should be happy because I just finished teaching a graduate course on the mathematics of gambling, and they had to sit through four weeks of shuffling. So this is all you're going to hear about today. So in case you're tired, it's the last thought. Wake up, new talk. So my second story, I want to tell, those of us who've been participating, I hope most of us were lucky enough to have heard Elaine Scarry talk about Plato's poetics on Wednesday. It was just made these wonderful texts come to life. Well, I'm going to talk about Plato. It says it right there for a few minutes. So one of the things that we don't know, so Plato wrote a lot of famous books, the ones that have come down to us, and we don't know what order he wrote them in. So Plato's Republic was written early, Laws was written late, and the others. And it matters if you're a Plato scholar, that is, because he changed his opinion, it matters. If you're trying to interpret, how did he come to? So that's a question how to seriate the books of Plato. And there's been endless articles written about that. Well, he was whilst here and while there, you can imagine the conversations going on and on. And around the late 1950s, a Plato scholar named Brandwood decided to go get some data. And Plato said that he systematically changed his rhyming pattern over time. And so what Brandwood did was recorded for every sentence the last five syllables and the sentence, whether the stresses, whether they were longer or short. And so, for example, Plato's Republic has around a thousand sentences in it. And for each of those thousand sentences, Brandwood recorded a binary vector, it was in this kind of language, of length five, long, short, short, short, long, if that's what those symbols mean. And then the notion was, the thing that he did and that I did, was let's look at, well, so there are 32 possible binary vectors, all possible patterns from all short to all long and everything in between. And so I would have a function f of x, if x is a possible binary pattern of length five, which is how many times did that pattern appear in Plato's Republic and in the other books, f of laws of x. And the idea was to look at, for example, Plato's Republic, which we know was written early, and see if these numbers show some pattern. And then if that pattern is different in laws, we could use it to seriate. That was the notion. And using, I'm not going to say in detail how that came out, but if you're interested, I think if you type in Percy and Plato, it's a paper I wrote with Julia Salzman. And not quite what I want to talk about, but that's an example of analysis of binary data. Well, there's all kinds of binary data. It could be that I'm looking at a string of zeros and ones, x1 up to xk, which may be of length 12, which was one or zero as that worker was employed or not in that month. And the current population survey gives me 5,000 workers and vectors of length 12, and it tells me what f of x is for those workers. And again, you could try to make sense out of those numbers. Or there's lots of a class of students, and you gave them a true false test, and you have how many students had this pattern. So there's lots of examples of binary data that one wants to analyze. And what I want to get to, so that you know this is how it started, I want to get to my own personal elliptic curve. So I've got a ways to go. So when we analyze data of this sort, we often replace the data by various averages. For example, it might be that I looked at all, I sum how many people, how many people, how many sentences began with one. How many sentences have a one in the I place. How many sentences have one zero in places, i and j, etc. So we often analyze such data by taking averages of the different functions, of the functions that come up, and then that helps clean up noise and allow us to make sense. And from this analysis, I was led to find a quite simple striking pattern in the Republican laws that were quite different, and when we use that to seriate the books, the majority opinion was vindicated, I'll put it that way, and it has had some impact on this tiny little area of scholarship, the fact that some math also pointed in the same way as other arguments. Okay, so if you have data, so I'm now, suppose we're given one function on binary k-tuples, and you are going to take certain averages of it, and so I'm going to specify a class of averages, let s be a subset of 2 to the k, a fixed subset of k-tuples, and then you could define the ray non-transform f bar of y, so I'm given f, and y is a binary vector, and this is the sum of f of x, for x in s plus y. So s is something like a ball, and what you're doing is taking your function and averaging it over a ball around y, that's a kind of common thing one will be doing for a second at any rate, and so you replace your data by some smoothing of it. Now a natural question, if you're doing stuff like that, if you're massaging data in that form, is well, can I, have I captured all the juice in the data? Well one pale version of that is given a bunch of averages, that is fixed in s, for example, and suppose I can tell you all of these averages, can you reconstruct f from it, or is there something hidden in the averaging process that is now invisible to you? And so a kind of math question is given s and f bar of y, for all y, can we reconstruct f? And this is, is the ray non-transform invertible in this situation, and there's no shortage of math and developments about properties of replacing a function by its averages over a collection of sets, and this is one that came up to me that I was interested in, and many other things, but I want to get to my favorite lift and curve, and I've got to go pretty directly to it. And so let me tell you some news, the news, the bad news and the good news. So the first piece of bad news is that, well first of all the good news is, the start of Larry's conference, the start of the good news, if the size of s is odd, you can always reconstruct. Okay, that's not hard to see, and it's true. But sometimes you can reconstruct it, it's important to reconstruct when the size of s is even. And, okay, well the first piece of bad news is that for most sets s of size 2k, you can't reconstruct, you can't. So the ray non-transform isn't invertible, and that's uniformly in k, actually. And here's the second piece I'll keep down here, maybe you won't be able to see it. A second piece of bad news is given a single s, and you can ask, given it, can you reconstruct? That problem, it's a yes or no question, that problem is NP complete. So there's not going to be some simple algorithmic way of doing it for general s. So that's maybe bad news for certain sort. But here's some good news. For many natural s's, because typical s and worst case s, of course the trouble could happen, but for many natural s, it's okay. That is, you're not losing any information. And the class I'm going to tell, the class that led to an elliptic curve, was balls in the hamming distance. So let s be equal to the set of all x, such that the number of ones in x is less than or equal to r, say. Okay, that's a ball, fixed ball, where this is the number of ones in x, the hamming metric. And so suppose I replace a function by smoothing it. Can you reconstruct it? It's a math question that came up in the middle of doing the analysis. So now it starts to depend on r. So, okay, so it starts to depend on r. And so I have two parameters now. The diameter of my ball and k, the length of my vectors. And so when r is one, so everything within one of me. It's okay if and only if k is odd. Okay, so that's a theorem anyway. When r is two, so everything within two of me, you can reconstruct if and only if k is not a square. So mostly you can reconstruct. Okay, that's good. r is three. It's okay if and only if k is odd and not a square. Okay, it's getting more and more okay. And when r is bigger than or equal to four, okay, just slightly bigger balls, it's okay that you boys have any reconstruction except for finitely many k. So that's already uses some classical piece of number theory, but not, okay. So I started in working on the question of, well, all right, what happens with four? I know that there are only finitely many bad values of k. Can I find them? What's it about? And I want to just write down what this has to do with anything. So let me write it down. So when r is four, it's bad, that is, you can't reconstruct if and only if. This polynomial, z to the fourth minus twice three k minus four z squared plus three k times k minus two has an integer zero, integer zero, zero plus three k. So there's a diafantene type condition, the k's which are bad, or the k's such that this is the fourth Grotch-Uk polynomial for people who like orthogonal polynomials and that's when you can reconstruct. Well, okay, this is work done with Ron Graham who then had a team of programmers and we went to the computer and so the bad values, I'll write here, so what are the, what are the bad values of k? Well, it was bad for k equals one, two, three, eight, seventeen, sixty-six, one, five, two, one, and fifteen thousand forty-three. Okay, so sometimes it was bad and we looked pretty hard and we thought, well, is it possible that that's all? Now for those many people in this audience, this is essentially an elliptic curve and so let me write it down that way by an elementary transformation, figuring out it, so I have two parameters as z and k here, so this is, let's see, up and down, so just to try to make it look more like something this audience might relate to, this is equivalent, equivalently, this is the curve, y squared is equal to six x squared times x squared minus one plus nine and if you prefer Biasdras form, u squared is equal to four v cubed minus fifty-seven v plus fifty-three. So you needed to find integer solutions of these equations and we know that there are only finitely many and it's a question about whether we found the largest one or not and it's just a little corner of work but I was very pleased to have an elliptic curve that I met on my own terms without somebody saying, well, this is a famous thing, there it came, I mean it just came from seriating the books of Plato and so I went to Barry and I said, hey, I've got my own elliptic curve, and it looked at me, but we're friends so he listened up and he got very, very interested in it and he put the word out, whatever that means but Barry calls you and says, and I asked him, why are you so interested in that curve? And he said, you know, curves that come up in nature from some other cause that are, you know, often have a way of reappearing and you know, curves that actually come up in the real problem deserve respect and I, thank you. And through a chain of events, but it really did start with Barry and I wrote their names down and I'll mispronounce them but let me at least try to say it, Stoker and DeVeger showed that we found all the integer solutions, except for this list of Ks you can always invert the radon transform when you are averaging over balls of size four. Anyway, it's a little kind of corner thread of applied math but it was one in which Barry really did make a difference. Their papers, well, okay, it's actually not easy to show that you found all the solutions, maybe it's easier since they did it but, okay. So again, I would wake you up when you were awake anyway, right? So here comes the third talk. And this talk, this is about wandering around on the streets of Paris and here's how it goes. So I'm interested in many things, some talents, language is not one of them, okay. So there I am, I was teaching it or say living in Paris and wandering around. Because you walk and you walk and you walk and you walk and you walk and you walk. But I, you know, didn't, my French is just poor. And so I noticed I was using an algorithm to maneuver around, not a map of course. But you know, oh that way, I went that way before, I kind of recognized it, I'll go that way. That is, I was wandering around the streets of Paris using the algorithm that streets that I walked more in the past I was more likely to choose in the future. And let those of us who have not done such a thing cast the first stones. And at some stage I decided to try to make a math problem out of that. You know, how can I, that sounds like something I should be able to mathmatize. So let me tell you what I did. Let's take the simplest case, let's take a triangle, here it is, A, B, C. Okay, and I'm going to put weights one on each of the edges. And imagine a random walker who starts at A and then picks B or C at random, maybe he goes to C. And every time he crosses over an edge he adds one to the weight of the edge. Okay, and when you're in a new vertex you pick where to go with probability proportional to the weight of the edges leading out of you. Okay, so that's what I was doing and I just said it as math, right? And so now the question is what happens? Okay. So this is a triangle. So let's see what would happen. So here two thirds of the time I go back, so maybe I go back and now I'm here again and now three quarters of the time I go back. So one natural thought is you wind up dying on an edge. You go back and forth and that's what you do, okay? That's one natural thought. And the second thought is what can't matter what happens at the beginning, you wind up spending your third of your time in each vertex. Because those are the only two natural guesses and both of them are wrong. And so there's no natural third guess that I could think of. But it's a simple enough problem that it must yield to thought. It's just a triangle after all. And I kept thinking I'd see it and eventually I blasted it out and it was hard work. And I want to tell you a sense about it, first let me tell you the sort of bottom line of it. So again, if NAB is the number of times I cross AB after N steps and I look at NBC, N over N, NAC. So this is the proportion of times I've crossed each edge. So this is a vector on the simplex, the numbers at 7 to 1. And it proved that this converges to a limit, theta 1, theta 2, theta 3 on the unit simplex and N goes to infinity almost surely. But this limit is random. So if you started with a fresh triangle and you did it again, you would converge almost surely, but the limit where you converge to is different. And each time it will be different. And so then it's a natural question. Well, there's some limiting probability distribution on the simplex. And I know lots of them. My community knows lots of them. And I did figure it out. I'm going to write it down in a second. But it's nobody's friend. So not one of the standard ones. I just write it down. It's not far away. I almost remember it. So the limiting density, this has a continuous density. It was xy plus xz plus yz to the 1 half divided by x plus y times x plus z to the 3 halves times y plus z to the 3 halves. And it's pi. It's a normalizing constant. And here, I guess, this is x, this is y, and this is z. Those are. So it's a funny density. And I once was at CCR. And I said, I'll give 100 bucks if anybody can show that this pi is the right constant. It's an integral over the simplex. And why does it integrate the pi? And some kind of end did it sitting there. And I thought, Richard's dong. And I paid 100. That was the hard part, is to get them to take them. Anyway, so this is the limiting proportion of time that you cross each edge in some funny, funny limiting probability distribution. Now, so let me just say this. The same story I just told you is true on any finite graph. So if you take a graph, it could be a square, it could be any kind of finite, say, simple finite graph connected. You start random walk with reinforcement. That is, you put one on all the edges. And you move, and every time you add, you add one to the edge. The same story is true. That is, the proportion of times you cross each edge tends to a limit. That limit has a density, which is absolutely continuous. And there's an expression for it, which is a little bit worse than this. But it's worse than this in an interesting way. The description of the limit uses the first homology group of the graph, Pi 1 of the graph. And it's the only theorem I know about in probability where anything about homology comes in. And I'd be happy to be corrected about that. But now, what does that have to do with Barry? So as part of our long conversation, I have often tried to teach Barry probability. How to think a little bit like a problem was. And it hasn't been easy. So one of the ways that I tried is I said, well, you know, and he wants to learn. I mean, speak all languages, including mine. And so I said, well, next time I'm, you know, in the middle of some problem, you know, we can do some calculations together so you get a feel for what it's like. So let me say a sentence about what is behind this. This random walk with reinforcement, that's what it's called, is generates a stochastic process. So X naught, where you are, say that's A, and then there's X1, X2, etc. So if you wander around, you know, where you are is random and I'm giving them names, calling them X naught, X1, X2, etc. And I guessed from examples or from having done things like that for years that this process, for any graph, this process was what's called partially exchangeable. And let me try to explain what that means. So if you take two possible realizations, so all the strings will start with A, but well, so for example, suppose you start A, B, A, B, C, B, A. That's one way your process could start. And another way it could start is if I switch these two blocks, B, C, B, A, B, A, so I just took this block and this single block and switched them. That's all I did. These two strings have the same transition count matrix. That is if I make a counting matrix, here's A, B, C, A, B, C, how many times in a string did I go from A to B, etc. Well, it's zero along the diagonal. How many times in this string did I go from A to B? Once, twice. So from A to B, I went twice. From A to C, no, no times, okay. From B to A, once, twice, okay, etc. Let's, well, we can just do it from B to C, I went once, okay, from C to B, C to A, C to A, zero, okay. So that's the transition count and this string has the same transition count matrix, okay, and you can get, that's if and only if, you can get one string to another by switching blocks in this way. And the claim is that for random walk with reinforcement, if two strings have the same transition count matrix, they're assigned the same probability, okay. And I'd verified that in small examples and thought it was probably true, but I hadn't actually written out a proof. And I said to Barry, we were walking back from the science center to his house or something, I told him the story and he said, well, let me try that. I'm going to write it down. And the next day, he wrote out a two-page proof and honest, you know, combinatorics from ballistic proof of that for any graph, a graph that random walk with reinforcement is, it's called partially exchangeable. Well, I built a machine in somewhat before that, which is called Diffiniting Theorem for Markov chains and so this condition is called partial exchangeability. So partial exchangeability is equivalent, so a process is partially exchangeable, is equivalent to it being a mixture of Markov chains. That is, if and only if for every n, and all x1 up to xn, the probability assigned to x1 up to xn, the probability that your process goes through this string, I suppose it starts at a fixed point, is equal to the integral over the simplex of the product of theta i j to the ni i j mu d theta. So here, this is the simplex, it would be the three simplex if I was working with the triangle, but it's the simplex of all indexed by the set of all edges. And so the claim is that partial exchangeability is equivalent to their existing a measure on the simplex fixed measure such that for all possible strings, the chance of seeing that string can equivalently be said as pick a transition matrix, pick a Markov chain from this probability on Markov chains, and then run that Markov chain, Diffiniting Theorem for Markov chains. So his calculations allowed me to use this theorem and then knowing that there was a limiting measure, it's the only first way we knew that there was a limiting measure, I could then use the existence of a limiting measure to calculate by combinatorics what are the chances and this is what came out. So that's a third example. And so one part of this talk, of course, is in as much as I am an applied mathematician, what do we do for a living? So I've given you three examples. They're mostly problems that come from some real world connection and shuffling cards and analyzing binary data and well, walking around the building. In many cases, even though you've done a specific problem that came from an application, if you take the math seriously, something happens. In particular, I'll tell you one sentence of what happened from this triangle problem. Of course, you can do this on any graph, so take an infinite graph, like take the integers. And so put one on every edge of the usual graph of the integers, a random marker starts at zero and every time she crosses an edge, she adds one to the way to the edge. So there's a restoring force back and when you're at a new vertex, move to one of the vertices, the j-senty with probability proportional to the edge weights. And ordinary random walk on z is recurrent to come back to zero infinitely often. So it must be if you have a restoring force, must also be recurrent and that's true. It wasn't so easy to prove. It was Robin P. Mannell's thesis at MIT. But in two dimensions, it was open for 30 years. It was my most famous open problem. That is, is random walk in two dimensions with recurrence, with reinforcement, is random walk recurrent. And finally, Christophe Sabot and Pierre Therres proved that it is recurrent. In fact, it's recurrent on any lattice. Just to give you one more sentence about that, if you take an infinite tree, our favorite object, the infinite binary tree, in random walk with reinforcement, if you add one each time, it's not recurrent. If you add five each time, it is recurrent. And five is the square root of some solution of the trans-adduent equation. So there's a phase transition. That's another result of Robbins. And so it's an interesting problem, and it came from this. Well, the breakthrough came because the measure, my crazy measure, this mu, you can't see it, but there it is. I didn't write it down. But this mu, which involved the homology group of the graph in interesting ways, had been studied by physicists, Tom Spencer and Morton Zernbauer, for doing super-symmetric strain theory. And in an unbelievably long, hard piece of analysis, they figured out enough about this measure so that we could do the asymptotics that we needed. And then they got interested. They'd never heard of Diffenetty's theorem or this way. But it's the same measure that came out. Why is that? And there's a very healthy interaction between the group of physicists and the group of probabilists. And if you're interested, it'll be an aimed workshop in about nine months from now on the interaction. These are three instances of how Barry helped one person in applications. I bet that everybody in this audience, at least those of us who know Barry, have a similar story. It would be interesting to try to bring them together. I'm going to end with a warning. I don't think I've successfully ever finished teaching Barry probability, but we're both still around. So, yeah. Thank you. Thank you. Thank you.
 So of all the accolades we've heard, wonderful things we've heard about Barry, applied mathematics  I don't think has been mentioned in the first bunch of talks.  And the theme of this talk is the following.  Anybody who does mathematics, no matter how focused, no matter how abstract, runs into  outsiders.  And you're at a faculty meeting, you're at a dinner, and some chemists are social scientists,  who you're a mathematician, I have a question.  Can I ask you, and every once in a while you get interested and do a little something,  and some applied math comes out of it.  It's hard of course to, how do you keep track of somebody's output in that dimension.  And I'm going to take advantage of the fact that the outsider that asks Barry the things  that I'm going to talk about is me.  So over close to 50 year period, I've talked to Barry, we're friends and talk about all  kinds of things.  And I tricked him, whatever, into thinking about various things, and I'm going to tell  you three of them.  And these are three stories.  The first is about shuffling cards.  And that's going to be my favorite story about stories.  And the second is about the books of Plano.  And the third is about walking on the streets of Paris.  And okay, so most of my mathematical adventures start with some real world problem.  And let me set the scene for the first instance.  So I was working at Bell Labs, and I was trying to figure out the optimal strategy in a certain  card game.  And it was much too complicated to solve or get to the end of it.  So we were doing it by simulation.  Try to make certain choices in how many cards each point is worth, and then have it play  against itself and optimize, that sort of thing.  And so in order to do that, we needed lots and lots of random permutations of 52 cards.  Let me remind you how you generate a random order in the deck of cards.  Suppose you had 52 cards as memory registers or in a stack.  Then you get the computer to generate a random number between 1 and 52, say 17, and you transpose  cards 1 and 17.  And then between 2 and 52, say 5, and you transpose 2 and 5.  Then between 3 and 52, maybe 3, so you do nothing to 3, etc.  So you do that, and assuming that the random number generator works, or that you're happy  with that, that generates a random permutation, right?  Because any card can be on top, and then any card next, etc.  OK, so we ran the simulations, and they took, well, I don't know, 30 hours of CPU time on  big machines.  So it was a lot of effort.  And after that was all done, and we're looking at something was wrong.  I don't know what does it mean something is wrong when you're looking at pages and pages  of simulations, but something was wrong.  Something wasn't monotone.  And so we start looking at the code.  I mean, there's no more painful thing to do than that, looking at somebody else's code.  And after two days, I sent to the lady, Mary, and get over there, well, I'm desperate.  How did you generate your random permutations?  And she said, oh yeah, you said that fussy thing, transpose random with 1 random.  She said, I made them more random.  I transpose random with random.  And I said, ha.  And you have to redo the simulations.  You have to rerun the code.  And she actually cried, I remember, and said, you know, but it can't make any difference.  She went to her boss, and he went to his boss, and he came down and yelled at me, your mathematicians  are crazy.  You know, she did 100 random transpositions.  That has to be enough to mix up 52 cards.  And so I really wanted to know the answer to the question, how many random transpositions  does it take to mix up 52 cards?  I mean, that's the background for this story.  And so just to put it in context, so you're with me.  So suppose a deck of cards starts out on the table, 1 up to 52 in order of card 1, card  2 up to 52.  You pick a card at random with your left hand, you pick a card at random with your right  hand, and you switch them.  And you do that a lot.  And you allow your left hand to equal your right hand, because otherwise there'd be a  parity problem after an even number of switches would be in an even position.  And I want to know how many transpositions does it take to mix up cards.  In my instance, the lady did 100.  The first time that the Bridge League went from hand shuffle cards to computer shuffle  cards, they did 60 random transpositions.  Not knowing the usual algorithm.  How many does it take?  So let me make math of that for a second.  So I'm working on all permutations of N is 52.  And the probability thing that I just waved my hands about, you can code it up this way.  It's a probability distribution.  The probability of a permutation sigma is, well, 1 over N of sigma is the identity, and  it's 2 over N squared if sigma is a transposition, and 0 otherwise.  That's my basic step in my switches.  And then repeated transpositions we model as convolution.  So I write it down just for a second p star p of sigma.  The chance of being at a given arrangement of a deck of cards after shuffling twice is  equal to the sum of p of eta p of, I guess, it's sigma a.  Here summed over eta.  So that's just ordinary convolution.  And p star k of sigma is the chance of being at the arrangement sigma after k switches.  So there I've written it down.  And then there's the uniform distribution u of sigma, which is 1 over N factorial.  All permutations equally likely.  And I want to know how large this, well, Pankeray actually was the first one to show.  The 1890s that p star k converges to u.  And k gets large, which just says if you shuffle a deck of cards a lot, it gets all mixed up.  And you already knew that.  And I want to know how fast.  And so in order to tell you that, I have to say one more definition, stop for a second  too.  And so the distance between shuffling k times and uniform, this is one good way of defining  it.  P star k of a minus u of a.  And maximum over a in Sn.  And so here's what this says.  A is some set of arrangements of the deck of cards.  Maybe all arrangements of the deck of cards with the ace of spades is in the top half.  And p star k of a is what's the chance that the deck is in that set of arrangements after  k shuffles.  And u of a is if the cards are perfectly mixed, what's the chance?  Take the difference between those two numbers and then you take the worst case of that.  That's the distance that we often use, total variation.  And with all of this specified, there's now a math problem, finally.  Given epsilon bigger than zero, how large k, except so that the distance of k is, you  know, the distance of k is less than epsilon.  That's now a math problem.  And.  I have a question.  What about just choosing one part of it and putting it in for choosing?  There are a lot of algorithms for generating a random.  Does that work?  I don't want to answer that right now.  I'd be happy to discuss it offline.  Not the right time for that question, but I'd be happy to discuss.  There are lots of algorithms.  I just try to say the standard one.  I'm just wondering why it doesn't matter if you've got a system.  Well, I don't know either, but I told you the one that they used.  So that's yet another question.  So with Miradat Shashahani, another longtime friend of Barry's, we figured this out.  And the way theorem comes out is this way.  If k is one half n log n plus cn, c is bigger than zero.  I'll explain this.  Then the distance of shuffling to random is less than or equal to 2 e to the minus c.  And this c is the same as this c.  And what that means, well, that means if you want to know how many times to shuffle to make  this less than 1 in 100, you write equals 1 in 100.  You solve for c and then put that into here and that gives you the answer.  And there's a lower bound that matches this.  So that was a, now if you want to do that, I want to learn how to do this and then learn  how to do that.  And so that's what a theorem looks like in the subject.  I think this was the first such theorem in the sense of a short quantitative bound.  And I, in 1985, I gave this same talk in this same room.  Barry and David Mumford were interested in having somebody in the math department who  knew about combinatorics and probability and asked me to give the job talk.  Although I didn't know it was a job talk, but anyway, I did talk about this because  I just written it all down.  And I should say by the way, the answer's around 400, I mean, or something like that  in order to, and we know why it's not random when it's not random.  And that did explain the anomalies in our results.  And after my talk, Barry, as usual, I saw him talk after talk, came up and said, that  was great, and thank you, man, a lot to me, still does.  And he said, but the reason your argument works is because the set of transpositions  is a conjugacy class in the group.  And what you're really doing is taking the element in the group algebra, which is the  sub of all transpositions plus the identity, and then raising it to a high power.  Well, you could do that for any group, you know, any lead type group.  And he was going on and kind of sketching out a program of research.  And we're friends, and after about five minutes or something, I said, yeah, but what's the  story?  Why would anybody care about doing whatever I was just doing on a lead type group?  And Barry didn't know what I was talking about.  And after another five minutes of my trying to explain, he said, I see.  He said, what you don't understand is that in mathematics, somebody else makes up the  story.  There's some truth to that, and there's a wonderful history.  The character theory that I needed in order to prove this theorem was done by Formanius  for just the craziest reason.  The determinant of a circulant is a product of linear forms in the entries.  And I mean, who would care about that?  And character theory came out of that.  So stranger things have happened now.  But Barry's thought stayed with me, even though I told you why I was doing this problem.  But I just came.  Sometimes takes a while for the ideas to mature.  I just came from six months at MSRI, where a group of us are doing exactly what Barry  laid out, that is, take a lead type group, say GLM over a finite field, and take a conjugacy  class like something like transfections or any conjugacy class.  In fact, these are all simple groups, and almost anything will generate.  And then you can do the analog, make the random walk.  And with a group of very wonderful group theorists who I've corrupted, it's his fault, but I've  corrupted them, there's a kind of unifying result which is more or less, but really more  or less, that is essentially always.  For any lead type group, any conjugacy class, the identity, etc., the rank of the group  is necessary and sufficient in order to have things be random.  So took a while, but I did finally follow.  And I have no idea why we're doing it.  It's just the math is nice.  And now I want to say, what else do I want to say about this particular thing?  Really the reason I told it to you is it is my favorite story about stories, but one thing  that came out of this result, just a lot of smart people here, this particular thing,  if I graph it.  So this is K, the number of shuffles, and this is the distance of p star K minus u, how close  we are.  And this distance that I'm working in is the difference between two numbers which are between  zero and one.  So it's between zero and one.  And it's zero if the measures are the same, and it's one if the measures are completely  distrubly supported, and what this theorem says is something a little surprising.  It says that this distance behaves with a sharp cutoff, and this cutoff happens at a  half n log n.  That's where this cut, that is this going to zero happens in the second term of the asymptotics.  So if you were to make a plot, and it's an outstanding conjecture in the field, let me  say it twice, take any set of permutations that generate the symmetric group, any wave  shuffling that you like, and start shuffling with them.  There is a sharp cutoff, that is there is this cutoff phenomena happens for any generating  set, and a marvelous development that came from this, we made a theory following what  I told you about, which says if you know all about one way of shuffling, if you have very,  very sharp answers for one way of mixing things, then you can get good answers for essentially  any way of shuffling.  It's called comparison theory, and that's now a machine on its own.  Using comparison theory, Rijuk, Shirash, and Helfkart, I think an inverse order, proved  that you know if you pick two permutations at random, they generate either Sn or An with  probability, well, one, and they generate Sn with probability three quarters.  So pick two permutations at random, say a transposition in an encycl, but any two permutations,  pick two permutations at random.  The mixing time is of order NQ blog N, and that's the worst, and we conjecture that there's  a sharp cutoff of this sort, and in fact we conjecture it for any set of generators for  any finite simple group, but there's just a handful of examples, and this is one of  them where we've been able to prove that there are cutoffs, in particular for a transposition  in an encycl, we don't know.  I believe that there's an explicit constant such that NQ blog N plus C is the right answer,  but we don't know.  So those are math problems that come from this development.  But more than that, it is a typical example of how I get involved in a problem and what  happens from it.  So that's enough without shuffling cards, and you should be happy because I just finished  teaching a graduate course on the mathematics of gambling, and they had to sit through four  weeks of shuffling.  So this is all you're going to hear about today.  So in case you're tired, it's the last thought.  Wake up, new talk.  So my second story, I want to tell, those of us who've been participating, I hope most  of us were lucky enough to have heard Elaine Scarry talk about Plato's poetics on Wednesday.  It was just made these wonderful texts come to life.  Well, I'm going to talk about Plato.  It says it right there for a few minutes.  So one of the things that we don't know, so Plato wrote a lot of famous books, the ones  that have come down to us, and we don't know what order he wrote them in.  So Plato's Republic was written early, Laws was written late, and the others.  And it matters if you're a Plato scholar, that is, because he changed his opinion, it  matters.  If you're trying to interpret, how did he come to?  So that's a question how to seriate the books of Plato.  And there's been endless articles written about that.  Well, he was whilst here and while there, you can imagine the conversations going on  and on.  And around the late 1950s, a Plato scholar named Brandwood decided to go get some data.  And Plato said that he systematically changed his rhyming pattern over time.  And so what Brandwood did was recorded for every sentence the last five syllables and  the sentence, whether the stresses, whether they were longer or short.  And so, for example, Plato's Republic has around a thousand sentences in it.  And for each of those thousand sentences, Brandwood recorded a binary vector, it was  in this kind of language, of length five, long, short, short, short, long, if that's  what those symbols mean.  And then the notion was, the thing that he did and that I did, was let's look at, well,  so there are 32 possible binary vectors, all possible patterns from all short to all long  and everything in between.  And so I would have a function f of x, if x is a possible binary pattern of length five,  which is how many times did that pattern appear in Plato's Republic and in the other books,  f of laws of x.  And the idea was to look at, for example, Plato's Republic, which we know was written  early, and see if these numbers show some pattern.  And then if that pattern is different in laws, we could use it to seriate.  That was the notion.  And using, I'm not going to say in detail how that came out, but if you're interested,  I think if you type in Percy and Plato, it's a paper I wrote with Julia Salzman.  And not quite what I want to talk about, but that's an example of analysis of binary data.  Well, there's all kinds of binary data.  It could be that I'm looking at a string of zeros and ones, x1 up to xk, which may be  of length 12, which was one or zero as that worker was employed or not in that month.  And the current population survey gives me 5,000 workers and vectors of length 12, and  it tells me what f of x is for those workers.  And again, you could try to make sense out of those numbers.  Or there's lots of a class of students, and you gave them a true false test, and you have  how many students had this pattern.  So there's lots of examples of binary data that one wants to analyze.  And what I want to get to, so that you know this is how it started, I want to get to my  own personal elliptic curve.  So I've got a ways to go.  So when we analyze data of this sort, we often replace the data by various averages.  For example, it might be that I looked at all, I sum how many people, how many people,  how many sentences began with one.  How many sentences have a one in the I place.  How many sentences have one zero in places, i and j, etc.  So we often analyze such data by taking averages of the different functions, of the functions  that come up, and then that helps clean up noise and allow us to make sense.  And from this analysis, I was led to find a quite simple striking pattern in the Republican  laws that were quite different, and when we use that to seriate the books, the majority  opinion was vindicated, I'll put it that way, and it has had some impact on this tiny little  area of scholarship, the fact that some math also pointed in the same way as other arguments.  Okay, so if you have data, so I'm now, suppose we're given one function on binary k-tuples,  and you are going to take certain averages of it, and so I'm going to specify a class  of averages, let s be a subset of 2 to the k, a fixed subset of k-tuples, and then you  could define the ray non-transform f bar of y, so I'm given f, and y is a binary vector,  and this is the sum of f of x, for x in s plus y.  So s is something like a ball, and what you're doing is taking your function and averaging  it over a ball around y, that's a kind of common thing one will be doing for a second  at any rate, and so you replace your data by some smoothing of it.  Now a natural question, if you're doing stuff like that, if you're massaging data in that  form, is well, can I, have I captured all the juice in the data?  Well one pale version of that is given a bunch of averages, that is fixed in s, for example,  and suppose I can tell you all of these averages, can you reconstruct f from it, or is there  something hidden in the averaging process that is now invisible to you?  And so a kind of math question is given s and f bar of y, for all y, can we reconstruct  f?  And this is, is the ray non-transform invertible in this situation, and there's no shortage  of math and developments about properties of replacing a function by its averages over  a collection of sets, and this is one that came up to me that I was interested in, and  many other things, but I want to get to my favorite lift and curve, and I've got to go  pretty directly to it.  And so let me tell you some news, the news, the bad news and the good news.  So the first piece of bad news is that, well first of all the good news is, the start of  Larry's conference, the start of the good news, if the size of s is odd, you can always  reconstruct.  Okay, that's not hard to see, and it's true.  But sometimes you can reconstruct it, it's important to reconstruct when the size of  s is even.  And, okay, well the first piece of bad news is that for most sets s of size 2k, you can't  reconstruct, you can't.  So the ray non-transform isn't invertible, and that's uniformly in k, actually.  And here's the second piece I'll keep down here, maybe you won't be able to see it.  A second piece of bad news is given a single s, and you can ask, given it, can you reconstruct?  That problem, it's a yes or no question, that problem is NP complete.  So there's not going to be some simple algorithmic way of doing it for general s.  So that's maybe bad news for certain sort.  But here's some good news.  For many natural s's, because typical s and worst case s, of course the trouble could  happen, but for many natural s, it's okay.  That is, you're not losing any information.  And the class I'm going to tell, the class that led to an elliptic curve, was balls  in the hamming distance.  So let s be equal to the set of all x, such that the number of ones in x is less than  or equal to r, say.  Okay, that's a ball, fixed ball, where this is the number of ones in x, the hamming metric.  And so suppose I replace a function by smoothing it.  Can you reconstruct it?  It's a math question that came up in the middle of doing the analysis.  So now it starts to depend on r.  So, okay, so it starts to depend on r.  And so I have two parameters now.  The diameter of my ball and k, the length of my vectors.  And so when r is one, so everything within one of me.  It's okay if and only if k is odd.  Okay, so that's a theorem anyway.  When r is two, so everything within two of me, you can reconstruct if and only if k is  not a square.  So mostly you can reconstruct.  Okay, that's good.  r is three.  It's okay if and only if k is odd and not a square.  Okay, it's getting more and more okay.  And when r is bigger than or equal to four, okay, just slightly bigger balls, it's okay  that you boys have any reconstruction except for finitely many k.  So that's already uses some classical piece of number theory, but not, okay.  So I started in working on the question of, well, all right, what happens with four?  I know that there are only finitely many bad values of k.  Can I find them?  What's it about?  And I want to just write down what this has to do with anything.  So let me write it down.  So when r is four, it's bad, that is, you can't reconstruct if and only if.  This polynomial, z to the fourth minus twice three k minus four z squared plus three k  times k minus two has an integer zero, integer zero, zero plus three k.  So there's a diafantene type condition, the k's which are bad, or the k's such that this  is the fourth Grotch-Uk polynomial for people who like orthogonal polynomials and that's  when you can reconstruct.  Well, okay, this is work done with Ron Graham who then had a team of programmers and we  went to the computer and so the bad values, I'll write here, so what are the, what are  the bad values of k?  Well, it was bad for k equals one, two, three, eight, seventeen, sixty-six, one, five, two,  one, and fifteen thousand forty-three.  Okay, so sometimes it was bad and we looked pretty hard and we thought, well, is it possible  that that's all?  Now for those many people in this audience, this is essentially an elliptic curve and  so let me write it down that way by an elementary transformation, figuring out it, so I have  two parameters as z and k here, so this is, let's see, up and down, so just to try to  make it look more like something this audience might relate to, this is equivalent, equivalently,  this is the curve, y squared is equal to six x squared times x squared minus one plus nine  and if you prefer Biasdras form, u squared is equal to four v cubed minus fifty-seven  v plus fifty-three.  So you needed to find integer solutions of these equations and we know that there are  only finitely many and it's a question about whether we found the largest one or not and  it's just a little corner of work but I was very pleased to have an elliptic curve that  I met on my own terms without somebody saying, well, this is a famous thing, there it came,  I mean it just came from seriating the books of Plato and so I went to Barry and I said,  hey, I've got my own elliptic curve, and it looked at me, but we're friends so he listened  up and he got very, very interested in it and he put the word out, whatever that means  but Barry calls you and says, and I asked him, why are you so interested in that curve?  And he said, you know, curves that come up in nature from some other cause that are,  you know, often have a way of reappearing and you know, curves that actually come up  in the real problem deserve respect and I, thank you.  And through a chain of events, but it really did start with Barry and I wrote their names  down and I'll mispronounce them but let me at least try to say it, Stoker and DeVeger  showed that we found all the integer solutions, except for this list of Ks you can always  invert the radon transform when you are averaging over balls of size four.  Anyway, it's a little kind of corner thread of applied math but it was one in which Barry  really did make a difference.  Their papers, well, okay, it's actually not easy to show that you found all the solutions,  maybe it's easier since they did it but, okay.  So again, I would wake you up when you were awake anyway, right?  So here comes the third talk.  And this talk, this is about wandering around on the streets of Paris and here's how it  goes.  So I'm interested in many things, some talents, language is not one of them, okay.  So there I am, I was teaching it or say living in Paris and wandering around.  Because you walk and you walk and you walk and you walk and you walk and you walk.  But I, you know, didn't, my French is just poor.  And so I noticed I was using an algorithm to maneuver around, not a map of course.  But you know, oh that way, I went that way before, I kind of recognized it, I'll go that  way.  That is, I was wandering around the streets of Paris using the algorithm that streets that  I walked more in the past I was more likely to choose in the future.  And let those of us who have not done such a thing cast the first stones.  And at some stage I decided to try to make a math problem out of that.  You know, how can I, that sounds like something I should be able to mathmatize.  So let me tell you what I did.  Let's take the simplest case, let's take a triangle, here it is, A, B, C.  Okay, and I'm going to put weights one on each of the edges.  And imagine a random walker who starts at A and then picks B or C at random, maybe he  goes to C.  And every time he crosses over an edge he adds one to the weight of the edge.  Okay, and when you're in a new vertex you pick where to go with probability proportional  to the weight of the edges leading out of you.  Okay, so that's what I was doing and I just said it as math, right?  And so now the question is what happens?  Okay.  So this is a triangle.  So let's see what would happen.  So here two thirds of the time I go back, so maybe I go back and now I'm here again and  now three quarters of the time I go back.  So one natural thought is you wind up dying on an edge.  You go back and forth and that's what you do, okay?  That's one natural thought.  And the second thought is what can't matter what happens at the beginning, you wind up  spending your third of your time in each vertex.  Because those are the only two natural guesses and both of them are wrong.  And so there's no natural third guess that I could think of.  But it's a simple enough problem that it must yield to thought.  It's just a triangle after all.  And I kept thinking I'd see it and eventually I blasted it out and it was hard work.  And I want to tell you a sense about it, first let me tell you the sort of bottom line of  it.  So again, if NAB is the number of times I cross AB after N steps and I look at NBC, N over  N, NAC.  So this is the proportion of times I've crossed each edge.  So this is a vector on the simplex, the numbers at 7 to 1.  And it proved that this converges to a limit, theta 1, theta 2, theta 3 on the unit simplex  and N goes to infinity almost surely.  But this limit is random.  So if you started with a fresh triangle and you did it again, you would converge almost  surely, but the limit where you converge to is different.  And each time it will be different.  And so then it's a natural question.  Well, there's some limiting probability distribution on the simplex.  And I know lots of them.  My community knows lots of them.  And I did figure it out.  I'm going to write it down in a second.  But it's nobody's friend.  So not one of the standard ones.  I just write it down.  It's not far away.  I almost remember it.  So the limiting density, this has a continuous density.  It was xy plus xz plus yz to the 1 half divided by x plus y times x plus z to the 3 halves  times y plus z to the 3 halves.  And it's pi.  It's a normalizing constant.  And here, I guess, this is x, this is y, and this is z.  Those are.  So it's a funny density.  And I once was at CCR.  And I said, I'll give 100 bucks if anybody can show that this pi is the right constant.  It's an integral over the simplex.  And why does it integrate the pi?  And some kind of end did it sitting there.  And I thought, Richard's dong.  And I paid 100.  That was the hard part, is to get them to take them.  Anyway, so this is the limiting proportion of time that you cross each edge in some funny,  funny limiting probability distribution.  Now, so let me just say this.  The same story I just told you is true on any finite graph.  So if you take a graph, it could be a square, it could be any kind of finite, say, simple  finite graph connected.  You start random walk with reinforcement.  That is, you put one on all the edges.  And you move, and every time you add, you add one to the edge.  The same story is true.  That is, the proportion of times you cross each edge tends to a limit.  That limit has a density, which is absolutely continuous.  And there's an expression for it, which is a little bit worse than this.  But it's worse than this in an interesting way.  The description of the limit uses the first homology group of the graph, Pi 1 of the graph.  And it's the only theorem I know about in probability where anything about homology comes in.  And I'd be happy to be corrected about that.  But now, what does that have to do with Barry?  So as part of our long conversation, I have often tried to teach Barry probability.  How to think a little bit like a problem was.  And it hasn't been easy.  So one of the ways that I tried is I said, well, you know, and he wants to learn.  I mean, speak all languages, including mine.  And so I said, well, next time I'm, you know, in the middle of some problem, you know, we  can do some calculations together so you get a feel for what it's like.  So let me say a sentence about what is behind this.  This random walk with reinforcement, that's what it's called, is generates a stochastic  process.  So X naught, where you are, say that's A, and then there's X1, X2, etc.  So if you wander around, you know, where you are is random and I'm giving them names,  calling them X naught, X1, X2, etc.  And I guessed from examples or from having done things like that for years that this  process, for any graph, this process was what's called partially exchangeable.  And let me try to explain what that means.  So if you take two possible realizations, so all the strings will start with A, but  well, so for example, suppose you start A, B, A, B, C, B, A.  That's one way your process could start.  And another way it could start is if I switch these two blocks, B, C, B, A, B, A, so I just  took this block and this single block and switched them.  That's all I did.  These two strings have the same transition count matrix.  That is if I make a counting matrix, here's A, B, C, A, B, C, how many times in a string  did I go from A to B, etc.  Well, it's zero along the diagonal.  How many times in this string did I go from A to B?  Once, twice.  So from A to B, I went twice.  From A to C, no, no times, okay.  From B to A, once, twice, okay, etc.  Let's, well, we can just do it from B to C, I went once, okay, from C to B, C to A,  C to A, zero, okay.  So that's the transition count and this string has the same transition count matrix, okay,  and you can get, that's if and only if, you can get one string to another by switching  blocks in this way.  And the claim is that for random walk with reinforcement, if two strings have the same  transition count matrix, they're assigned the same probability, okay.  And I'd verified that in small examples and thought it was probably true, but I hadn't  actually written out a proof.  And I said to Barry, we were walking back from the science center to his house or something,  I told him the story and he said, well, let me try that.  I'm going to write it down.  And the next day, he wrote out a two-page proof and honest, you know, combinatorics  from ballistic proof of that for any graph, a graph that random walk with reinforcement  is, it's called partially exchangeable.  Well, I built a machine in somewhat before that, which is called Diffiniting Theorem  for Markov chains and so this condition is called partial exchangeability.  So partial exchangeability is equivalent, so a process is partially exchangeable, is  equivalent to it being a mixture of Markov chains.  That is, if and only if for every n, and all x1 up to xn, the probability assigned to x1  up to xn, the probability that your process goes through this string, I suppose it starts  at a fixed point, is equal to the integral over the simplex of the product of theta i  j to the ni i j mu d theta.  So here, this is the simplex, it would be the three simplex if I was working with the  triangle, but it's the simplex of all indexed by the set of all edges.  And so the claim is that partial exchangeability is equivalent to their existing a measure  on the simplex fixed measure such that for all possible strings, the chance of seeing  that string can equivalently be said as pick a transition matrix, pick a Markov chain from  this probability on Markov chains, and then run that Markov chain, Diffiniting Theorem  for Markov chains.  So his calculations allowed me to use this theorem and then knowing that there was a  limiting measure, it's the only first way we knew that there was a limiting measure,  I could then use the existence of a limiting measure to calculate by combinatorics what  are the chances and this is what came out.  So that's a third example.  And so one part of this talk, of course, is in as much as I am an applied mathematician,  what do we do for a living?  So I've given you three examples.  They're mostly problems that come from some real world connection and shuffling cards  and analyzing binary data and well, walking around the building.  In many cases, even though you've done a specific problem that came from an application, if  you take the math seriously, something happens.  In particular, I'll tell you one sentence of what happened from this triangle problem.  Of course, you can do this on any graph, so take an infinite graph, like take the integers.  And so put one on every edge of the usual graph of the integers, a random marker starts  at zero and every time she crosses an edge, she adds one to the way to the edge.  So there's a restoring force back and when you're at a new vertex, move to one of the  vertices, the j-senty with probability proportional to the edge weights.  And ordinary random walk on z is recurrent to come back to zero infinitely often.  So it must be if you have a restoring force, must also be recurrent and that's true.  It wasn't so easy to prove.  It was Robin P. Mannell's thesis at MIT.  But in two dimensions, it was open for 30 years.  It was my most famous open problem.  That is, is random walk in two dimensions with recurrence, with reinforcement, is random  walk recurrent.  And finally, Christophe Sabot and Pierre Therres proved that it is recurrent.  In fact, it's recurrent on any lattice.  Just to give you one more sentence about that, if you take an infinite tree, our favorite  object, the infinite binary tree, in random walk with reinforcement, if you add one each  time, it's not recurrent.  If you add five each time, it is recurrent.  And five is the square root of some solution of the trans-adduent equation.  So there's a phase transition.  That's another result of Robbins.  And so it's an interesting problem, and it came from this.  Well, the breakthrough came because the measure, my crazy measure, this mu, you can't see it,  but there it is.  I didn't write it down.  But this mu, which involved the homology group of the graph in interesting ways, had been  studied by physicists, Tom Spencer and Morton Zernbauer, for doing super-symmetric strain  theory.  And in an unbelievably long, hard piece of analysis, they figured out enough about this  measure so that we could do the asymptotics that we needed.  And then they got interested.  They'd never heard of Diffenetty's theorem or this way.  But it's the same measure that came out.  Why is that?  And there's a very healthy interaction between the group of physicists and the group of probabilists.  And if you're interested, it'll be an aimed workshop in about nine months from now on the  interaction.  These are three instances of how Barry helped one person in applications.  I bet that everybody in this audience, at least those of us who know Barry, have a similar  story.  It would be interesting to try to bring them together.  I'm going to end with a warning.  I don't think I've successfully ever finished teaching Barry probability, but we're both  still around.  So, yeah.  Thank you.  Thank you.  Thank you.
Persi_DIACONIS_-_Barry_Mazur_as_an_Applied_Mathema_-nijw3vuRfg_0_359.png Persi_DIACONIS_-_Barry_Mazur_as_an_Applied_Mathema_-nijw3vuRfg_360_611.png Persi_DIACONIS_-_Barry_Mazur_as_an_Applied_Mathema_-nijw3vuRfg_612_1259.png Persi_DIACONIS_-_Barry_Mazur_as_an_Applied_Mathema_-nijw3vuRfg_1260_2087.png Persi_DIACONIS_-_Barry_Mazur_as_an_Applied_Mathema_-nijw3vuRfg_2088_2315.png Persi_DIACONIS_-_Barry_Mazur_as_an_Applied_Mathema_-nijw3vuRfg_2316_4187.png Persi_DIACONIS_-_Barry_Mazur_as_an_Applied_Mathema_-nijw3vuRfg_4188_4295.png Persi_DIACONIS_-_Barry_Mazur_as_an_Applied_Mathema_-nijw3vuRfg_4296_5567.png Persi_DIACONIS_-_Barry_Mazur_as_an_Applied_Mathema_-nijw3vuRfg_5568_6203.png Persi_DIACONIS_-_Barry_Mazur_as_an_Applied_Mathema_-nijw3vuRfg_6204_7247.png Persi_DIACONIS_-_Barry_Mazur_as_an_Applied_Mathema_-nijw3vuRfg_7248_7403.png Persi_DIACONIS_-_Barry_Mazur_as_an_Applied_Mathema_-nijw3vuRfg_7404_7451.png Persi_DIACONIS_-_Barry_Mazur_as_an_Applied_Mathema_-nijw3vuRfg_7452_8231.png Persi_DIACONIS_-_Barry_Mazur_as_an_Applied_Mathema_-nijw3vuRfg_8232_8699.png Persi_DIACONIS_-_Barry_Mazur_as_an_Applied_Mathema_-nijw3vuRfg_8700_9167.png Persi_DIACONIS_-_Barry_Mazur_as_an_Applied_Mathema_-nijw3vuRfg_9168_10691.png Persi_DIACONIS_-_Barry_Mazur_as_an_Applied_Mathema_-nijw3vuRfg_10692_13787.png Persi_DIACONIS_-_Barry_Mazur_as_an_Applied_Mathema_-nijw3vuRfg_13788_13859.png Persi_DIACONIS_-_Barry_Mazur_as_an_Applied_Mathema_-nijw3vuRfg_13860_14375.png Persi_DIACONIS_-_Barry_Mazur_as_an_Applied_Mathema_-nijw3vuRfg_14376_17147.png Persi_DIACONIS_-_Barry_Mazur_as_an_Applied_Mathema_-nijw3vuRfg_17148_17591.png Persi_DIACONIS_-_Barry_Mazur_as_an_Applied_Mathema_-nijw3vuRfg_17592_17699.png Persi_DIACONIS_-_Barry_Mazur_as_an_Applied_Mathema_-nijw3vuRfg_17700_17747.png Persi_DIACONIS_-_Barry_Mazur_as_an_Applied_Mathema_-nijw3vuRfg_17748_17867.png Persi_DIACONIS_-_Barry_Mazur_as_an_Applied_Mathema_-nijw3vuRfg_17868_18443.png Persi_DIACONIS_-_Barry_Mazur_as_an_Applied_Mathema_-nijw3vuRfg_18444_19187.png Persi_DIACONIS_-_Barry_Mazur_as_an_Applied_Mathema_-nijw3vuRfg_19188_19295.png Persi_DIACONIS_-_Barry_Mazur_as_an_Applied_Mathema_-nijw3vuRfg_19296_19343.png Persi_DIACONIS_-_Barry_Mazur_as_an_Applied_Mathema_-nijw3vuRfg_19344_20411.png Persi_DIACONIS_-_Barry_Mazur_as_an_Applied_Mathema_-nijw3vuRfg_20412_21911.png Persi_DIACONIS_-_Barry_Mazur_as_an_Applied_Mathema_-nijw3vuRfg_21912_22487.png Persi_DIACONIS_-_Barry_Mazur_as_an_Applied_Mathema_-nijw3vuRfg_22488_22787.png Persi_DIACONIS_-_Barry_Mazur_as_an_Applied_Mathema_-nijw3vuRfg_22788_23447.png Persi_DIACONIS_-_Barry_Mazur_as_an_Applied_Mathema_-nijw3vuRfg_23448_25679.png Persi_DIACONIS_-_Barry_Mazur_as_an_Applied_Mathema_-nijw3vuRfg_25680_28475.png Persi_DIACONIS_-_Barry_Mazur_as_an_Applied_Mathema_-nijw3vuRfg_28476_28655.png Persi_DIACONIS_-_Barry_Mazur_as_an_Applied_Mathema_-nijw3vuRfg_28656_28739.png Persi_DIACONIS_-_Barry_Mazur_as_an_Applied_Mathema_-nijw3vuRfg_28740_28919.png Persi_DIACONIS_-_Barry_Mazur_as_an_Applied_Mathema_-nijw3vuRfg_28920_30611.png Persi_DIACONIS_-_Barry_Mazur_as_an_Applied_Mathema_-nijw3vuRfg_30612_30671.png Persi_DIACONIS_-_Barry_Mazur_as_an_Applied_Mathema_-nijw3vuRfg_30672_31151.png Persi_DIACONIS_-_Barry_Mazur_as_an_Applied_Mathema_-nijw3vuRfg_31152_41447.png Persi_DIACONIS_-_Barry_Mazur_as_an_Applied_Mathema_-nijw3vuRfg_41448_42227.png Persi_DIACONIS_-_Barry_Mazur_as_an_Applied_Mathema_-nijw3vuRfg_42228_44843.png Persi_DIACONIS_-_Barry_Mazur_as_an_Applied_Mathema_-nijw3vuRfg_44844_54563.png Persi_DIACONIS_-_Barry_Mazur_as_an_Applied_Mathema_-nijw3vuRfg_54564_54755.png Persi_DIACONIS_-_Barry_Mazur_as_an_Applied_Mathema_-nijw3vuRfg_54756_55151.png Persi_DIACONIS_-_Barry_Mazur_as_an_Applied_Mathema_-nijw3vuRfg_55152_58391.png Persi_DIACONIS_-_Barry_Mazur_as_an_Applied_Mathema_-nijw3vuRfg_58392_58451.png Persi_DIACONIS_-_Barry_Mazur_as_an_Applied_Mathema_-nijw3vuRfg_58452_58631.png Persi_DIACONIS_-_Barry_Mazur_as_an_Applied_Mathema_-nijw3vuRfg_58632_58691.png Persi_DIACONIS_-_Barry_Mazur_as_an_Applied_Mathema_-nijw3vuRfg_58692_58751.png Persi_DIACONIS_-_Barry_Mazur_as_an_Applied_Mathema_-nijw3vuRfg_58752_58871.png Persi_DIACONIS_-_Barry_Mazur_as_an_Applied_Mathema_-nijw3vuRfg_58872_65927.png Persi_DIACONIS_-_Barry_Mazur_as_an_Applied_Mathema_-nijw3vuRfg_65928_67535.png Persi_DIACONIS_-_Barry_Mazur_as_an_Applied_Mathema_-nijw3vuRfg_67536_68243.png Persi_DIACONIS_-_Barry_Mazur_as_an_Applied_Mathema_-nijw3vuRfg_68244_68639.png Persi_DIACONIS_-_Barry_Mazur_as_an_Applied_Mathema_-nijw3vuRfg_68640_72383.png Persi_DIACONIS_-_Barry_Mazur_as_an_Applied_Mathema_-nijw3vuRfg_72384_72623.png Persi_DIACONIS_-_Barry_Mazur_as_an_Applied_Mathema_-nijw3vuRfg_72624_72671.png Persi_DIACONIS_-_Barry_Mazur_as_an_Applied_Mathema_-nijw3vuRfg_72672_72983.png Persi_DIACONIS_-_Barry_Mazur_as_an_Applied_Mathema_-nijw3vuRfg_72984_73871.png Persi_DIACONIS_-_Barry_Mazur_as_an_Applied_Mathema_-nijw3vuRfg_73872_74771.png Persi_DIACONIS_-_Barry_Mazur_as_an_Applied_Mathema_-nijw3vuRfg_74772_75467.png Persi_DIACONIS_-_Barry_Mazur_as_an_Applied_Mathema_-nijw3vuRfg_75468_75983.png Persi_DIACONIS_-_Barry_Mazur_as_an_Applied_Mathema_-nijw3vuRfg_75984_76043.png Persi_DIACONIS_-_Barry_Mazur_as_an_Applied_Mathema_-nijw3vuRfg_76044_76091.png Persi_DIACONIS_-_Barry_Mazur_as_an_Applied_Mathema_-nijw3vuRfg_76092_76955.png Persi_DIACONIS_-_Barry_Mazur_as_an_Applied_Mathema_-nijw3vuRfg_76956_77003.png Persi_DIACONIS_-_Barry_Mazur_as_an_Applied_Mathema_-nijw3vuRfg_77004_80039.png Persi_DIACONIS_-_Barry_Mazur_as_an_Applied_Mathema_-nijw3vuRfg_80040_81755.png Persi_DIACONIS_-_Barry_Mazur_as_an_Applied_Mathema_-nijw3vuRfg_81756_82007.png Persi_DIACONIS_-_Barry_Mazur_as_an_Applied_Mathema_-nijw3vuRfg_82008_82151.png Persi_DIACONIS_-_Barry_Mazur_as_an_Applied_Mathema_-nijw3vuRfg_82152_82448.png
So of all the accolades we've heard, wonderful things we've heard about Barry, applied mathematics I don't think has been mentioned in the first bunch of talks. And the theme of this talk is the following. Anybody who does mathematics, no matter how focused, no matter how abstract, runs into outsiders. And you're at a faculty meeting, you're at a dinner, and some chemists are social scientists, who you're a mathematician, I have a question. Can I ask you, and every once in a while you get interested and do a little something, and some applied math comes out of it. It's hard of course to, how do you keep track of somebody's output in that dimension. And I'm going to take advantage of the fact that the outsider that asks Barry the things that I'm going to talk about is me. So over close to 50 year period, I've talked to Barry, we're friends and talk about all kinds of things. And I tricked him, whatever, into thinking about various things, and I'm going to tell you three of them. And these are three stories. The first is about shuffling cards. And that's going to be my favorite story about stories. And the second is about the books of Plano. And the third is about walking on the streets of Paris. And okay, so most of my mathematical adventures start with some real world problem. And let me set the scene for the first instance. So I was working at Bell Labs, and I was trying to figure out the optimal strategy in a certain card game. And it was much too complicated to solve or get to the end of it. So we were doing it by simulation. Try to make certain choices in how many cards each point is worth, and then have it play against itself and optimize, that sort of thing. And so in order to do that, we needed lots and lots of random permutations of 52 cards. Let me remind you how you generate a random order in the deck of cards. Suppose you had 52 cards as memory registers or in a stack. Then you get the computer to generate a random number between 1 and 52, say 17, and you transpose cards 1 and 17. And then between 2 and 52, say 5, and you transpose 2 and 5. Then between 3 and 52, maybe 3, so you do nothing to 3, etc. So you do that, and assuming that the random number generator works, or that you're happy with that, that generates a random permutation, right? Because any card can be on top, and then any card next, etc. OK, so we ran the simulations, and they took, well, I don't know, 30 hours of CPU time on big machines. So it was a lot of effort. And after that was all done, and we're looking at something was wrong. I don't know what does it mean something is wrong when you're looking at pages and pages of simulations, but something was wrong. Something wasn't monotone. And so we start looking at the code. I mean, there's no more painful thing to do than that, looking at somebody else's code. And after two days, I sent to the lady, Mary, and get over there, well, I'm desperate. How did you generate your random permutations? And she said, oh yeah, you said that fussy thing, transpose random with 1 random. She said, I made them more random. I transpose random with random. And I said, ha. And you have to redo the simulations. You have to rerun the code. And she actually cried, I remember, and said, you know, but it can't make any difference. She went to her boss, and he went to his boss, and he came down and yelled at me, your mathematicians are crazy. You know, she did 100 random transpositions. That has to be enough to mix up 52 cards. And so I really wanted to know the answer to the question, how many random transpositions does it take to mix up 52 cards? I mean, that's the background for this story. And so just to put it in context, so you're with me. So suppose a deck of cards starts out on the table, 1 up to 52 in order of card 1, card 2 up to 52. You pick a card at random with your left hand, you pick a card at random with your right hand, and you switch them. And you do that a lot. And you allow your left hand to equal your right hand, because otherwise there'd be a parity problem after an even number of switches would be in an even position. And I want to know how many transpositions does it take to mix up cards. In my instance, the lady did 100. The first time that the Bridge League went from hand shuffle cards to computer shuffle cards, they did 60 random transpositions. Not knowing the usual algorithm. How many does it take? So let me make math of that for a second. So I'm working on all permutations of N is 52. And the probability thing that I just waved my hands about, you can code it up this way. It's a probability distribution. The probability of a permutation sigma is, well, 1 over N of sigma is the identity, and it's 2 over N squared if sigma is a transposition, and 0 otherwise. That's my basic step in my switches. And then repeated transpositions we model as convolution. So I write it down just for a second p star p of sigma. The chance of being at a given arrangement of a deck of cards after shuffling twice is equal to the sum of p of eta p of, I guess, it's sigma a. Here summed over eta. So that's just ordinary convolution. And p star k of sigma is the chance of being at the arrangement sigma after k switches. So there I've written it down. And then there's the uniform distribution u of sigma, which is 1 over N factorial. All permutations equally likely. And I want to know how large this, well, Pankeray actually was the first one to show. The 1890s that p star k converges to u. And k gets large, which just says if you shuffle a deck of cards a lot, it gets all mixed up. And you already knew that. And I want to know how fast. And so in order to tell you that, I have to say one more definition, stop for a second too. And so the distance between shuffling k times and uniform, this is one good way of defining it. P star k of a minus u of a. And maximum over a in Sn. And so here's what this says. A is some set of arrangements of the deck of cards. Maybe all arrangements of the deck of cards with the ace of spades is in the top half. And p star k of a is what's the chance that the deck is in that set of arrangements after k shuffles. And u of a is if the cards are perfectly mixed, what's the chance? Take the difference between those two numbers and then you take the worst case of that. That's the distance that we often use, total variation. And with all of this specified, there's now a math problem, finally. Given epsilon bigger than zero, how large k, except so that the distance of k is, you know, the distance of k is less than epsilon. That's now a math problem. And. I have a question. What about just choosing one part of it and putting it in for choosing? There are a lot of algorithms for generating a random. Does that work? I don't want to answer that right now. I'd be happy to discuss it offline. Not the right time for that question, but I'd be happy to discuss. There are lots of algorithms. I just try to say the standard one. I'm just wondering why it doesn't matter if you've got a system. Well, I don't know either, but I told you the one that they used. So that's yet another question. So with Miradat Shashahani, another longtime friend of Barry's, we figured this out. And the way theorem comes out is this way. If k is one half n log n plus cn, c is bigger than zero. I'll explain this. Then the distance of shuffling to random is less than or equal to 2 e to the minus c. And this c is the same as this c. And what that means, well, that means if you want to know how many times to shuffle to make this less than 1 in 100, you write equals 1 in 100. You solve for c and then put that into here and that gives you the answer. And there's a lower bound that matches this. So that was a, now if you want to do that, I want to learn how to do this and then learn how to do that. And so that's what a theorem looks like in the subject. I think this was the first such theorem in the sense of a short quantitative bound. And I, in 1985, I gave this same talk in this same room. Barry and David Mumford were interested in having somebody in the math department who knew about combinatorics and probability and asked me to give the job talk. Although I didn't know it was a job talk, but anyway, I did talk about this because I just written it all down. And I should say by the way, the answer's around 400, I mean, or something like that in order to, and we know why it's not random when it's not random. And that did explain the anomalies in our results. And after my talk, Barry, as usual, I saw him talk after talk, came up and said, that was great, and thank you, man, a lot to me, still does. And he said, but the reason your argument works is because the set of transpositions is a conjugacy class in the group. And what you're really doing is taking the element in the group algebra, which is the sub of all transpositions plus the identity, and then raising it to a high power. Well, you could do that for any group, you know, any lead type group. And he was going on and kind of sketching out a program of research. And we're friends, and after about five minutes or something, I said, yeah, but what's the story? Why would anybody care about doing whatever I was just doing on a lead type group? And Barry didn't know what I was talking about. And after another five minutes of my trying to explain, he said, I see. He said, what you don't understand is that in mathematics, somebody else makes up the story. There's some truth to that, and there's a wonderful history. The character theory that I needed in order to prove this theorem was done by Formanius for just the craziest reason. The determinant of a circulant is a product of linear forms in the entries. And I mean, who would care about that? And character theory came out of that. So stranger things have happened now. But Barry's thought stayed with me, even though I told you why I was doing this problem. But I just came. Sometimes takes a while for the ideas to mature. I just came from six months at MSRI, where a group of us are doing exactly what Barry laid out, that is, take a lead type group, say GLM over a finite field, and take a conjugacy class like something like transfections or any conjugacy class. In fact, these are all simple groups, and almost anything will generate. And then you can do the analog, make the random walk. And with a group of very wonderful group theorists who I've corrupted, it's his fault, but I've corrupted them, there's a kind of unifying result which is more or less, but really more or less, that is essentially always. For any lead type group, any conjugacy class, the identity, etc., the rank of the group is necessary and sufficient in order to have things be random. So took a while, but I did finally follow. And I have no idea why we're doing it. It's just the math is nice. And now I want to say, what else do I want to say about this particular thing? Really the reason I told it to you is it is my favorite story about stories, but one thing that came out of this result, just a lot of smart people here, this particular thing, if I graph it. So this is K, the number of shuffles, and this is the distance of p star K minus u, how close we are. And this distance that I'm working in is the difference between two numbers which are between zero and one. So it's between zero and one. And it's zero if the measures are the same, and it's one if the measures are completely distrubly supported, and what this theorem says is something a little surprising. It says that this distance behaves with a sharp cutoff, and this cutoff happens at a half n log n. That's where this cut, that is this going to zero happens in the second term of the asymptotics. So if you were to make a plot, and it's an outstanding conjecture in the field, let me say it twice, take any set of permutations that generate the symmetric group, any wave shuffling that you like, and start shuffling with them. There is a sharp cutoff, that is there is this cutoff phenomena happens for any generating set, and a marvelous development that came from this, we made a theory following what I told you about, which says if you know all about one way of shuffling, if you have very, very sharp answers for one way of mixing things, then you can get good answers for essentially any way of shuffling. It's called comparison theory, and that's now a machine on its own. Using comparison theory, Rijuk, Shirash, and Helfkart, I think an inverse order, proved that you know if you pick two permutations at random, they generate either Sn or An with probability, well, one, and they generate Sn with probability three quarters. So pick two permutations at random, say a transposition in an encycl, but any two permutations, pick two permutations at random. The mixing time is of order NQ blog N, and that's the worst, and we conjecture that there's a sharp cutoff of this sort, and in fact we conjecture it for any set of generators for any finite simple group, but there's just a handful of examples, and this is one of them where we've been able to prove that there are cutoffs, in particular for a transposition in an encycl, we don't know. I believe that there's an explicit constant such that NQ blog N plus C is the right answer, but we don't know. So those are math problems that come from this development. But more than that, it is a typical example of how I get involved in a problem and what happens from it. So that's enough without shuffling cards, and you should be happy because I just finished teaching a graduate course on the mathematics of gambling, and they had to sit through four weeks of shuffling. So this is all you're going to hear about today. So in case you're tired, it's the last thought. Wake up, new talk. So my second story, I want to tell, those of us who've been participating, I hope most of us were lucky enough to have heard Elaine Scarry talk about Plato's poetics on Wednesday. It was just made these wonderful texts come to life. Well, I'm going to talk about Plato. It says it right there for a few minutes. So one of the things that we don't know, so Plato wrote a lot of famous books, the ones that have come down to us, and we don't know what order he wrote them in. So Plato's Republic was written early, Laws was written late, and the others. And it matters if you're a Plato scholar, that is, because he changed his opinion, it matters. If you're trying to interpret, how did he come to? So that's a question how to seriate the books of Plato. And there's been endless articles written about that. Well, he was whilst here and while there, you can imagine the conversations going on and on. And around the late 1950s, a Plato scholar named Brandwood decided to go get some data. And Plato said that he systematically changed his rhyming pattern over time. And so what Brandwood did was recorded for every sentence the last five syllables and the sentence, whether the stresses, whether they were longer or short. And so, for example, Plato's Republic has around a thousand sentences in it. And for each of those thousand sentences, Brandwood recorded a binary vector, it was in this kind of language, of length five, long, short, short, short, long, if that's what those symbols mean. And then the notion was, the thing that he did and that I did, was let's look at, well, so there are 32 possible binary vectors, all possible patterns from all short to all long and everything in between. And so I would have a function f of x, if x is a possible binary pattern of length five, which is how many times did that pattern appear in Plato's Republic and in the other books, f of laws of x. And the idea was to look at, for example, Plato's Republic, which we know was written early, and see if these numbers show some pattern. And then if that pattern is different in laws, we could use it to seriate. That was the notion. And using, I'm not going to say in detail how that came out, but if you're interested, I think if you type in Percy and Plato, it's a paper I wrote with Julia Salzman. And not quite what I want to talk about, but that's an example of analysis of binary data. Well, there's all kinds of binary data. It could be that I'm looking at a string of zeros and ones, x1 up to xk, which may be of length 12, which was one or zero as that worker was employed or not in that month. And the current population survey gives me 5,000 workers and vectors of length 12, and it tells me what f of x is for those workers. And again, you could try to make sense out of those numbers. Or there's lots of a class of students, and you gave them a true false test, and you have how many students had this pattern. So there's lots of examples of binary data that one wants to analyze. And what I want to get to, so that you know this is how it started, I want to get to my own personal elliptic curve. So I've got a ways to go. So when we analyze data of this sort, we often replace the data by various averages. For example, it might be that I looked at all, I sum how many people, how many people, how many sentences began with one. How many sentences have a one in the I place. How many sentences have one zero in places, i and j, etc. So we often analyze such data by taking averages of the different functions, of the functions that come up, and then that helps clean up noise and allow us to make sense. And from this analysis, I was led to find a quite simple striking pattern in the Republican laws that were quite different, and when we use that to seriate the books, the majority opinion was vindicated, I'll put it that way, and it has had some impact on this tiny little area of scholarship, the fact that some math also pointed in the same way as other arguments. Okay, so if you have data, so I'm now, suppose we're given one function on binary k-tuples, and you are going to take certain averages of it, and so I'm going to specify a class of averages, let s be a subset of 2 to the k, a fixed subset of k-tuples, and then you could define the ray non-transform f bar of y, so I'm given f, and y is a binary vector, and this is the sum of f of x, for x in s plus y. So s is something like a ball, and what you're doing is taking your function and averaging it over a ball around y, that's a kind of common thing one will be doing for a second at any rate, and so you replace your data by some smoothing of it. Now a natural question, if you're doing stuff like that, if you're massaging data in that form, is well, can I, have I captured all the juice in the data? Well one pale version of that is given a bunch of averages, that is fixed in s, for example, and suppose I can tell you all of these averages, can you reconstruct f from it, or is there something hidden in the averaging process that is now invisible to you? And so a kind of math question is given s and f bar of y, for all y, can we reconstruct f? And this is, is the ray non-transform invertible in this situation, and there's no shortage of math and developments about properties of replacing a function by its averages over a collection of sets, and this is one that came up to me that I was interested in, and many other things, but I want to get to my favorite lift and curve, and I've got to go pretty directly to it. And so let me tell you some news, the news, the bad news and the good news. So the first piece of bad news is that, well first of all the good news is, the start of Larry's conference, the start of the good news, if the size of s is odd, you can always reconstruct. Okay, that's not hard to see, and it's true. But sometimes you can reconstruct it, it's important to reconstruct when the size of s is even. And, okay, well the first piece of bad news is that for most sets s of size 2k, you can't reconstruct, you can't. So the ray non-transform isn't invertible, and that's uniformly in k, actually. And here's the second piece I'll keep down here, maybe you won't be able to see it. A second piece of bad news is given a single s, and you can ask, given it, can you reconstruct? That problem, it's a yes or no question, that problem is NP complete. So there's not going to be some simple algorithmic way of doing it for general s. So that's maybe bad news for certain sort. But here's some good news. For many natural s's, because typical s and worst case s, of course the trouble could happen, but for many natural s, it's okay. That is, you're not losing any information. And the class I'm going to tell, the class that led to an elliptic curve, was balls in the hamming distance. So let s be equal to the set of all x, such that the number of ones in x is less than or equal to r, say. Okay, that's a ball, fixed ball, where this is the number of ones in x, the hamming metric. And so suppose I replace a function by smoothing it. Can you reconstruct it? It's a math question that came up in the middle of doing the analysis. So now it starts to depend on r. So, okay, so it starts to depend on r. And so I have two parameters now. The diameter of my ball and k, the length of my vectors. And so when r is one, so everything within one of me. It's okay if and only if k is odd. Okay, so that's a theorem anyway. When r is two, so everything within two of me, you can reconstruct if and only if k is not a square. So mostly you can reconstruct. Okay, that's good. r is three. It's okay if and only if k is odd and not a square. Okay, it's getting more and more okay. And when r is bigger than or equal to four, okay, just slightly bigger balls, it's okay that you boys have any reconstruction except for finitely many k. So that's already uses some classical piece of number theory, but not, okay. So I started in working on the question of, well, all right, what happens with four? I know that there are only finitely many bad values of k. Can I find them? What's it about? And I want to just write down what this has to do with anything. So let me write it down. So when r is four, it's bad, that is, you can't reconstruct if and only if. This polynomial, z to the fourth minus twice three k minus four z squared plus three k times k minus two has an integer zero, integer zero, zero plus three k. So there's a diafantene type condition, the k's which are bad, or the k's such that this is the fourth Grotch-Uk polynomial for people who like orthogonal polynomials and that's when you can reconstruct. Well, okay, this is work done with Ron Graham who then had a team of programmers and we went to the computer and so the bad values, I'll write here, so what are the, what are the bad values of k? Well, it was bad for k equals one, two, three, eight, seventeen, sixty-six, one, five, two, one, and fifteen thousand forty-three. Okay, so sometimes it was bad and we looked pretty hard and we thought, well, is it possible that that's all? Now for those many people in this audience, this is essentially an elliptic curve and so let me write it down that way by an elementary transformation, figuring out it, so I have two parameters as z and k here, so this is, let's see, up and down, so just to try to make it look more like something this audience might relate to, this is equivalent, equivalently, this is the curve, y squared is equal to six x squared times x squared minus one plus nine and if you prefer Biasdras form, u squared is equal to four v cubed minus fifty-seven v plus fifty-three. So you needed to find integer solutions of these equations and we know that there are only finitely many and it's a question about whether we found the largest one or not and it's just a little corner of work but I was very pleased to have an elliptic curve that I met on my own terms without somebody saying, well, this is a famous thing, there it came, I mean it just came from seriating the books of Plato and so I went to Barry and I said, hey, I've got my own elliptic curve, and it looked at me, but we're friends so he listened up and he got very, very interested in it and he put the word out, whatever that means but Barry calls you and says, and I asked him, why are you so interested in that curve? And he said, you know, curves that come up in nature from some other cause that are, you know, often have a way of reappearing and you know, curves that actually come up in the real problem deserve respect and I, thank you. And through a chain of events, but it really did start with Barry and I wrote their names down and I'll mispronounce them but let me at least try to say it, Stoker and DeVeger showed that we found all the integer solutions, except for this list of Ks you can always invert the radon transform when you are averaging over balls of size four. Anyway, it's a little kind of corner thread of applied math but it was one in which Barry really did make a difference. Their papers, well, okay, it's actually not easy to show that you found all the solutions, maybe it's easier since they did it but, okay. So again, I would wake you up when you were awake anyway, right? So here comes the third talk. And this talk, this is about wandering around on the streets of Paris and here's how it goes. So I'm interested in many things, some talents, language is not one of them, okay. So there I am, I was teaching it or say living in Paris and wandering around. Because you walk and you walk and you walk and you walk and you walk and you walk. But I, you know, didn't, my French is just poor. And so I noticed I was using an algorithm to maneuver around, not a map of course. But you know, oh that way, I went that way before, I kind of recognized it, I'll go that way. That is, I was wandering around the streets of Paris using the algorithm that streets that I walked more in the past I was more likely to choose in the future. And let those of us who have not done such a thing cast the first stones. And at some stage I decided to try to make a math problem out of that. You know, how can I, that sounds like something I should be able to mathmatize. So let me tell you what I did. Let's take the simplest case, let's take a triangle, here it is, A, B, C. Okay, and I'm going to put weights one on each of the edges. And imagine a random walker who starts at A and then picks B or C at random, maybe he goes to C. And every time he crosses over an edge he adds one to the weight of the edge. Okay, and when you're in a new vertex you pick where to go with probability proportional to the weight of the edges leading out of you. Okay, so that's what I was doing and I just said it as math, right? And so now the question is what happens? Okay. So this is a triangle. So let's see what would happen. So here two thirds of the time I go back, so maybe I go back and now I'm here again and now three quarters of the time I go back. So one natural thought is you wind up dying on an edge. You go back and forth and that's what you do, okay? That's one natural thought. And the second thought is what can't matter what happens at the beginning, you wind up spending your third of your time in each vertex. Because those are the only two natural guesses and both of them are wrong. And so there's no natural third guess that I could think of. But it's a simple enough problem that it must yield to thought. It's just a triangle after all. And I kept thinking I'd see it and eventually I blasted it out and it was hard work. And I want to tell you a sense about it, first let me tell you the sort of bottom line of it. So again, if NAB is the number of times I cross AB after N steps and I look at NBC, N over N, NAC. So this is the proportion of times I've crossed each edge. So this is a vector on the simplex, the numbers at 7 to 1. And it proved that this converges to a limit, theta 1, theta 2, theta 3 on the unit simplex and N goes to infinity almost surely. But this limit is random. So if you started with a fresh triangle and you did it again, you would converge almost surely, but the limit where you converge to is different. And each time it will be different. And so then it's a natural question. Well, there's some limiting probability distribution on the simplex. And I know lots of them. My community knows lots of them. And I did figure it out. I'm going to write it down in a second. But it's nobody's friend. So not one of the standard ones. I just write it down. It's not far away. I almost remember it. So the limiting density, this has a continuous density. It was xy plus xz plus yz to the 1 half divided by x plus y times x plus z to the 3 halves times y plus z to the 3 halves. And it's pi. It's a normalizing constant. And here, I guess, this is x, this is y, and this is z. Those are. So it's a funny density. And I once was at CCR. And I said, I'll give 100 bucks if anybody can show that this pi is the right constant. It's an integral over the simplex. And why does it integrate the pi? And some kind of end did it sitting there. And I thought, Richard's dong. And I paid 100. That was the hard part, is to get them to take them. Anyway, so this is the limiting proportion of time that you cross each edge in some funny, funny limiting probability distribution. Now, so let me just say this. The same story I just told you is true on any finite graph. So if you take a graph, it could be a square, it could be any kind of finite, say, simple finite graph connected. You start random walk with reinforcement. That is, you put one on all the edges. And you move, and every time you add, you add one to the edge. The same story is true. That is, the proportion of times you cross each edge tends to a limit. That limit has a density, which is absolutely continuous. And there's an expression for it, which is a little bit worse than this. But it's worse than this in an interesting way. The description of the limit uses the first homology group of the graph, Pi 1 of the graph. And it's the only theorem I know about in probability where anything about homology comes in. And I'd be happy to be corrected about that. But now, what does that have to do with Barry? So as part of our long conversation, I have often tried to teach Barry probability. How to think a little bit like a problem was. And it hasn't been easy. So one of the ways that I tried is I said, well, you know, and he wants to learn. I mean, speak all languages, including mine. And so I said, well, next time I'm, you know, in the middle of some problem, you know, we can do some calculations together so you get a feel for what it's like. So let me say a sentence about what is behind this. This random walk with reinforcement, that's what it's called, is generates a stochastic process. So X naught, where you are, say that's A, and then there's X1, X2, etc. So if you wander around, you know, where you are is random and I'm giving them names, calling them X naught, X1, X2, etc. And I guessed from examples or from having done things like that for years that this process, for any graph, this process was what's called partially exchangeable. And let me try to explain what that means. So if you take two possible realizations, so all the strings will start with A, but well, so for example, suppose you start A, B, A, B, C, B, A. That's one way your process could start. And another way it could start is if I switch these two blocks, B, C, B, A, B, A, so I just took this block and this single block and switched them. That's all I did. These two strings have the same transition count matrix. That is if I make a counting matrix, here's A, B, C, A, B, C, how many times in a string did I go from A to B, etc. Well, it's zero along the diagonal. How many times in this string did I go from A to B? Once, twice. So from A to B, I went twice. From A to C, no, no times, okay. From B to A, once, twice, okay, etc. Let's, well, we can just do it from B to C, I went once, okay, from C to B, C to A, C to A, zero, okay. So that's the transition count and this string has the same transition count matrix, okay, and you can get, that's if and only if, you can get one string to another by switching blocks in this way. And the claim is that for random walk with reinforcement, if two strings have the same transition count matrix, they're assigned the same probability, okay. And I'd verified that in small examples and thought it was probably true, but I hadn't actually written out a proof. And I said to Barry, we were walking back from the science center to his house or something, I told him the story and he said, well, let me try that. I'm going to write it down. And the next day, he wrote out a two-page proof and honest, you know, combinatorics from ballistic proof of that for any graph, a graph that random walk with reinforcement is, it's called partially exchangeable. Well, I built a machine in somewhat before that, which is called Diffiniting Theorem for Markov chains and so this condition is called partial exchangeability. So partial exchangeability is equivalent, so a process is partially exchangeable, is equivalent to it being a mixture of Markov chains. That is, if and only if for every n, and all x1 up to xn, the probability assigned to x1 up to xn, the probability that your process goes through this string, I suppose it starts at a fixed point, is equal to the integral over the simplex of the product of theta i j to the ni i j mu d theta. So here, this is the simplex, it would be the three simplex if I was working with the triangle, but it's the simplex of all indexed by the set of all edges. And so the claim is that partial exchangeability is equivalent to their existing a measure on the simplex fixed measure such that for all possible strings, the chance of seeing that string can equivalently be said as pick a transition matrix, pick a Markov chain from this probability on Markov chains, and then run that Markov chain, Diffiniting Theorem for Markov chains. So his calculations allowed me to use this theorem and then knowing that there was a limiting measure, it's the only first way we knew that there was a limiting measure, I could then use the existence of a limiting measure to calculate by combinatorics what are the chances and this is what came out. So that's a third example. And so one part of this talk, of course, is in as much as I am an applied mathematician, what do we do for a living? So I've given you three examples. They're mostly problems that come from some real world connection and shuffling cards and analyzing binary data and well, walking around the building. In many cases, even though you've done a specific problem that came from an application, if you take the math seriously, something happens. In particular, I'll tell you one sentence of what happened from this triangle problem. Of course, you can do this on any graph, so take an infinite graph, like take the integers. And so put one on every edge of the usual graph of the integers, a random marker starts at zero and every time she crosses an edge, she adds one to the way to the edge. So there's a restoring force back and when you're at a new vertex, move to one of the vertices, the j-senty with probability proportional to the edge weights. And ordinary random walk on z is recurrent to come back to zero infinitely often. So it must be if you have a restoring force, must also be recurrent and that's true. It wasn't so easy to prove. It was Robin P. Mannell's thesis at MIT. But in two dimensions, it was open for 30 years. It was my most famous open problem. That is, is random walk in two dimensions with recurrence, with reinforcement, is random walk recurrent. And finally, Christophe Sabot and Pierre Therres proved that it is recurrent. In fact, it's recurrent on any lattice. Just to give you one more sentence about that, if you take an infinite tree, our favorite object, the infinite binary tree, in random walk with reinforcement, if you add one each time, it's not recurrent. If you add five each time, it is recurrent. And five is the square root of some solution of the trans-adduent equation. So there's a phase transition. That's another result of Robbins. And so it's an interesting problem, and it came from this. Well, the breakthrough came because the measure, my crazy measure, this mu, you can't see it, but there it is. I didn't write it down. But this mu, which involved the homology group of the graph in interesting ways, had been studied by physicists, Tom Spencer and Morton Zernbauer, for doing super-symmetric strain theory. And in an unbelievably long, hard piece of analysis, they figured out enough about this measure so that we could do the asymptotics that we needed. And then they got interested. They'd never heard of Diffenetty's theorem or this way. But it's the same measure that came out. Why is that? And there's a very healthy interaction between the group of physicists and the group of probabilists. And if you're interested, it'll be an aimed workshop in about nine months from now on the interaction. These are three instances of how Barry helped one person in applications. I bet that everybody in this audience, at least those of us who know Barry, have a similar story. It would be interesting to try to bring them together. I'm going to end with a warning. I don't think I've successfully ever finished teaching Barry probability, but we're both still around. So, yeah. Thank you. Thank you. Thank you.
of them. And these are three stories. The first is about shuffling cards. And that's going to be is about the books of Plano. And the third is about walking on the streets of Paris. And okay, of Barry's, we figured this out. And the way essentially an elliptic curve and so let me write binary tree, in random walk with reinforcement,