MAXWELL INSTITUTE for MATHEMATICAL SCIENCES
Probability Seminars
Abstracts
We derive an upper bound for the
largest Lyapunov exponent of a Markovian random matrix product of
nonnegative matrices.
The bound is expressed as the maximum of a nonlinear
concave function over a finite-dimensional
convex set of probability distributions.
The technique used is Markovian type counting.
This is joint work with Reza Gharavi.
In this talk, we present a new model of geometric random tree on the d-
dimensional Euclidean space. This tree has a simple radial structure
with
the origin as root. This tree is motivated by applications in wireless
mutlihop communications.
When the set of points is a realisation of a homogeneous Poisson point
process, some interesting functionals of this random tree are
explicitly
known, for example the distribution of the length of the edges or the
mean
degree of a node.
We will also pay attention to the asymptotic behaviour
of the tree, such as the path from a vertex to the origin,
the shape of set of points of a given generation or also its
topological
ends.
This work is a joint work with Francois Baccelli.
I will talk about how probabilistic methods of analyzing
randomly-labeled trees can provide an important insight
on the 5x+1 analogue of the famous Collatz problem (3x+1), please see
†.
Though no rigorous results about number theory will be proved in my
talk, a number of properties of the trees with random labels will be
rigorously established.
The talk will describe joint work with Alexandros Beskos and Omiros
Papaspiliopoulos on the simulation of diffusion processes without
discretisation approximation. A number of examples to Monte Carlo
calculations and likelihood based inference for diffusions will be
briefly described.
We present exact asymptotics for the distribution of the first time a
Levy process becomes negative, assuming heavy-tailed positive jumps and
starting from positive level.
We apply these results to find asymptotics for the distribution of the
busy period
in an M/GI/1 queue. This is joint work with Seva Sheer.
We estimate the rate of convergence of the Wong-Zakai type of
approximations for
SDEs and SPDEs. Two cases are studied: SDEs in finite dimensional
settings and
evolution stochastic systems. The latter result is applied to the
second order
SPDEs of parabolic type and the filtering problem. Roughly, the result
is the
following. Let W_n be a sequence of continuous stochastic processes of
finite
variation on an interval [0,T]. Assume that for some α > 0 the
processes
W_n converge almost surely in the supremum norm in [0,T] to W with the
rate n^{-κ} for each κ < α. Then the solutions u_n of the
differential equations with W_n converge almost surely in the supremum
norm
in [0,T] to the solution u of the ``Stratonovich'' SDE with W with the
same rate of convergence, n^{-κ} for each κ<α, in the case
of SDEs and with the rate of convergence n^{-κ/2} for each
κ<α, in the case of evolution systems and SPDEs. Finally, we verify
that the two most common approximations of the Wiener process,
smoothing and
polygonal approximation, satisfy the assumptions made.
We study the so-called Skorokhod reflection problem (SRP) posed for
real-valued functions defined on a partially ordered set (poset),
when there are two boundaries, considered also to be functions
of the poset.
The problem is to constrain the function between the
boundaries by adding and subtracting nonnegative nondecreasing (NN)
functions
in the most efficient way.
We show existence and uniqueness of
its solution by using only order theoretic arguments.
The solution is also shown to obey a fixed point equation.
When the underlying poset is
a σ-algebra of subsets of a set, our results
yield a generalization of the classical
Jordan-Hahn decomposition of a signed measure.
We also study the problem on a poset that
has the structure of a tree, where we identify additional
structural properties of the solution,
and on discrete posets, where
we show that the fixed point equation uniquely characterizes the
solution.
Further interesting posets we consider are
the poset of real n-vectors ordered by majorization, and the
poset of n × n positive semidefinite real
matrices ordered
by pointwise ordering of the associated quadratic forms.
We say a function on a poset is of bounded variation if it can
be written as the difference of two NN functions.
The solution to the SRP when the upper and lower
boundaries are the identically zero function corresponds to the most
efficient or minimal such representation of a function of bounded
variation.
Minimal representations for several important functions of bounded
variation on several of the posets mentioned above are determined
in this paper.
This is joint work with Venkat Anantharam.
Link
to a preprint
We present high order numerical schemes for the strong solution of
linear
stochastic differential equations. These schemes are based on the
Neumann and Magnus
expansions. The Magnus integrator demonstrates an order of magnitude
improvement in
accuracy when compared to classical stochastic numerical integration
schemes or the Neumann
integrator. Moreover, in scenarios when the cost of computing the
matrix exponential does
not dominate, this improved accuracy is provided at the same
computational cost. We also apply
both the Neumann and Magnus integrators to a stochastic Riccati
differential system that
can be linearized. Both integrators demonstrate superior efficiency
when compared to a
non-linear stochastic Runge-Kutta method. (Joint work with Gabriel Lord
and Simon Malham)
Tail asymptotics for the supremum of a random walk attracted a lot of
interest in queueing theory or risk theory. In this talk, we show that
these asymptotics can be extended to the case of the supremum of a
subadditive process. This new result allows us to obtain large
deviations results for queueing networks in their stationary regime. In
the particular case of (max,plus)-linear recursions, the rate of
exponential decay of the stationary solution is explicitly computed.
We consider a time-homogeneous Markov chain $X_n$ valued on real line.
Suppose the chain is transient, that is, the chain generates a
$\sigma$-finite renewal measure. We prove the key renewal theorem under
condition that this chain has asymptotically homogeneous at infinity
jumps
and asymptotically positive drift.
We give an almost complete classification of ergodicity and
transience conditions for a general multi-queue system with the
following features: arrivals form Poisson streams and there are
various routing schemes for allocating arrivals to queues; the
servers can be configured in a variety of ways; completed jobs can
feed back into the system; the exponential service times and
feedback probabilities depend upon the configuration of the servers
switching between service regimes is instantaneous. Several
different levels of control of the service regimes are considered.
Our results for the $N$-queue system require randomisation of
service configurations. This will be illustrated by showing the result
in detail for two queues. We also provide some examples of queueing
systems which are covered by our model.
Starting from the potential theoretic definition of the local times
of a Markov process -- when these exist -- we obtain a Tanaka formula
for the local times of symmetric Lévy processes. The most
interesting
case is that of the symmetric α-stable Lévy process (for
α ∈ (1,2])
which is studied in detail. In particular, we determine which powers
of such a process are semimartingales. These results complete, in a
sense, the works by K. Yamada, and Fitzsimmons and
Getoor.
I will use the theory of boundary value problems for elliptic
pseudodifferential
operators to discuss the well known difficulties which arise in the
study of
Markov processes with state spaces having a boundary and which are
largely
unresolved,
especially in the case of general (Wentzell) boundary conditions. The
talk
will be aimed
at probabilists with possibly little or even no prior knowledge of the
theory
of pseudodifferential operators.
In the first half of the talk I shall survey the basic facts about
coherent and convex risk measures (in the contexts of the talk the risk
measures are a class of some non-linear functionals on the space of
uniformly bounded random variables).
Second part of the talk will be devoted to the recent result of
A.Cherny and P.Grigoriev, who proved that on an atomless probability
space a risk measure is law invariant iff it is dilatation monotone
(i.e. monotone with respect to the conditional expectations over all
sigma-subalgebras). In some sense this result could be viewed as an
inverse theorem to the characterization of the law-invariant risk
measures due to Kusuoka and Follmer and Schied.
No preliminary knowledge (but basic probability and analysis) is
assumed.
Exclusion processes form one of the major classes of interacting
particle
systems. There, particles on a lattice execute independent random walks
in continuous time, except when the target site is already occupied, in
which case the particle remains at the original site.
Many results exist for the lattice Z. In particular, the equilibria of
such exclusion processes are in many cases well understood. Little is
presently known, however, for Z^d, d>1 . We will review the behavior
of
the exclusion process on Z and with the remaining time present the
foundation of a theory for d>1 .
In this talk, using mean field techniques, we present a performance
analysis of random multi-access algorithms, such as the exponential
back-off algorithm, in the case of a finite number of saturated or
non-saturated sources. We prove a decoupling property when the number
of
sources grows large, and present some applications of this property.
Stochastic differential inclusions(SDIs) represent an important
generalization of the notion of stochastic differential
equations(SDEs). In this talk we will discuss SDIs on domain of
$\bR^d$. Some new results on solvability and approximations of SDIs
will be presented. The existence of solutions is proved by monotonicity
method in terms of minimizing certain convex functionals and in this
way solutions are approximated by implicit schemes. In this
presentation, a result on the rate of convergence will be discussed.
We adopt the classical ALOHA scheme to the case when the users
in a multiple-access system have local interactions given by some
neighbourhood relations. We prove that the fluid limits of the system's
workload satisfy a certain differential equation and, via an analysis
of
this differential equation, obtain conditions sufficient for the system
to
be stable. We also discuss the behaviour of the fluid limits. This is a
joint work with Charles Bordenave and Serguei Foss.
I present a short new proof of the following result.
{\bf Theorem.} Let $F$ be a distribution on the positive half-line and
$\overline{F}(x) = F((x,\infty ))$. Assume that $F$ is
{\it heavy-tailed}, that is: for
any $c>0$,
$$
\int_0^{\infty} e^{cx} F(dx) = \infty.
$$
Let $\xi_1,\xi_2,\ldots$ be i.i.d. sequence of random variables
with a common distribution $F$. Let
$\tau$ be an independent {\it light-tailed} counting random variable
and
$F^{*\tau}$ a distribution of $S_{\tau} = \sum_1^{\tau} \xi_i$.
Then
$$
\liminf_{x\to\infty}
\frac{\overline{F^{*\tau}}(x)}{\overline{F}(x)} = {\bf E} \tau.
$$
\vspace{0.5cm}
I also provide various comments on this limit and on relative problems.
Moez Draief:
Threshold for Virus Spread on Networks
We consider epidemics on finite undirected graphs and study the
relationship between the epidemics outcome, the infection parameters,
and properties of the graph. We establish thresholds on certain classes
of graphs with homogeneous node degrees. In addition, we obtain
thresholds for epidemics on power-law graphs.
Alexander Veretennikov:
On Doeblin-Doob and other mixing conditions for Markov processes
In his seminal Stochastic Processes (1953), J.L.Doob, in particular,
gave a detailed classification of various conditions for a homogeneous
Markov process to have an (exponential) convergence to equilibrium
distribution. In the literature, the most general condition used in
this theory is called Doeblin-Doob's condition. Some of those
conditions provide a uniform (exponential) convergence on some classes
of processes. Other conditions allow only an (always exponential)
convergence rate for a single process. Doob's most general case that
gives a uniform convergence on some class is most widely used, unlike
Doeblin-Doob's one. Recently it was understood that there is a natural
more general condition that also provides a uniform convergence on some
appropriate class of processes; moreover, this condition also gives a
more natural bound for the exponent power in this rate. In the talk,
this condition will be discussed with applications to mixing for
approximation schemes of stochastic differential equations under a good
recurrence.
Peter Mörters:
Intersections of Random Walks in Supercritical Dimensions
In high dimensions two independent simple random walks have only a
finite number of intersections. I discuss recent results
on the upper tail behaviour of the number of intersections, obtained
in collaboration with Xia Chen (Knoxville)
Vassili Kolokoltsov:
Fractional Dynamics and Continuous Time Random Walks
Functional limit theorem for continuous-time random walks (CTRW) are
found in the general case of dependent waiting times and jump sizes
that
are also position dependent. The limiting anomalous diffusion is
described in terms of fractional dynamics that is often considered by
physicists as a natural model for Hamiltonian chaos. Probabilistic
interpretation of generalized fractional evolution is given in terms
of the random time change (subordination) by means of hitting time
processes.
Thomas Liniger
Multivariate Hawkes Processes and Applications
We consider multivariate, marked Hawkes processes and give the
conditions for sub-critical behavior and a direct proof based on
[Brémaud and Massoulié, 1996]. To achieve this we use
Poisson
embeddings, which can be used to derive further results concerning
stability under initial conditions. Hawkes processes have been widely
applied in earthquake modelling and have found more recent applications
in finance, such as pricing of credit derivatives [Errais, Giesecke and
Goldberg, 2007].
Vladimir Rykov:
Queueing Networks with Transparent Calls
In some applications of queueing networks the situation arises when all
calls of the same
type can be served simultaneously as if they were a single call. One of
the main
applications of this type of model is in queueing networks with
multipoint connection
protocols, which are used in TV broadcasting, video-on-demand, some
types of
teleconferencing, etc..
Analagous service principles are probably realised in neuron networks,
where an impulse
caused by some irritant is delivered to all executives for its organs
simultaneously.
traditional approaches to the analysis of complex telecommunications
networks are based on
modelling of stochastic networks (SN) and reversible Markov processes,
which permit us to obtain the
steady state probabilities in product form.
The reversibility approach is not applicable directly for stochastic
networks with general
service time distributions, because of the absence of a theory of
reversible processes on
general state spaces. In this case the product form for the staedy
state distribution is
usually obtained by the phase method approach. This approach consists
of approximation of
any distribution by the mixture of convolutions of exponential
distributions, and the fact
that these mixtures are dense in the class of distributions on the
positive reals. But
the weak convergence arguments necessary for this are only proved for
the case of a
finite state space.
An alternative approach to proving the product form for stochastic
networks with general
service time distributions was proposed in a number of papers by Rykov
et al. This
approach is based on direct investigation of Markov processes with
additional variables
which describe the stochastic network under consideration.
Fuller Abstract
Florin Avram:
The one dimensional exact and asymptotic exit/ruin theory have been
developed by Cramer and Lundberg as an application of Laplace's
method.
In several dimensions this method breaks down; exact solutions are very
rarely
available, and even asymptotic expansions (beyond the large deviations
logarithmic approximation) are not fully studied.
On the other hand, exact and asymptotic results are available for a
certain
class of "degenerate" multidimensional Levy processes which appear
in proportional reinsurance problems,
and which may be reduced to
one-dimensional first-passage problems with linear barriers.
(Joint work with Zbigniew Palmowski and Martijn Pistorius.)
Stephen Connor:
Coupling: Co-adapted vs. Maximal
Coupling is an interesting probabilistic technique, with many
applications. The existence of maximal couplings for general stochastic
processes has been known for some time, but such couplings are often
not co-adapted (and hence usually rather unintuitive). In this talk I
will introduce the concepts of maximal and co-adapted couplings, before
looking at how good co-adapted couplings can possibly be in the case of
two simple stochastic processes: Euclidean Brownian motion and a simple
symmetric random walk on the hypercube. This topic is interesting in
its own right, but also has consequences for the possible efficiency of
perfect simulation algorithms such as Coupling from the Past.
Phylogenetics is the reconstruction and analysis of 'evolutionary'
trees and graphs in biology (and related areas of classification such
as linguistics).
Several areas of mathematics and statistics are playing an increasingly
important part in the underlying theory. I will describe some of the
ways in which concepts from combinatorics and probability have helped
provide insights into certain fundamental questions relevant to
evolutionary biology, and outline some open problems.
Nikolai Leonenko:
Multifractality of Products of Geometric Ornstein-Uhlenbeck Type
Processes
This is joint work with V.V. Anh (Queensland University of Technology,
Brisbane) and N.-R. Shieh (National Taiwan University, Taipei).
We consider multifractal products of stochastic processes as de.ned in
Man-
nersalo et al. (2002), but we provide a new interpretation of the
conditions
on the mean, variance and covariance functions of the resulting
cumulative
processes in terms of the moment generating functions. We show that the
logarithms of the corresponding limiting processes have an in.nitely
divisible
distribution such as the gamma and variance gamma distributions
(resulting
in the log-gamma and log-variance gamma scenarios respectively), the
inverse
Gaussian and normal inverse Gaussian distributions (yielding the
log-inverse
Gaussian and log-normal inverse Gaussian scenarios respectively). We
describe
the behavior of their q-th order moments and R�nyi
functions, which are non-
linear, hence displaying their multifractality. A property on the
dependence
structure of the limiting processes, leading to their possible
long-range depen-
dence, is also obtained.
We consider very di�erent scenarios such as the
log-gamma and log-inverse
Gaussian scenarios as typical examples of our approach. We should also
note
some related results by Barndor�-Nielsen and
Schmiegel (2004) who introduced
some L�vy-based spatiotemporial models for
parametric modelling of turbu-
lence. Log-in.nitely divisible scenarios related to independently
scattered ran-
dom measures were introduced in Bacry and Muzy (2003) and others. We
should
note that Chris Heyde (1999) proposed to use a multifrcality into risky
asset
model with fractal activity time (see also Heyde and Leonenko (2005)).
Nikita Vvedenskaya:
Differential Equations Arising in Network Problems
The talk focuses on large queueing systems and networks
with dependent queues. In particular, we are interested in
the large-time performance and stationary distribution
of such networks. These problems are often rather complicated,
and one of the ways to study them is via an asymptopical approach.
In case where the network is guided by a Markov process and the number
of
its nodes $N$ is very large, the limiting situation, as $N\to infty$,
may be described by differential equations.
The solution to these equations gives an accurate assessment of the
network performance.
I present several examples where such aproach turnes to be successful.
First, we consider fast Jackson networks with dynamic routing. T he
simplest system with dynamic routing was given by Dobrushin,
Karpelevich and Vvedenskaya (and independently, Mitzenmacher):
it contains $N$ identical servers with IID exponential service times
and a Poisson flow of tasks.
Upon its arrival, each task randomly selects $m$ servers and is
directed to the one with a shorter
queue. The limiting situation is described by a rather simple infinite
system of ODEs, with a unique globally attracting fixed point. The
probability of long queues in the limiting system decreases
superexponentially.
Numerical simulations show that in the system with finite $N$
the queue length distribution is close to the limit one.
Later, Martin--Suhov and Suhov--Vvedenskaya considered open
Jackson-type
networks where each node contains $N$ identical servers and a task
selects several servers (from one or several nodes) and is directed to
the one with a shorter queue.
Finally, in a random multiple access system with $N$ users and
ALOHA-like protocol, each user tries to transmit its message with a
frequency determined by its back-off stage (the stage is changed after
each transmission.)
As $N\to \infty$, the system performance is
described by a solution to a system of ODE with one or several fixed
points. In case of several solutions the original system is treated as
'metastable'.
Goran Peskir: The British Option
We present a new put/call option where the buyer may exercise at any
time
prior to maturity whereupon his payout is the `best prediction' of the
Euro-
pean payout under the hypothesis that the true drift of the stock price
equals
a contract drift. Inherent in this is the protection feature which is
key to the
British option. Should the option holder believe the true drift of the
stock
price to be unfavourable (based upon the observed price movements), he
can
substitute the true drift with the contract drift and minimise his
losses. With
the contract drift properly selected the British put option becomes a
more
`buyer friendly' alternative to the American put: when stock price
move-
ments are favourable, the buyer may exercise rationally to very
comparable
gains; when price movements are unfavourable he is afforded the unique
pro-
tection described above. Moreover, the British put option is always
cheaper
than the American put. In the final part we present a brief review of
optimal
prediction problems which preceded the development of the British
option.
This is a joint work with F. Samee (Manchester).
Ron Doney:
The reflected process of a random walk or Levy process
Terry Lyons: Old work of Krylov and new uses
for Ito's map
It is an interesting exercise to compute the iterated integrals of
Brownian Motion and to calculate the expectations (of polynomial
functions of these integrals).
Recent work on constructing discrete measures on path space, which
give the same value as Wiener measure to certain of these expectations,
has led to promising new numerical algorithms for solving 2nd order
parabolic PDEs in moderate dimensions. Old work of Krylov associated
finitely additive signed measures to certain constant coefficient PDEs
of higher order. Recent work with Levin allows us to identify the
relevant expectations of iterated integrals in this case, leaving many
interesting open questions and possible numerical algorithms for
solving
high dimensional elliptic PDEs.
Alexei Piunovskiy: Fluid approximation of
birth-and-death processes
Abstract
Juan Carlos Pardo Millan:
Positive self-similar Markov processes
Positive self-similar Markov processes are positive real-valued strong
Markov processes satisfying the scaling property with some index
α > 0. These processes are to be found in many areas of probability
theory. To give just a few examples, let us mention: the continuous
state
branching process which is associated to a self-similar Lévy
tree and
whose genealogy may be described by the beta-coalescent, the size of a
tagged individual in the self-similar branching Markov chain, the so
called
tagged fragment of a self-similar fragmentation. These processes also
appear as the limit of local structure of random quadrangulations. In
this
talk, we survey some recent results on this topic.
This is joint work with M.E. Caballero, L. Chaumont and V. Rivero.
Christina Goldschmidt: Behaviour near the
extinction time in stable
fragmentation processes
The stable fragmentations are particularly nice examples of the
self-similar fragmentation processes introduced by Bertoin. They are
derived by looking at the masses of the subtrees formed by discarding
the the parts of a stable continuum random tree below height t, for t ≥
0. Such a fragmentation possesses a parameter α which lies between -1/2
and 0, called the index of self-similarity; heuristically, any block of
mass m splits at a rate proportional to mα. Since α is
negative, this means that smaller blocks split faster than larger ones.
Indeed, small blocks split faster and faster until they are reduced to
dust (blocks of size 0). The whole state is entirely reduced to dust in
some almost surely finite time zeta, called the extinction time. We
give a detailed limiting description of the distribution of a stable
fragmentation of index α as it approaches its extinction time.
This is joint work with Benedicte Haas of Universite Paris-Dauphine.
Ben Hambly:
Local limit theorems for simple random walks on sequences of graphs
In recent years there have been invariance principles proved for random
walk on supercritical percolation clusters
and for random walks on fractal graphs. We show that these theorems can
be refined to yield local limit theorems for
the convergence of the transition densities of the random walks to
those of the appropriate heat kernel on the limit
of the seqence of graphs.
Mokshay Madiman:
Information inequalities for joint distributions, with interpretations
and applications (tentative)
Upper and lower bounds are obtained for the joint
entropy of a collection of random variables in terms of an
arbitrary collection of subset joint entropies. These inequalities
generalize Shannon's chain rule for entropy as well as inequalities
of Han, Fujishige and Shearer. A duality between the upper and
lower bounds for joint entropy is developed, and connections
to structural properties of the entropy function are explored.
The new inequalities are applied to obtain new results in
combinatorics, such as bounds on the number of independent
sets in an arbitrary graph and the number of zero-error sourcechannel
codes, as well as new determinantal inequalities in matrix
theory. A new inequality for relative entropies is also developed,
along with interpretations in terms of hypothesis testing.
Ari Arapostathis: Uniform stability of
controlled Markov processes
and applications
We consider controlled Markov Processes modeled by Itô stochastic
differential equations in Rd, i.e., controlled
diffusions.
A control is called stable if the corresponding process is
positive recurrent.
It is well known that the invariant probability measures of a positive
recurrent diffusion can be characterized via an embedded Markov chain
which lives on the boundary of an annulus in Rd, a
method due to R. Hasminskii.
A controlled diffusion is called uniformly stable
if the first return times to the annulus are uniformly integrable, with
respect
to all stationary Markov controls, when the initial distribution of the
diffusion
is taken as the invariant distribution of the embedded chain.
This definition is due to Vivek Borkar.
•
The first part of the talk will be a tutorial on ergodic properties of
diffusions,
including some recent results of Nikolai V. Krylov and V.I. Bogachev.
•
Subsequently, we present some key new results:
(a) if each stationary Markov control is stable, then the
controlled diffusion is
uniformly stable, and
(b)
that uniform boundedness of the mean hitting time of some bounded
domain
is sufficient for uniform stability.
•
Next, we present equivalent characterizations of uniform stability,
either in terms
of the collection of invariant probability measures, or via stochastic
Lyapunov
functions.
•
Lastly, we discuss applications in optimal control.
Michael Zazanis:
Fluid Queues and the Superposition of ON/OFF Sources with
Unequal Characteristics
We consider superpositions of a large number of markovian
ON/OFF sources with unequal characteristics and examine
the types of limit processes obtained. We also examine
multidimensional versions of such processes as inputs to
coupled queueing systems and obtain logarithmic asympotics
for the workload in the light-tailed case.
Andrew Richards:
Subexponential Geometric Sums. How good are the asymptotics?
Geometric sums of random variables are objects of interest in their own
right, and useful in applications. In the case of subexponetial
summands, the asymptotics of the tail distribution of the sum is easy
to obtain, but finding an upper bound for the sum is a hard problem. We
consider one method for constructing an upper bound for the relative
error of the asymptotic relation, and show how to use the result in
practice using several examples.
Ju-Yi Yen:
Asset allocation: with non-Gaussian factors and exponential utilities
We build a multivariate portfolio model and analyze empirical results
of the investment. A signal processing technique known as independent
component analysis is applied to decompose multivariate financial time
series into statistically independent components (ICs). These ICs are
assumed to follow the pure jump non-Gaussian process. The process
allows one to capture movements in skewness and kurtosis as well as
volatility.
Boris Bocharov: Solving stochastic integral
inclusions using maximal
monotone operators.
Stochastic integral inclusions with maximal monotone
operators are considered in Banach Spaces. Implicit numerical
scheme(s) are presented. Furthermore, the convergence of the
approximations to the solution of the inclusion is established.
Finally, it is suggested how the original problem can be generalized
in a number of ways.
Dmitry Korshunov:
Lamperti's approach to transience, positive and null reccurence
The first part of the talk is devoted to classification of
one-dimensional Markov chains according to the asymptotic behaviour of
the first two moments of their jumps. This classification is due to J.
Lamperti, from 60's. The second part of the talk is about heavy-traffic
analysis for stationary distributions of Markov chains. Also, stability
problems for stationary distributions will be considered. We conclude
with applications to ALOHA and to queueing systems with state-dependent
service rate.
Amanda Turner:
Planar aggregation and the coalescing Brownian flow
Diffusion limited aggregation (DLA) is a random growth model which was
originally introduced in 1981 by Witten and Sander. This model is
prevalent in nature and has many applications in the physical sciences
as well as industrial processes. Unfortunately it is notoriously
difficult to understand, and only one rigorous result has been proved
in the last 25 years. We consider a simplified version of the
Hastings-Levitov model of planar aggregation which is
obtained by composing certain independent random conformal maps and
show that the evolution of harmonic measure on the boundary of the
cluster converges to the coalescing Brownian flow.
Vitali Wachtel: Heavy-traffic analysis of the
maximum of an
asymptotically stable random walk.
For families of random walks $\{S_k^{(a)}\}$ with $\mathbf E S_k^{(a)}
= -ka < 0$ we consider their maxima $M^{(a)} = \sup_{k \ge 0}
S_k^{(a)}$. We investigate the asymptotic behaviour of $M^{(a)}$ as $a
\to 0$ for asymptotically stable random walks. This problem appeared
first in the 1960's in the analysis of a single-server queue when the
traffic load tends to $1$ and since then is referred to as the
heavy-traffic approximation problem. Kingman and Prokhorov suggested
two different approaches which were later followed by many authors. We
give two elementary proofs of our main result, using each of these
approaches. It turns out that the main technical difficulties in both
proofs are rather similar and may be resolved via a generalisation of
the Kolmogorov inequality to the case of an infinite variance.
Dmitry Korshunov:
On problem of stability of Markov chains in infinite-dimensional spaces
On a particular example of a Markovian polling
system with infinitely many stations we discuss
the problem of stability (ergodicity) of the
corresponding infinite-dimensional Markov
process of queue lengths. The corresponding
Markov chain is not irreducible,
as there are clearly states which do not
communicate, e.g. the states (0,0,...)
and (1,1,...). Then, for the corresponding
infinite-dimensional Markov process, the usual
type of ergodicity cannot in general occur,
and it is necessary to introduce a modified
concept, sometimes called weak ergodicity,
which corresponds to the convergence of
the finite-dimensional distributions of
the process. Of particular interest is the
identification of functionals of the process
which do converge to the stationary version.
Henrik Hult: Efficient calculation of risk
measures by importance
sampling - the heavy-tailed case
Computation of extreme quantiles and tail-based risk measures using
standard Monte Carlo simulation can be inefficient. A large number of
samples are needed to obtain reliable estimates. A method to the reduce
computational cost is to use importance sampling. Then samples are
generated from a sampling distribution and each sample is weighted
according to its likelihood ratio. We show that importance sampling
algorithms, designed for efficient tail probability estimation, can
significantly improve Monte Carlo estimators of risk measures, such as
Value-at-Risk and Expected Shortfall. In the heavy-tailed setting, when
the random variable of interest has a regularly varying distribution,
we provide sufficient conditions for the asymptotic relative error of
importance sampling estimators to be small. The results are illustrated
by numerical examples.
Vladas Sidoravicius: On non-uniqueness for
specifications (g-functions
or chains with
infinite connections)
The question of whether a specification, also referred sometime
as g-function or “chain with infinite connectionsâ€,
uniquely determines
the stationary process under natural “mixingâ€
assumption, has been
prominent since the pioneering work of Döblin and Fortet
(1937). However
in the past time reasonable progress was achieved only in providing
sufficient conditions for the uniqueness of Gibbs measure. Bramson and
Kalikow (1993) provided a remarkable, and for decades unique example of
a
continuous and regular specification that admits multiple Gibbs
measures. During the talk I will review already known facts and will
present a new
non-uniqueness result, which in combination with uniqueness criteria of
Johansson and Öberg (2003) determines the optimal modulus of
continuity
for a specification which admits multiple Gibbs measures.
Daniel Ueltschi: Random Permutations with
Nonuniform Distributions
I will discuss various models of random permutations with nonuniform
distributions. One model involves weights that depend on the cycle
structure of the permutation. The other models deal with permutations
of points in space, and there is an additional weight that involves the
length of permutation jumps. The main question is about the possible
occurrence of infinite cycles at high enough density. These models of
random permutations are motivated by quantum statistical mechanics
and by mathematical biology. (This is joint work with V. Betz and
Y. Velenik.)
Seva Shneer: Slotted versus non-slotted
CSMA: throughputs and fairness
We consider a system consisting of n transmitters on a line. The
channel used by transmitters is such that 2 of them cannot send
messages simultaneously if the distance between them is not larger than
k, where k is a positive integer. The well-known CSMA protocol is often
used to govern the behaviour of the transmitters in this scenario, and
the performance of the system in this case is well understood.
We consider a discrete-time analogue of the CSMA protocol and in the
case of a completely saturated system find exact formulas for the total
throughput of the system governed by this algorithm and for individual
throughputs of all transmitters. We then compare these throughputs with
the throughputs achieved by the classical CSMA protocol. The fairness
of the two protocols is also compared. Finally, we discuss bounds for
the throughput of a system where the first transmitter (source) is
saturated and messages are relayed by the intermediate transmitters to
the last one (destination). A number of directions for future research
will be discussed at the end of the talk.
We give a short overview of classical random mappings models and
give some examples of the basic results. These models have natural
applications in cryptology. In particular, questions concerning the
structure of random digraphs representing mappings arise in the analysis
of cryptographic systems (e.g. DES), in applications of Pollard's
algorithm, in simulations of shift register sequences, and in
computational number theory and random number generation. To date, the
most widely studied models have been special cases of a model whose
key feature is that each vertex in the corresponding digraph `chooses'
the vertex that it is mapped to independently of the `choices' made
by all other vertices. First we will focus on results for such random
mappings with independent choices of the images which are related
to some of these applications. Then we will also consider random
mappings for which the vertex `choices' are not necessarily independent
(the joint work with Jennie Hansen). In particular, a general
model is constructed by first specifying the in-degrees of the vertices
(using a collection of non-negative integer-valued exchangeable random
variables) and then selecting a random mapping uniformly from
all mappings with the given in-degree sequence. We focus on the
corresponding properties of two special cases - the preferential and
anti-preferential attachment models.
Sandeep Juneja: Estimating Mean of Non-Linear Function of a Conditional Expectation with
Applications to Portfolio Risk Measurement
In this talk we consider the estimation of E(G[ E(Y|X)]) where G is a
non linear function, Y takes real values while X may be
multi-dimensional. Applications include risk measurement of a portfolio
containing derivatives where the value of a portfolio at a time horizon
of interest is a conditional expectation that depends on the value of
risk factors at that time. This estimation requires nested simulation:
In the outer loop independent samples of X are generated while in the
inner loop for each generated X, many samples of Y are generated.
Practitioners often view this methodology to be computationally
prohibitive and develop ad-hoc approximations that may be inaccurate. In
this talk, we analyze the trade-off between outer and inner step
computational allocation and identify the rate of convergence of the
mean square error of the optimal allocation scheme as the computational
effort increases to infinity. We note that for large portfolios it may
be optimal to simply generate a single sample in the inner loop thus
suggesting that optimally done, estimation via accurate models is
computationally viable. We also compare the nested simulation with
alternate Kernel based methods for and show that the latter may perform
better when the underlying random process has low dimensionality, while
pure nested simulation may be preferred otherwise.
Sandeep Juneja: The Concert Queuing Game: To Wait or To be Late
We introduce the concert (or cafeteria) queueing problem: A finite but
large number of customers arrive into a queueing system that starts
service at a specified opening time. Each customer is free to choose her
arrival time (before or after opening time), and is interested in early
service completion with minimal wait. These goals are captured by a cost
function which is additive and linear in the waiting time and service
completion time, with coefficients that may be class dependent. We
analyze the system in the many-customer asymptotic regime and develop a
fluid limit for the resulting queueing system. We consider a fluid model
of this system, which is motivated as the fluid-scale limit of the
stochastic system. In the fluid setting, we explicitly identify the
unique Nash-equilibrium arrival profile for each class of customers. Our
structural results imply that, in equilibrium, the arrival rate is
increasing up until the closing time where all customers are served.
Furthermore, the waiting queue is maximal at the opening time, and
monotonically decreases thereafter. In the simple single class setting,
we show that the price of anarchy (PoA, the efficiency loss relative to
the socially optimal solution) is exactly two, while in the multi-class
setting we develop tight upper and lower bounds on the PoA. In addition,
we consider several mechanisms that may be used to reduce the PoA. We
also discuss Nash equilibrium in the single class finite customer
setting and show its convergence to the fluid limit equilibrium. The
proposed model may explain queueing phenomena in diverse settings that
involve a pre-assigned opening time.
Andrew Wade: Non-homogeneous random walks
For this talk a random walk is a discrete-time time-homogeneous Markov
process on d-dimensional Euclidean space. If such a random walk is spatially
homogeneous, its position can be expressed as a sum of independent
identically distributed random vectors, and these homogeneous random walks
are
well understood. The most subtle case is when the mean dirft
(i.e., average increment) of the walk is zero.
The assumption of spatial homogeneity, while simplifying the mathematical
analysis, is not always realistic for applications. As soon as the spatial
homogeneity assumption is relaxed, the situation becomes much more
complicated:
a non-homogeneous random walk can be transient in two dimensions, for
instance.
I will give an introduction to some results on non-homogeneous
random walks with asymptotically zero mean-drift, that is, the magnitude of
the drift at a point tends to 0 as the distance of that point from the
origin tends to infinity. It turns out that this is the natural regime in
which to look for important phase transitions in asymptotic behaviour. This
includes work by Lamperti in the 1960s on recurrence/transience behaviour.
I will also discuss recent joint work with Iain MacPhee and Mikhail
Menshikov (Durham) concerned with angular asymptotics, i.e., exit-from-cones
problems. We show that, in contrast to recurrence/transience behaviour, the
angular properties of non-homogeneous random walks are remarkably
well-behaved in some sense in the asymptotically zero drift regime.
Terence Chan: Ruin probability asymptotics and bounds with
investment of surplus
In this talk I will consider asymptotics (as the initial capital goes to
infinity) and upper bounds of the ruin probability of a risk process
with a spectrally positive Levy process as claims and constant premium
rate, where the surplus is invested. Results are obtained for thin- and
fat-tailed claims distributions and investment in riskless and
risky assets.
Dimitrios Konstantinides: Precise large deviations for sums of
negatively dependent random variables with common long tailed
distributions
We investigate the precise large deviations for negatively
dependent random variables. We prove general asymptotic relations
for both the partial sums S_n for the long tailed distributions
and the random sums S_{N_t} for the subexponential distributions,
where the N_t is an integer counting process. It is found out that
the precise large deviations for negatively dependent random
variables are insensitive to this kind of dependence. Finally, we
present applications on the classical counting processes, Poisson
and renewal.
Jonathan Jordan: Geometric preferential attachment random graphs
Preferential attachment (or "scale-free") random graphs, in which a
growing network develops by new vertices attaching preferentially to
existing vertices which already have a high degree, were proposed,
originally by Barabási and Albert, as models for networks appearing in a
wide range of contexts (including biological, technological and social)
in which examination of data often reveals an approximately power law
distribution of vertex degrees. It was rigorously shown by Bollobás at
al that preferential attachment graphs did indeed have this property.
In many of the contexts in which random graph models are used it makes
sense for the vertices to have some location in space. The original
preferential attachment model has no spatial element, and in this talk I
will describe a model which combines a preferential attachment element
with a spatial element. I will describe results which show that under
certain conditions on the spatial element the power law degree property
is retained, and discuss what may happen when these conditions do not apply.
Guenter Last: On the chaos expansion on general Poisson spaces
We establish an explicit Wiener-Ito chaos expansion of Poisson
functionals. We also present some consequences for the variational
calculus of Poisson processes. Parts of the talk are based on joint
work with Mathew Penrose (Bath).
Neil Walton: Insensitive, maximum stable allocations converge to proportional fairness
We describe a queueing model where service is allocated as a
function of queue sizes. We consider allocations policies that are
insensitive to service requirements and have a maximal stability region.
We take a limit where the queueing model become congested. We study how
service is allocated under this limit. We demonstrates that the only
possible limit allocation is one that maximizes a proportionally fair
optimization problem.
Michel Mandjes: Birthday Surprises
The classical birthday problem is a standard exercise for our students:
what is the probability that, among k people, everyone has a different
birthday? Things complicate enormously, however, in the situation that
the birthdays are not equally spread over the year, and also other
ramifications can be thought of. In this presentation I will look at
various generalized birthday problems, in various asymptotic regimes.
This talk contains joint work with Sandeep Juneja (TIFR)
Damon Wischik: What mathematicians should know about the design
principles of the Internet
The IETF will soon sign off an Experimental Standard for multipath TCP.
This is the fruit of four years of work by a group of us in the computer
science department at UCL, aimed at implementing the maths in a 2005 paper
by Kelly and Voice, which was prompted by a 2003 paper by Han, Shakkottai
et al. I will describe the repositionings we made en route to deployment,
and discuss which aspects of the maths are in tune with the design
principles of the Internet.