Random Structures Fall 2014

Friday, 2:00PM-3:00PM, RLM 8.136

Organizers: Francois Baccelli and Ngoc Tran

This is a weekly working group at the Department of Mathematics at UT Austin. It is opened to anybody who is interested in topics around the theme of random structures, such as networks, spatial processes, random graphs, random combinatorial objects, with applications in operations research, machine learning and computer science.

To be added to the mailing list, please email: ntran at math.utexas.edu

Schedule

DATE SPEAKER TITLE (click for abstract below)
September 12 Terry Lyons Expected Signatures
October 29 Ila Fiete Neural codes for memory
November 5 Anne Bouillard Network Calculus, part 1
November 7 Anne Bouillard Network Calculus, part 2
November 12 Darryl Veitch Topology Tomography with Spatial Dependencies
November 19 Ngoc Tran Random Permutations and Random Subdivisions
December 3 Evdokia Nikolova The Burden of Risk Aversion in Mean-Risk Selfish Routing



Title and Abstracts

Expected Signatures

Terry Lyons

Department of Mathematics, University of Oxford

How does one describe the law of a stochastic process. If it is Markov then the Stroock-Varadhan martingale characterisation offers a viable and even standard approach. For the general case, the expected signature is the correct alternative to the Laplace transform; the signature equivalent of a characteristic function also exists. How does one compute it, and how does one use it?

Neural codes for memory

Ila Fiete
Center for Learning and Memory, UT Austin

I'll talk about how the brain uses components that individually have only short time-scale memory (10's of milliseconds) and are stochastic, to construct memories over longer times (10's of seconds). I'll discuss models of neural dynamics and coding, and present a striking number-theoretic neural code for representing one's location in a room. The aim is to convey some of the mathematical challenges in understanding dynamics and representation in the brain.

Network Calculus, part 1

Anne Bouillard
Ecole Normale Superieure

Network calculus (NC) is a theory based on the (min,plus) algebra and whose aim is to compute worst-case performance bounds in communication networks. This theory abstracts flows circulating in a network and the service offered by the networks elements by functions (named curves) on which computations are performed. The basic concepts will be presented in this talk. First, the concepts of arrival of service curves are defined. I will show how the (min,plus) operations on these functions appear in the model of a single server, then, how to extend the framework in order to analyze (feed-forward) networks. Finally, I will present a first model for Stochastic Network Calculus


Network Calculus, part 2

Anne Bouillard
Ecole Normale Superieure

Network calculus (NC) is a theory based on the (min,plus) algebra and whose aim is to compute worst-case performance bounds in communication networks. This theory abstracts flows circulating in a network and the service offered by the networks elements by functions (named curves) on which computations are performed. The three following problems will be addressed. 1) how to find the best path from one source to one destination for one flow crossing the system; 2) how to compute exact worst-case performance bounds in a feed-forward network, and 3) the problem of supervision of a flow that uses some basic concepts of NC but with a different aim.


Topology Tomography with Spatial Dependencies

Darryl Veitch
University of Melbourne, Australia

There has been considerable tomography inference work on measurement networks with a tree topology. Here observations are made, at the leaves of the tree, of `probes' sent down from the root which are copied at each branch point. Inference can be performed based on loss or delay (transit time) information carried by probes, and used in order to recover loss parameters, delay parameters, or the detailed topology, of the tree. In all of these a strong assumption of spatial independence between links in the tree has been made in prior work. I will describe recent work on topology inference, based on loss measurement, which breaks that assumption. In particular I will introduce a new model class for loss with non trivial spatial dependence, the `Jump Independent Models', which are well motivated, and prove that within this class the topology is identifiable.


Random Permutations and Random Subdivisions

Ngoc Tran
Department of Mathematics, UT Austin

I will talk about various problems related to random permutations and random subdivisions. In particular, I discuss size-biased permutations, which have applications to statistical sampling. Then I will talk about random subdivisions obtained from projections of polytopes. These are related to random polytopes and zeros of random tropical polynomials. Based on joint work with Jim Pitman and Francois Baccelli.


The Burden of Risk Aversion in Mean-Risk Selfish Routing

Evdokia Nikolova
Department of Electrical and Computer Engineering, UT Austin

Considering congestion games with uncertain delays, we compute the inefficiency introduced in network routing by risk-averse agents. At equilibrium, agents may select paths that do not minimize the expected latency so as to obtain lower variability. A social planner, who is likely to be more risk neutral than agents because it operates at a longer time-scale, quantifies social cost with the total expected delay along routes. From that perspective, agents may make suboptimal decisions that degrade long-term quality. We define the price of risk aversion (PRA) as the worst-case ratio of the social cost at a risk-averse Wardrop equilibrium to that where agents are risk-neutral. For networks with general delay functions and a single source-sink pair, we show that the PRA depends linearly on the agents' risk tolerance and on the degree of variability present in the network. In contrast to the price of anarchy, in general the PRA increases when the network gets larger but it does not depend on the shape of the delay functions. To get this result we rely on a combinatorial proof that employs alternating paths that are reminiscent of those used in max-flow algorithms. For series-parallel (SP) graphs, the PRA becomes independent of the network topology and its size. As a result of independent interest, we prove that for SP networks with deterministic delays, Wardrop equilibria maximize the shortest-path objective among all feasible flows.
Joint work with Nicolas Stier-Moses
Paper is available here: http://arxiv.org/abs/1411.0059