Merken

# Breaking barriers in probability

#### Automatisierte Medienanalyse

## Diese automatischen Videoanalysen setzt das TIB|AV-Portal ein:

**Szenenerkennung**—

**Shot Boundary Detection**segmentiert das Video anhand von Bildmerkmalen. Ein daraus erzeugtes visuelles Inhaltsverzeichnis gibt einen schnellen Überblick über den Inhalt des Videos und bietet einen zielgenauen Zugriff.

**Texterkennung**–

**Intelligent Character Recognition**erfasst, indexiert und macht geschriebene Sprache (zum Beispiel Text auf Folien) durchsuchbar.

**Spracherkennung**–

**Speech to Text**notiert die gesprochene Sprache im Video in Form eines Transkripts, das durchsuchbar ist.

**Bilderkennung**–

**Visual Concept Detection**indexiert das Bewegtbild mit fachspezifischen und fächerübergreifenden visuellen Konzepten (zum Beispiel Landschaft, Fassadendetail, technische Zeichnung, Computeranimation oder Vorlesung).

**Verschlagwortung**–

**Named Entity Recognition**beschreibt die einzelnen Videosegmente mit semantisch verknüpften Sachbegriffen. Synonyme oder Unterbegriffe von eingegebenen Suchbegriffen können dadurch automatisch mitgesucht werden, was die Treffermenge erweitert.

Erkannte Entitäten

Sprachtranskript

00:03

the term can I tend to take good good morning and thanks for all being here so In after getting this invitation I decided rather than focusing on the kind of 1 1 work probability I want to give you several examples of an approach that has been useful for for me hopefully can be useful for you which is 10 seeing anything connections between different areas either within probability or adjacent areas that use probability theory and on so I will give 3 examples necessarily not going into all the details in them there and these are the example they work done over the years and some of them were not rescinded or the 1 example and tell you about it itself is intersection equivalent to that is something I worked on 20 years ago then 1 example is 2nd example will be broadcasting the country worked on also some time ago and then something more recent from the last 3 5 years which is still delivered developing which is the connection between the cover times and in Gulston process specifically the Gulf and so it's a different examples but the the common theme is in in all of them a lot of the progress is made not only by you know trying to work hard and solved a heart problem that's always recommended but also looking is there a solution of a heart problem in another area that can be useful for the problem I'm interested in so had so this example of intersection good let me go back to the background I really to something very very also theorem of there the significance of tiny and dude from there in from the forties which tells us which sets are hit by Brown in motion and to be concrete let's focus on 3 dimensions the skin the adapted to any dimension so suggested concrete I want to focus on our Korea but on so I have given I'm given some In some compact said K and I want to know where he does Brian motion so be would just be the path of right emotions when the brain motion hit the city Toronto and promotion of the Saturday was positive probability and fear of good ideas this is only a day has positive in one-dimensional capacity so In the years is bigger than 3 than the 1 you replace your by demons to and here it so what is the capacity of its said the inverse of the minimal energy so we take the minimal energy the measure In the birthday and this is a measure of probability measure on and here the versatile defender of capacity of but this would be the of energy and the of energy of a measure is this is a call the week With energy so we will continue Exxon knew why I will work closely the other facilities are known as high as there is capacities when he put out the hear the case of officals managed to distinguish and you Newtonian capacity but and it has been all this can include dimensions things are a little more delicate have to talk over with the capacity that focus on 3 dimensions so this is the classical thereof Cook Danny and and so when actual question what that was open for many years in the Indian people work on it a lot in the 80's Was that I want the same thing for told Independent Brian motion so they have won bronze in motion Everything is in our 3 4 concrete and have another Ryan motion path me to leave the independent running back it I had in mind just so in there is an annoying thing that usually Brian motion started the origins of the universe that is contained the origin and will intersect so I want this set not to contain the origin of tentatively it's better to think and we will do that and that we started the brand instead of actually origin let's started at the uniform .period in box so I didn't see this in the beginning either I have to take a removed from the origin or I have to start not at the point so let's do the latter soul let's think of the initial points of Soviet times 0 would be uniform is unwell but say their unity OK and then I take the 2 it's an independent Brian motion is the 1 and analysts have an independent promotion started it in another uniform random .period I want to know when does this so it's also very classical the two-run emotions in our 3 intersect with positive probability and In so there is a ready jump here so it but until then the question is when it is In and if a intersect the motions so when ready in classical theory of direct here just tiny the children motions in 3 dimensions will intersect with of probability but I want to intersect with the set again some compact said but in no way Nunavut the intersection on and was born in Providence and what is quite easy to show is that it's enough that the two-dimensional capacity so just to get an idea of the other dimensional capacity is closely related to opt for the mention of a host of measures if the sector has how's the dimension bigger than then it has positive of the dimensional capacity is today that so if accept it has to be really bigger than like a plane in order for it to have positive two-dimensional capacity I hope so this direction was was relatively easy a 2nd moment arguments in and was it was well known that this direction was opened for a long time in the 80's in various good people thought about it and there already is a wrestling those very interested in this question I didn't solve then and the 1st solution was actually obtained this is true but it's not easy at 1st solution was obtained by and Fitzsimmons and salads vary 89 published in the United Institute in conquering the very impressive solution using very nice but quite fancy potential theory and there's a sentence From

09:31

there paper the state's member so they they consider much more generous setting and which makes it a little hard to read the paper so they write down a bit we will work in the setting of special standard processes we won't define them precisely here but see page 347 and movement of the Torah roughly speaking the processes that are left continuous indirect apology this is just a roughly speaking and so but in fact you know there is a really nice approved I will go take that but a few years later found a different group which I 1 is the 1 I want to tell you about which was based on this idea intersection equivalents and and the point is that a related theory was proved by Ross Lyons in the context of percolation countries and that can be converted to it to answer this question and get some more so let's shift gears for a minute and then will connect to this soaks in the the question is In so doing today daily abroad and grasslands and which was kind of public 1st published in 92 and has probably been the paper referring to and you can also find an account of this in mind my book with Ross and which has it is about to appear in Cambridge University Press In city confined some in the position of the but the origin of papers of Ross very well written and what the hearing concerned is the following questions so I have a treaty that's not the a regulatory some general tree and and then doing percolation on the tree with some parameter peak so so what does that mean we have so every edge you opened With probability independently and then we can have some wrote and asked What is the probability that they know that the route is infinite last component opened last and the answer is that they have to a constant indeed up to a factor of to all this is put to be the equivalent to the capacity of the boundary of the tree In a right to that because we're in the tree and and here I want to please use the following addition from going to take repeatedly to the mines of and so to define the capacity the very have a metric because we have the distance so so what is the boundary of the tree the banditry is a set of infinite race in the past from the route and if I have to To raise I'm willing to consider the distance between 1 CSI and another a out to be can take to the minors so you could put of the miners the new 8 so what is this is this is the point that I have the 2 tasks the indicator to raise this to the point the minimum made that this is the the root this is the point where the 2 who raised separated and this absolute value means the number of images from the route to the separation .period and this is the way it 1 of the natural matrix on the tree boundaries and then the rest of the deficient proceeds as about so the outside energy output to tended remind us that there were in the tree of the founders of the tree is just the Intergraph the UK's the new later all the distance between the sea witnesses said for distance the but if it so this is a good deal of the integration this is the distance I hope that's OK and I would take the distance to the power of fire this this is the of energy so and this is lines them so again in the ad in this morsel 1 direction is is easy to show that he is to show that there is a probability of at least the capacity of the 2nd moment argument the other direction needs some kind of it is a mark of property so bitterly about hepatitis 0 and you know many pros Cook dies serum but really the only reason they it works well in both directions in 1 direction you just a 2nd moment in the other direction you use a mark of property of Brian motion namely in ending if you know that the probability of Brian motion intersecting positive then In you want to show that the capacity is positive stuff to find measure of fine at energy what will be his measure it would be the hit the measure by Brown motion of the sector so you you are given the data that the brainwashing hits the and to construct a measure you just using and then the fact the mark of property around motion can be then used to control the energy of the measures have as in the tree it is so Russell didn't exactly expresses his proof like that but you know later I want to send you to a different paper and called Martin capacity in that has a long title but this is it with the command of and sales of 95 also in animals probability where we explaining the last theorem in a way which is close to Cook dies namely disposable percolation and you look at all the vertices interconnected by all so that it just go to level and look at all the practices that are connected by open paths to the roof this is it random subset of the boundary in this case were just doing it if I had version of the boundaries are just going to Neverland but the nice thing is that if you go along the way this final boundary of the trees along level and and just jumped left to right just along the to that are connected to the route this is a mark of change so if I had if I'm here and I'm connected to the rule by an open path than to find where is the next verdicts connected what happened to the left is irrelevant because of the tree structure In this mark of property is really 1 way to understand what makes you the nontrivial direction in announced their work so it's really the connection to that so so once you have In lands steered the point is that if this is an equivalency and now Have we want to think about it not only on the trees but in the context of Euclidean space where there is a natural mapping from trees to clear the airspace just beyond its expansion or binary expansion so that we have I'm so sick of research show we want to realize that the connection between trees and eucalyptus space so you can use expansion in the case of offered few we would divided into 2 by biting so if in 3 dimensions get 8 cubes and this gives a natural

19:00

structure the 8 every tree every verdicts of 8 children and if I have some said a let's suppose that the city is in there it is in the queue so we can always move the steps to the cube so we can assume that we're talking about sex in the queue then has it within his the buyer expansion to find treaty so the trick all by nearly people 3 of binary expansions full points in so it is now set in 0 1 but kill a conductor this is we look at this history if a was raises the whole kill the tree would be in the form of a territory of the verdicts of the children with the various Asmara compact that Princess if they may be doesn't intersect this Cuba and already in the 1st generation instead of having all 8 children I have fewer children and so on so just by looking at the geometry of a which binary cubes intersects I can easily build this binary tree and then In once during in this form last theorem can be In extended so it was so now I'm going to in and look at the random sets Orlando its call Landover of this would be an inside that Cuba is to be around them said obtained by our way ,comma random random factors will affect proclamation he is obtained everything cubes with probability the tension the Internet and oneself the amendment but this and drawing two-dimensional pictures but then got the dimensions so I take the the cube divided in 2 3 and into the future everything with probability p if I remove it you know then I it's not going to be said they are your 1 now I have these each of these again subdivide and I retains probability .period move was from the woman's B and so on this is the class the construction of Procter percolation but we sit just corresponds to percolate if we enacted back using binary expansion just corresponds to percolation on the tree and therefore has weakened expressed it Lance theorem in the point in the form to the probability all random said land of intersecting affixed the said in this probability is equivalent to the capacity all they think so actually I should put the question the cheery responding to it In an facility just the translation of lines there and in this In this kind of setting is this is just the probability that the when they do percolation on the tree corresponding to a I have survival in the trees that corresponds to this intersection being on the but in no if I want to think of this to the capacity the capacity the fund to think of a geometrically it corresponds to a slightly different matter acquired the distance between 2 points in the queue was not there Euclidean distance but it's pretty close it the minimal binary killed that contains both of them so that usually like the distance but not always if the 2 points are you know very close to they noted very close a boundary like if the 2 points are here then there including difference is small but the tree distances large nevertheless there is a theory that says that the capacity of In theory in providing the mental and myself that the capacity to that is equivalent to the capacity of effect so although the metrics are not you know they're not to buy leeches equivalent at all but a capacity is sufficiently flexible that that 1 cannot 1 to the other this argument is really just based on "quotation mark Schwartz it's not hard I know once we have been then we are in in good shape because now we can state 1 connection we already see how we doing boards you look good so so putting this together so it was couple times here and we see that the probability that the Bryan motion its colleges 1 intersect is not meant it is equivalent to the probability that the well under 1 the number 1 is remember said corresponding to In the index 1 interested players I because both of these things in question with :colon something that can to fill in some of these things are equivalent to the 1 capacity of the city OK in Have we made any progress so what 1 thing is you see that this is Watson and Ponting intersection according so the random set B 1 the path of a rise in motion started uniform in Q he is at least inside the Q intersection equivalent to this random effects of these do this random factors the SEC's look completely different the topological properties are very different but the intersection properties of the same given name the domestic targets Centocor Inc on any targets at which is independent of these of the sex then to ask whether intersects 1 is equivalent up to constant to ask whether into intersect number 1 and so OK so why this useful because it's very easy to understand what happens when we intercepted 2 independent copies of this Sept so remember what was our goal to understand the big B maybe 1 and intersect With the tool and the 2nd In London the same way as this known well let's think of this as some said frees me too and now we know that this is equivalent by the the probability that call Landau 1 oneself this is so this 1 just corresponds to the problem parameter unfunded this 1 means I'm going to take notion 1 copy of the set intersect the 2 I'm just because none right so this means equivalent of 2 constants won't care about the value of the constants now this is supplying the fact that we obtained using about replacing the sustained by the said the 2 intersecting so you just condition deal and apply the previous day OK but now use commutativity of intersection so you can look at this the other way and this is equivalent To the probability so beaten this is now being 2 intersected with a Anderson so I can now In uses the same principle again to say equivalent to In London 1 intercept land that was once a visit to independent copies of all of these random said land of 1 so that might what is this said land of 1 very simply take the cue divided in and each sub just keep was probability half and removes was to have been repealed so that's now under 1 and we have to independent copies of this and we're still in the 2nd McCain Have we made progress yes because this

28:27

intersection is easy to understand I told you about this friend said to intercept 2 copies will do that we had landed this is exactly landed 2 right because if I'm taking intersection to cover it's the same as taking a cue and saying I keep it was from India quarter instead of the have landed 2 3 London of to just 1 2nd of 2 into the air but now I have lion's theorem or our variant of it is applied with parameter of sleep was doing so certified for equals 1 needed this is equivalent to the capacity to 12 To get a very soft proof of this it's in Fitzsimmons on various here and in this case In but we can't but the intersection opponents gives you some more information which was not so their although the view that the film doesn't actually give you everything you can obtain from this techniques it does give you there are some advantages to their technique there some advantages to this so both could both useful and the point of showing this example of the unknown more than 20 years old is that if you have a heart problem well if you can solve it's great if not maybe this problem has been solved in a different language or keep your antennas up to see is a problem that is being attacked in a different area which is really equivalent to your question now and that's it didn't put away my clock so what that kind of thing then there the clock so we have 10 2020 objectives and has appeared so that had a nice story about a broadcasting countries a worlds television in that kind of detail but before on any questions about this story intent on if you look good you want to see more about this scenario if his search for intersection equivalents as a paper in communication that physics from the 19th and all of this is also covered as I mentioned in my book with thrust the board that is I think the 2nd example which I will give any detail on but this is a good example where which I heard from 1st heard about from several computer scientists at so 1 it was then in France and is back in France yeah few kenyan and Leonard shoreline and also managed to conclude with evidence and they were computer scientists interested in the following kind of questions so you have a big 1 that means put the bid to be a plus or minus 1 and this made can be and we have to shrink and that it can be flipped with probability epsilon so we have if I have here here's some in data from being you're going to get Miner said With probability Epsilon and I'm going to get and from within 1 2 of this is true on on every edge of this this is called binary symmetric channels probability epsilon you fled with her with the 1 exception you don't so you have that said started with a plot the usually have a bluff but occasionally it was probably gets along I have my I have the concern now this came from a problem in noisy computation water won't tell you about but they're really the question you're asking if the ball they see the individuals In generation and think of and is very large so I see this being in duration and that giving information what was the original thing Of course this depends on the Epsilon so Saturday's thinking about this problem but I think so you may want to think of it 1st on the binary tree but we understand that on any tree and anyway there then we just tell you the answer don't have time really to explain the case but the key thing is that meets for for the Eritrea so if 1 collapsing on is less than 1 4 the square root of then they then information title so the mutual information between the road and everything level and goes to 0 exponentially and and if 1 and to epsilon is bigger than 1 over the then the information survives sold the mutual information states bounded below which if you see this level you can never be sure of what was here but you have some it's useful information that doesn't die out so this is the paper called broadcasting on trees and easy on and the case of survived Gary trees turned out was already solved by ease the grabbed Nova in the setting of using than on trees but we did that and not just that case but in the case of general trees so for general trees replaced for general trees replaced being by 1 over the critical percolation probability of the tree and this is actually using some of rough lines there on 1 could extend this to understand this process and any tree there interesting part of the story as it turned out to you I have friends in different areas and they talk to some of my math melody friends and attended this question saying question was investigated heavily in math biology is it .period model for understanding and few genetic reconstruction so you have but the Contras DNA and you see how it evolves through mutations and you want to understand given the present population what can you say about at the corner of the end of some Asian engine and sister and there it's really not binary but this is kind of the 1st .period model that they were looking at and they hadn't been in biology they hadn't even obtained the shock result for for for the beer retreat by that time although there was no some Ph.D. thesis on it and so on and again this problem was investigated separately in statistical physics in the context of the evening was and making his connections were very was very useful because it turned out later that some of the techniques of the biologist although they work inferior for the binary grace there were very useful for handling more simple so L 100 also wrote his thesis was me in Jerusalem on this topic and continue to develop it further his student islands slide developed it more and this is the story which is continuing so turns out that this the crafted block model which is a very hot topic now Is it is very usefully approximated by this model so understanding this is kind of a necessary 1st step to understand because the rock model and said very hot topic which I have to recommend you to look at but I can't get into that but the point is that you know this is really probability but was investigated by people in different application areas or a different topic without being aware of each other so just you being aware of what's happening in different communities would do probability even know they're not called problem is and can be very useful OK so in the last a few minutes before it whatever 18 minutes and want to this is about the last thing where but in a different connection only be a brief survey because of the tiny the emphasis is about cover times the topic in probability but was really studied more by combinatorial lists and computer scientists cover times

37:57

for and walks on graft so what I'm telling you is a very brief survey of work and from 5 years ago with John Dingell densely and there's some later developments so Jan actually this he did this when he was stealing UC-Berkeley now he's in Chicago so this is about run the walks from graft in topics that we'll probably see some problems like many commuter lists computer scientists and the issue is how long do you need to run until you cover the reference by putting conducted says he can get an irreversible market changed its focus on simple random

38:43

walk on on the graph so Of all the weights would be 1 just doing simple random walk so this is some of the local times and hitting times and really the cover time is when we visited everywhere so has

39:05

just reminded some notations so it hitting time for me to the expected time a random walk started that you will take to reach me so this is almost a mantra could satisfy triangle inequality but it's not symmetric so consider tries it attended the commute time of the passage of you this is now a metric underground strangling quality symmetry no had the cover of Time the object of interest here which it's very natural thing to look at but computer scientists were interested in it because it is related to other reasons for determining connectivity so the company just expected time From the worst starting verdicts to hit or for the use of GE just to give you an idea here is the order of magnitude of cover times of different from different graphs you clever Patterson squared complete graphics just coupon collecting its annual then why did the dimension grid it was determined up to a constant in you 89 no squared then but determining so by any hearing me the number of points this is a routine and Beirut with and read it during the right constant In front of a it took a lot of efforts work did with the Morrison's it but I'm not going to be interested in constant source of this gives the order of magnitude of cotton and some graft but and some general bounced cover times are always at least an organic and that most in Q 1 and Q but playing so it would be useful in understanding covered use the notion of effective resistance many of you know that 1 way to think of you you haven't work was effectively this is 1 way to think about it is that the commute time at a defined so is the commute time identity after the 1st approved by computer scientists which is it said that the commute time is twice the number of registered the effective resistance so if you want you can think of this as the definition of effectiveness and the other definitions as well and this missing particular tells you that effectiveness it's 1 way to show the effectiveness of systematic is he decided the triangle inequality effective resistance is not obvious from the classical definition but it is obvious that way OK think and so

41:57

others and filling in the 90's asked Can you estimate the cover Telegraph up to constant the timidity of receive an estimated by running a Markov chain running the walk averaging and you'll get some statistical estimate which would be pretty good suppose you wanted to know it for sure deterministic estimate up to a constant please this efficiently so this is very easy if you want hitting times because hitting times satisfied and obvious linear equation right hitting from you to me if you different from the well after take 1 step from you and then I have an average over the neighbors of your reading from reading be this is a system of linear equations which stresses which is uniquely solvable only gives you it intact most energy but what about cover times yeah they couldn't write such equations in fact you can write equations for cover times in this space of sets and they will give you some linear system in exponentially many variables this will give you an exact solution if you have exponential time so that is polynomial time and worsened to estimated up to and I can can can always involves some of the top earlier New World showed that you can get a novel then squared approximation using what's called the Matthews Matthews abound so Matthews engaging proved denies upper bounds so the cover time is at most a maximum heating time multiplied by Slovenia when they have extra money when give longer Tucker your gives this proof it takes just a few minutes but I won't so cover time is at most the maximum hitting time multiplied by the harmonic series but there's also a lower bound to the cover Time is at least the following you maximize over a subset of the verdict said and then you minimize over you different from the European time for me to be times and although the the size of and what did these people showed is that this lower bound together with the maximum hitting 10 which is also lower bound if you take these 2 together then they are very close to shore so opulent all Rabin Square that give you the coveted but it's not up to constantly give examples that show the slow-growing squared is really there so they were motivated by the sound of the problem but you know the lot of progress but didn't quite it was another conjecture which also motivated them this is a quick conjecture all Winkler as criminal and it is concerned the blanket time so

45:00

the blanket time so when you reach the covet I visited every verdicts in the graph but non-uniformed some right the last verdicts you the visited his residence in you reached its once and by that time there will always be some other registered that I visited many times even the complete rough ride when you cover the complete grasses just coupon collector you reach some verdicts once most criticism visited Logan times by them so they asked for the blanket time which is you cover the graphic approximately uniformly they all their local times there was in fact a tool of each other so here the local time at a verdict is the number of visits to act normalized by the degree we normalize degree because at a stationary distribution we know that hasn't asymptotic if I look at the ratio of 2 local times asymptotic it must into 1 this is just the fact that the empirical distribution will tend to the station from which you were not interested in topics we want some quantitative balance and what the winters ago when looking like attended the expected time when all purchases are visited there with an effective date of each other and they made very courageous guests the guests that the blanket time is within a constant of the cover so they made this game based on whether very good intuition and about 3 examples of the ladies they analyze the because and complete graphical understand the Taurus and that's about it but then they intuition that what happened in these examples should have been completely generally and and the conjecture that the blanket time is always within the uniform constant just depend on the data so you and doesn't depend on the grass really amazing courage which had to be right so again by this and the the method of kind of sinking actually implies that their guests was right up to a Rabin Square because in this estimate that the current Ginola's will develop works both for cover time and for blanket and so you get it there within be no growing squares of each other and that you still don't know didn't denied their

47:35

winning ,comma notice I was very interesting cover times too and I worked on them with the Martin bottle in being and me off at we were really trying to understand covered thousands of specific graphs it a Disraeli grass near criticality required delicate graphs and understand the cover time there we took the approach of continuity bowl and we find it a little bit and we love the following general rebound which would apply the case the cover Time we could bound by the number of edges the times the effective resistance that diameter and the resistance rhetoric finds some Indian so this is the route to log of the entropy number so you have the verdict said and you ask and so what end of SD Absalon given effect estimated the Internet it's in a minimal number of stonewalled you need to cover the set and you're the sector the verdict said the metric is the effective resistance method and the and and the radius we want to look at is part-time jobs and you take that rejects along in the square root integrate square and this is a bound for the cover of Time 1 In this was some of the ideas in the proof were in the low but it can King who paper but you know we have to refine that little we got his band you know we submitted the paper and we're kind of in a rush and after it was submitted I was talking to John was my student dissent with the minute you know this integral looks familiar so this is very similar to the deadly integral Fergusson prostitute going back to 67 OK so so this is younger the son the differences here there's a square the metric is different but where does look similar so then know maybe note this deadly Intergraph for is a way to bound the soup of Adelson process so what is going on here so well out of this when many of you know Nelson process so access it is aghast and the governor profits the metric we use only doesn't process is just a matter given by the standard deviations of the distance between 2 points is just the way L to distance between the corresponding Nelson variables and then so this was their medallions 67 which was almost shop so this is all usually have very good bound but it's not exactly shock and actually finding the right the bound took 20 years after this deadly and when I saw this that will maybe 4 current and we don't need to go through the same 20 years we can just piggyback over on the work on the Nelson prose so for

50:46

Telegraph and you know culminating in telegram the 57 a managed to find any sharp formula for the 2 of us and process the 2 ends that naturally feel if this analogy useful can we use their theory somehow and so do To understand positive answer we have 5 minutes so we won't really understand that without an barely a few things the terms of the relevant Guston process is a famous 1 which is important for various reasons the Gulston field 1 this is had the best in the field you know studied both in discrete and continuous settings include hear something about that later today in continuous sitting in the disgraced setting it's given a graph this is center doesn't process and the variance the GX minus you why is the effective resistance between X and Y so given the grass Gee I know how to compete effectively and then I can give them a dozen bosses were this is the effective resistance and currently produced to describing doesn't roses he via its governance Colonel the governments of the 2 variables jets and you why is the Green function from X to Y random killed that some specific verdicts 0 so this is just means they start random mock attack look at the expected number of visits to what I was killing in the 0 normalized with the degree of why this week function is positive definite symmetric functions and so it's a covariance Colonel and that's the guns in the field some pictures of what it looks like into dimensions In two-dimensional artists and then the virus

52:43

serum which is answered both the outdoors Phil question and the a blanket time conjecture overwintering agreement is so it was obtained in 2010 and published in Annals math into some the thing is that the cover claims equivalent of 2 constants the number of edges times the slope of the doubts and free field on the graph squared it is also equivalent to the blanket takes over we don't know any direct probabilistic proved between the cover them the black time would obviously amended that is bigger than the cover them but the other way and we don't know any direct publicity just via analytic characters nations we can show their equipment and that if so indeed we do have to wait the 20 years it because we could just use you know some of the previous work 1 so you know there's a rich serial the maximum of Garcia processes and that I can't going to it but the there is endemic to functional 1st described by Fernie can then use battlegrounds in completed but I want to show that the soup of Augusta process is gonna do and I main fear was that the cover time you can be restated that the cover Time is equivalent to this In a number of editors found this government to square and this the allowed us also to find an algorithm to estimate the testimony the

54:28

cover time this story of damage to his very interesting but I have to I have to skip it in retrospect the many analogies between Nelson processes and even the random walk that were not really realize before so this is a is a classical inequalities in doesn't pass a ghost in the aeration that says In you if you have you gotten process and you have found separated points then you can lower bound the maximum and tell them this is very close to the Matthews abound OK so I'm going to skip the

55:10

definition of the Gulf and functional considered a crucial element of the proof which also has strong French Connection is that this is thinking is offer them theory specifically of the ambient who eyes and bound in and Napoli as inbound Caspian Marcus president and chief of at least 2 positions there and down this is an amazing fearing that the relates the local time of a process to aim to Adelson fields and in our case to adults and free field in no time to tell you anything about that but that's the kind of was a crucial element in proof and that's a horse the story

55:54

of Finnish Veneman the last 1 thing that is so we got an estimate of the cover climb but the constant but we wondered is it the connection actually shoppers is the cover time asymptotic 2 the number of edges times the maximum of the death of the square if this is true then the Taliban theory is not precise enough for that because it only estimates Justin processes up to constants when the 2 different and indeed an upper bound followed from this isomorphism series of covered his most that but we couldn't at the time the corresponding lower bound and and this was approved by John in a bunch of cases general trees and assuming uniform on and degrees and then pocket

56:45

books and then the general thing was approved by Alex Ji based on an idea also you independently found earlier by the pool and this is again goes back to making "quotation mark breaking barriers so we're talking about random walk on the discrete graphics but it turns out in order to get the sharpest result is better to look at they is capable of processing have the graphical the edges of the random walk it instead of doing a random walk on the graph you do run in motion on this matter space obtained by thinking of you on the edge of segments and it turns out that if you applied as office in theory in this context it's more powerful than applying it directly on the grass and anyone gets the completes the exact estimates for this refinement Indian is due to be Alex's I confined In his paper on the archive agendas related work not exactly the same by teachers who pulled down in Paris and that's a good point to stop thank you a copy of the letter of the law and world according to the institution so question of the situation the world said so you're doing the chief said the review of the rights and about the history of the European a federal law it's something you want to it's national our quality until if you use this so the point is that it's really so immediately this setting you have this your these bound the Cup's have some boundary intersection which creates some your superficial difficulties but the thing is we can complete the transfer the questions it too up to the treaty and really all the monetary where we have is not for you so know In will roughly speaking the printing of the aid a mark of property or obtained by a kind of random if piano curves in space but really regretting in this format is much more painful than it needs to be you just transfer the question do you know the question you have To the tree and there because the nice separation you have having the tree used a very clean not working so everything you see you doing for any consequences you want in Euclidean space by mapping to the treaty but rather than working directly including space and there is some courses for instance if you're looking at high dimensions you lose constants that depended the exponentially dimensions so this is not a good approach work and of a high-dimensional uniform restaurants but many questions we care about are in 2 2 and 3 and a low dimensions this has an analog in 2 dimensions in 2 dimensions you you have to very the progression probability as you go before so everything works just transferring to the to the tree the so it not he was back and

00:00

Maxwellscher Dämon

Ebene

Subtraktion

Punkt

Prozess <Physik>

Quader

Momentenproblem

Ortsoperator

Hausdorff-Dimension

Äquivalenzklasse

Term

Überlagerung <Mathematik>

Richtung

Wechselsprung

Wahrscheinlichkeitsrechnung

Arithmetische Folge

Theorem

Vorlesung/Konferenz

Wahrscheinlichkeitsmaß

Inklusion <Mathematik>

Grundraum

Einflussgröße

Einfach zusammenhängender Raum

Parametersystem

Stochastische Abhängigkeit

Inverse

Güte der Anpassung

Fokalpunkt

Frequenz

Vierzig

Energiedichte

Flächeninhalt

Menge

Kompakter Raum

Rechter Winkel

Potenzialtheorie

Ordnung <Mathematik>

09:29

Matrizenrechnung

Prozess <Physik>

Punkt

Momentenproblem

Extrempunkt

Natürliche Zahl

Gruppenkeim

Euklidische Ebene

Raum-Zeit

Richtung

Übergang

Theorem

Randomisierung

Translation <Mathematik>

Vorlesung/Konferenz

Wurzel <Mathematik>

Gerade

Einflussgröße

Funktion <Mathematik>

Verschiebungsoperator

Ereignisdatenanalyse

Parametersystem

Addition

Multifunktion

Dimension 6

Kategorie <Mathematik>

Endlich erzeugte Gruppe

Binärbaum

Kommutator <Quantentheorie>

Frequenz

Teilbarkeit

Konstante

Teilmenge

Arithmetisches Mittel

Randwert

Menge

Betrag <Mathematik>

Kompakter Raum

Würfel

Rechter Winkel

Konditionszahl

Beweistheorie

Tourenplanung

Perkolation

Geometrie

Aggregatzustand

Standardabweichung

Subtraktion

Ortsoperator

Hausdorff-Dimension

Gruppenoperation

Klasse <Mathematik>

Zahlenbereich

Bilinearform

Äquivalenzklasse

Physikalische Theorie

Topologie

Algebraische Struktur

Knotenmenge

Arithmetische Folge

Warteschlange

Zusammenhängender Graph

Indexberechnung

Abstand

Leistung <Physik>

Trennungsaxiom

Einfach zusammenhängender Raum

Linienelement

Mathematik

Relativitätstheorie

Schlussregel

Unendlichkeit

Integral

Energiedichte

Wärmeausdehnung

28:27

Resultante

Subtraktion

Punkt

Prozess <Physik>

Wasserdampftafel

Physikalismus

t-Test

Kartesische Koordinaten

Statistische Physik

Sondierung

Äquivalenzklasse

Statistische Hypothese

Symmetrische Matrix

Übergang

Topologie

Überlagerung <Mathematik>

Theorem

Randomisierung

Vorlesung/Konferenz

Wurzel <Mathematik>

Gerade

Quarkmodell

Einfach zusammenhängender Raum

Parametersystem

Mathematik

Endlich erzeugte Gruppe

Überlagerung <Mathematik>

p-Block

Binärbaum

Kommutator <Quantentheorie>

Frequenz

Rechenschieber

Objekt <Kategorie>

Quadratzahl

Kombinatorik

Menge

Flächeninhalt

Rechter Winkel

Beweistheorie

Mereologie

Ablöseblase

Perkolation

Aggregatzustand

Numerisches Modell

Grenzwertberechnung

38:43

Größenordnung

Subtraktion

Gewicht <Mathematik>

Punkt

Hausdorff-Dimension

Gruppenoperation

Zahlenbereich

Gradient

Ungerichteter Graph

Gerichteter Graph

Computeranimation

Überlagerung <Mathematik>

Zahlensystem

Symmetrie

Irrfahrtsproblem

Nichtunterscheidbarkeit

Einfach zusammenhängender Raum

Graph

Dreiecksungleichung

Logarithmus

Expandierender Graph

Überlagerung <Mathematik>

Kommutator <Quantentheorie>

Zeitzone

Knotenmenge

Objekt <Kategorie>

Größenordnung

41:54

Lineare Abbildung

Distributionstheorie

Harmonische Analyse

Extrempunkt

Zahlenbereich

Gleichungssystem

Extrempunkt

Raum-Zeit

Computeranimation

Gebundener Zustand

Überlagerung <Mathematik>

Variable

Arithmetische Folge

Spieltheorie

Mittelwert

Massestrom

Schätzwert

Erweiterung

Approximation

Graph

Logarithmus

Reihe

Lineare Gleichung

Überlagerung <Mathematik>

Physikalisches System

Kette <Mathematik>

Zeitzone

Empirische Verteilungsfunktion

Approximation

Lineares Gleichungssystem

Summengleichung

Teilmenge

Energiedichte

Diskrete-Elemente-Methode

Quadratzahl

Menge

Rechter Winkel

Beweistheorie

47:34

Kovarianzfunktion

Punkt

Prozess <Physik>

t-Test

Symmetrisierung

Ungerichteter Graph

Extrempunkt

Fastring

Computeranimation

Gruppe <Mathematik>

Randomisierung

Entropie

Wurzel <Mathematik>

Analytische Fortsetzung

Durchmesser

Radius

Analogieschluss

Dimension 2

Umwandlungsenthalpie

Lineares Funktional

Multifunktion

Integral

Menge

Rechter Winkel

Beweistheorie

Tourenplanung

Körper <Physik>

Standardabweichung

Subtraktion

Hausdorff-Dimension

Gruppenoperation

Zahlenbereich

Term

Physikalische Theorie

Obere Schranke

Überlagerung <Mathematik>

Ausdruck <Logik>

Graph

Variable

Abstand

Varianz

Radius

Erweiterung

Durchmesser

Graph

Green-Funktion

Logarithmus

Überlagerung <Mathematik>

Integral

Freie Gruppe

Quadratzahl

52:40

Theorem

Prozess <Physik>

Punkt

Extrempunkt

Besprechung/Interview

Natürliche Zahl

Zahlenbereich

Analytische Menge

Äquivalenzklasse

Extrempunkt

Computeranimation

Überlagerung <Mathematik>

Graph

Ungleichung

Irrfahrtsproblem

Freie Gruppe

Analogieschluss

Mathematik

Graph

Klassische Physik

Indexberechnung

Variable

Konstante

Quadratzahl

Körper <Physik>

Ext-Funktor

55:08

Theorem

Prozess <Physik>

Ortsoperator

Extrempunkt

Zahlenbereich

Element <Mathematik>

Extrempunkt

Physikalische Theorie

Computeranimation

Topologie

Überlagerung <Mathematik>

Konstante

Uniforme Struktur

Freie Gruppe

Einfach zusammenhängender Raum

Schätzwert

Erweiterung

Reihe

Isomorphismus

Überlagerung <Mathematik>

Zeitzone

Konstante

Diskrete-Elemente-Methode

Quadratzahl

Beweistheorie

Zustand

Körper <Physik>

Markov-Kette

56:44

Trennungsaxiom

Resultante

Schätzwert

Punkt

Euklidischer Raum

Kurve

Graph

Kategorie <Mathematik>

Hausdorff-Dimension

Hochdruck

Güte der Anpassung

Wärmeübergang

Gesetz <Physik>

Raum-Zeit

Physikalische Theorie

Topologie

Konstante

Randwert

Arithmetische Folge

Irrfahrtsproblem

Uniforme Struktur

Randomisierung

Ordnung <Mathematik>

Analogieschluss

Feuchteleitung

### Metadaten

#### Formale Metadaten

Titel | Breaking barriers in probability |

Serientitel | Les Probabilités de Demain |

Teil | 02 |

Anzahl der Teile | 17 |

Autor | Peres, Yuval |

Mitwirkende |
Abraham, Céline (Organizer) Chen, Linxiao (Organizer) Maillard, Pascal (Organizer) Mallein, Bastien (Organizer) Fondation Sciences Mathématiques de Paris (Organizer) |

Lizenz |
CC-Namensnennung 3.0 Unported: Sie dürfen das Werk bzw. den Inhalt zu jedem legalen Zweck nutzen, verändern und in unveränderter oder veränderter Form vervielfältigen, verbreiten und öffentlich zugänglich machen, sofern Sie den Namen des Autors/Rechteinhabers in der von ihm festgelegten Weise nennen. |

DOI | 10.5446/20277 |

Herausgeber | Institut des Hautes Études Scientifiques (IHÉS) |

Erscheinungsjahr | 2016 |

Sprache | Englisch |

#### Inhaltliche Metadaten

Fachgebiet | Mathematik |