Probability Seminar, Statistical Laboratory

# Probability Seminar, Statistical Laboratory

### Lent 2009

 Date Speaker Title Notes January 19 Harald Oberhauser (Cambridge). "Towards a (rough) pathwise theory of fully non-linear stochastic partial differential equations" (abstract) January 26. Nathanael Berestycki (Cambridge). "On the mixing time of random conjugacy walks" (abstract). February 3. Daniel Levin (Oxford). "A new combinatorial method for calculating the moments of Lévy area" (abstract) February 5. Van Vu (Rutgers) "Random matrices: Universality of ESDs and the circular law" Combinatorics seminar. February 10. Benjamin Schlein (Cambridge). "Local semicircle law and level repulsion for Wigner random matrices" (abstract) February 13. Noga Alon (Tel-Aviv). "The structure of large graphs". 5pm in MR2. February 24 Michael Mitzenmacher (Harvard). "A Survey of Results for Deletion Channels and Related Synchronization Channels " (abstract) 2pm MR5, joint with Networks seminar February 24. Sergei Levendorskii (Univeristy of Leicester) "Refined and enhanced FFT techniques, with applications to pricing barrier options and their sensitivities" (abstract) 3.30pm MR12 Feburary 27. Dmitri Korshunov (Novosibirsk) "Convolution tail equivalent distributions: basic properties" (abstract) (Joint with Networks seminar). March 5. Franck Barthe (Toulouse) Geometric Structure for Brascamp Leib Inequalities At the Discrete Analysis seminar, 4.30pm MR12. March 6. Asaf Naor (NYU) Towards a calculus for nonlinear spectral gaps At the Discrete Analysis seminar, 4.30pm MR12. March 11. Alexander Holroyd (Microsoft and UBC). Poisson matching (abstract) Unusual day and location: Gatehouse March 17. Sandy Davie (Edinburgh). Existence of unique solutions for SDEs for individual driving paths(abstract)

### Abstracts

January 19. Harald Oberhauser (Cambridge). "Towards a (rough) pathwise theory of fully non-linear stochastic partial differential equations"

We return to seminal work of P.L.Lions and P.Souganidis on nonlinear stochastic partial differential equations in viscosity sense and present some evidence that rough path analysis a la T.Lyons may allow to continue, and perhaps complete, the program they started in a series of papers from 1998-2003.

January 26. Nathanael Berestycki (Cambridge). "On the mixing time of random conjugacy walks".

Let G be a finite graph and consider a random walk on this graph. How long does it take for this walk to be well mixed, i.e., to be close to its equilibrium distribution? A striking phenomenon, discovered in the early 80's by Aldous and Diaconis independently, is that convergence to equilibrium often occurs abruptly: this is known as the cutoff phenomenon. In this talk we shall consider the classical example of random transpositions over the symmetric group. In this case, Diaconis and Shahshahani used representation theory to prove that such a cutoff occurs at time (1/2) n log n. We present a new, probabilistic proof of this result, which extends readily to other walks where the step distribution is uniform over a given conjugacy class. This proves a conjecture of Roichman (1996) that the mixing time of this process is (1/C) n log n, where C is the size of the conjugacy class. This is joint work with Oded Schramm and Ofer Zeitouni.

February 3. Daniel Levin (Oxford). "A new combinatorial method for calculating the moments of Lévy area."

We present a new way to compute the moments of the Lévy area of a two-dimensional Brownian motion. This is a classical problem of great importance, originally solved by Lévy. Our approach uses iterated integrals and combinatorial arguments involving the shuffle product (joint paper with Mark Wildon, Swansea).

February 5. Van Vu (Rutgers) at the Combinatorics seminar. "Random matrices: Universality of ESDs and the circular law"

February 10. Benjamin Schlein (Cambridge). "Local semicircle law and level repulsion for Wigner random matrices."

Consider ensembles of N by N hermitian random matrices with independent and identically distributed entries (up to the symmetry constraints), scaled so that the typical distance between successive eigenvalues is of the order 1/N. In this talk, I am going to discuss some properties of the spectrum of these matrices as N tends to infinity. In particular, I am going to present a proof of the validity of the semicircle law for the eigenvalue density on energy scales of the order K/N, in the limit of large but fixed K (independent of N). This is the smallest scale on which the semicircle law can be expected to hold. Moreover, I am going to discuss some upper bounds on the probability of finding eigenvalues in a given interval, which show the phenomenon of level repulsion. This is a joint work with L. Erdos and H.-T. Yau.

February 13. Kuwait lecture by Noga Alon (Tel-Aviv). "The structure of large graphs". 5pm in MR2.

February 24 (MR5, joint with Networks seminar). Michael Mitzenmacher (Harvard). "A Survey of Results for Deletion Channels and Related Synchronization Channels "

At this point, it seems that most everything is known about the basic channels studied in information theory. For the i.i.d. (independent and identically distributed) binary erasure channel and the i.i.d. binary symmetric error channel, the capacity has long been known, and there are very efficient encoding and decoding schemes that are near capacity. The situation is very different for the i.i.d. binary deletion channel. With this channel, the sender sends n bits, and each bit is deleted with some fixed probability p. So, for example, the sender might send 10110010, and the receiver obtains 1100. The i.i.d. binary deletion channel is perhaps the most basic channel that incorporates the challenge of synchronization. Surprisingly, even the capacity of the deletion channel remains unknown! In this talk, I will survey what is known about the deletion channel, focusing on our recent work on bounds on the capacity. The main result is that the for any probability p, the deletion channel has capacity at least (1-p)/9. Hence, the capacity of the deletion channel is always within a constant factor of the erasure channel (which has capacity (1-p)). We also discuss the many remaining open problems in the area of synchronization channels. No previous background is necessary.

February 24. (3.30pm) Sergei Levendorskii (Univeristy of Leicester) "Refined and enhanced FFT techniques, with applications to pricing barrier options and their sensitivities"

Many mathematical methods of option pricing rely on one's ability to calculate the action of certain integro-differential operators and convolution operators quickly and efficiently. In turn, the latter computations are based on FFT techniques. However, in many important cases, a straightforward application of FFT and iFFT leads to errors of several kind, which cannot be made simultaneously small (uncertainty principle) unless grids with too many points are used. We explain an approach to using FFT techniques that gives one more flexibility in controlling the aforementioned errors, and, at the same time, yields fast and efficient algorithms. As applications, using Carr's randomization, we compute the prices and sensitivities of barrier options and first-touch digital options on stocks whose log-price follows a Levy process. The numerical results obtained via our approach are demonstrated to be in good agreement with the results obtained using other (sometimes fundamentally different) approaches that exist in the literature. However, our method is computationally much faster (often, dozens of times faster). Moreover, our technique has the advantage that its application does not entail a detailed analysis of the underlying Levy process: one only needs an explicit analytic formula for the characteristic exponent of the process. Thus our algorithm is very easy to implement in practice. Finally, our method yields accurate results for a wide range of values of the spot price, including those that are very close to the barrier, regardless of whether the maturity period of the option is long or short. A natural extension of the method gives similar results for double-barrier options.

Feburary 27. (Joint with Networks seminar). Dmitri Korshunov (Novosibirsk) "Convolution tail equivalent distributions: basic properties."

The talk discusses the tail behaviour of 2-fold convolutions $\overline{F*F}$ of right-unbounded distributions and to the tail behaviour of the distribution of the random sum $S_\tau$. We start with the description of all possible values of the limit of the ratio $\overline{F*F}(x)/\overline F(x)$ as $x\to\infty$. This problem is closely related to the problem of the lower limit of this ratio and goes back to W. Rudin. The second part of the talk is devoted to conditions under which $P(S_\tau>x)\sim E\tau \overline F(x)$ as $x\to\infty$. We also consider applications of results obtained to random walks, compound Poisson distributions, infinitely divisible laws, and branching processes.

March 11. Alexander Holroyd (Microsoft Research and UBC).

Red points and blue points occur as independent Poisson processes in R^d, and we consider schemes to perfectly match red points to blue points in a translation-invariant way. For any matching scheme in dimensions 1 and 2, the distance X from a typical red point to its blue partner has infinite d/2-th moment, while in dimensions >=3 there exist schemes where X has exponential tails. For the variant problem of matching points of a single color to each other, there exist schemes where X has exponential tails, but if we insist that the matching is a deterministic factor of the points then in dimension 1, X must have infinite mean. The Gale-Shapley stable marriage is a natural greedy matching scheme. It is close to optimal (in terms of X) for two-color matching in dimension 1, but far from optimal for dimensions >=3 and for one-color matching. Joint work with Robin Pemantle, Yuval Peres and Oded Schramm.

March 17. Existence of unique solutions for SDEs for individual driving paths.

Existence and uniqueness theorems for (vector) stochastic differential equations dx=a(t,x)dt+b(t,x)dW are usually formulated at the level of stochastic processes. If one asks for such a result for an individual driving Brownian path W then there is a difficulty of interpretation. One solution to this is to use rough path theory, and in this context a uniqueness theorem can be proved (for a.e. W) for dx=b(x)dW if b has Holder continuous derivative. Another variant with a natural interpretation is dx=a(t,x)dt+dW where, if a is bounded Borel, uniqueness can be shown for a.e. W. The talk will explore the extent to which these two approaches can be combined.