We would like to invite you to the following talks of the Eindhoven Stochastics Seminar:

Lutz Warnke (Georgia Institute of Technology) – A dynamic view on the probabilistic method: random graph processes

Monday 27 August, 11.00-12.00, Room MF 13 (5th floor, MetaForum Building, TU/e)

ABSTRACT:
Random graphs are the basic mathematical models for large-scale disordered networks in many different fields (e.g., physics, biology, sociology). Since many real world networks evolve over time, it is natural to study various random graph processes which arise by adding edges (or vertices) step-by-step in some random way. The analysis of such random processes typically brings together tools and techniques from seemingly different areas (combinatorial enumeration, differential equations, discrete martingales, branching processes, etc), with connections to the analysis of randomized algorithms. Furthermore, such processes provide a systematic way to construct graphs with “surprising” properties, leading to some of the best known bounds in extremal combinatorics (Ramsey and Turan Theory). In this talk I shall survey several random graph processes of interest (in the context of the probabilistic method), and give a glimpse of their analysis.

David Goldberg (Cornell University) – Beating the curse of dimensionality in options pricing and optimal stopping

Monday 27 August, 13.00-14.00, Room MF 13 (5th floor, MetaForum Building, TU/e)

ABSTRACT:
The fundamental problems of pricing high-dimensional path-dependent options and optimal stopping are central to applied probability, financial engineering, operations research, and stochastic control. Modern approaches, often relying on ADP, simulation, and/or duality, typically have limited rigorous guarantees, which may scale poorly and/or require previous knowledge of good basis functions. A key difficulty with many approaches is that to yield stronger guarantees, they would necessitate the computation of deeply nested conditional expectations, with the depth scaling with the time horizon T.
We overcome this fundamental obstacle by providing an algorithm which can trade-off between the guaranteed quality of approximation and the level of nesting required in a principled manner. We develop a novel pure-dual approach, inspired by a connection to network flows. This leads to a representation for the optimal value as an infinite sum for which : 1. each term is the expectation of an elegant recursively defined infimum; 2. the first k terms only require k levels of nesting; and 3. truncating at the first k terms yields a (normalized) error of 1/k. This enables us to devise simple randomized and data-driven algorithms and stopping strategies whose runtimes are effectively independent of the dimension, beyond the need to simulate sample paths of the underlying process. Our method allows one to elegantly trade-off between accuracy and runtime through a parameter epsilon controlling the associated performance guarantee (analogous to the notion of PTAS in the theory of approximation algorithms), with computational and sample complexity both polynomial in T (and effectively independent of the dimension) for any fixed epsilon, in contrast to past methods typically requiring a complexity scaling exponentially.
Joint work with Ph.D. student Yilun Chen.

Nicolas Broutin (Sorbonne Université) – Fragmentations and tree-like fractals: a functional fixed-point approach

Monday 27 August, 15.00-16.00, Room MF 13 (5th floor, MetaForum Building, TU/e)

ABSTRACT:
I will review some models and recent results where “fixed-points” approach or the “contraction method” have played a central role. Recursive partitioning schemes are central to many applications, starting with efficient data structures based on the divide-and-conquer paradygm. For more than 25 years now, arguments based on Banach fixed theorem have long been used to prove “softly” the convergence in distribution of associated real-valued random variables in the context of analysis of algorithms. I will review a number of questions that call for a more general approach for random functions. The applications include the quantification of the cost of partial match search queries in data data such as quad trees and k-trees, the construction of natural fractal tree-like objects such as Aldous’ continuum random trees, or certain trees that are dual to recursive geometric partitions, and extend to the convergence of certain random fields.
This is based on a collection of joint works with Henning Sulzbach and Ralph Neininger.

Upcoming events of the Eindhoven Stochastics Colloquium: http://www.win.tue.nl/StoSem/