Abstracts
Speakers
Abstracts
Konstantin Avrachenkov (INRIA)
(Joint work with N. Litvak and D. Nemirovsky)
Monte Carlo methods for personalized PageRank
PageRank is one of the principal criteria according to which Google ranks relevant answers to a user query. PageRank can be viewed as a random walk on the Web graph with uniform random jumps after a geometrically distributed number of steps. It can also be viewed as a singular perturbed Markov chain. PageRank is not able to take into account personal preferences of the users. To address this problem, the Personalized PageRank criterion has been proposed. In the Personalized PageRank the random walk on the Web graph restarts with a non-uniform distribution representing user preferences and interests. Since a user is typically interested in some top list of relevant answers, we propose to use Monte Carlo methods which find top lists with very light complexity. We study and compare several Monte Carlo methods analytically as well as numerically.
Vivek Borkar (Tata Institute of Fundamental
Research) (Joint work with V. Gaitsgory (UniSA) and K. Sureshkumar (IIT,
Mumbai)
Singular perturbations in stochastic control
There has been much research in past on controlled diffusions with a slow and a fast component, the latter parametrized by a small parameter. A typical result shows that in the limit as this parameter converges to zero, the slow component of the controlled diffusion is well approximated by a diffusion obtained by averaging its dynamics over the asymptotic behaviour of the fast component. This programme has been carried out for integral cost criteria by several authors, e.g., Kabanov, Pergamenshchikov, Kushner, not to mention the corresponding work in deterministic control. This talk will describe how such results are also obtained for the harder criteria of ergodic or long run average cost, and risk-sensitive cost. This is joint work with V. Gaitsgory (UNISA) and K. Sureshkumar (IIT, Mumbai).
Vladimir Gaitsgory (UniSA)
Linear Programming Based Analysis and Solution of
Nonlinear Infinite Horizon Optimal Control Problems
We will discuss relationships between the deterministic infinite time horizon optimal control problems with discounting and time averaging criteria, in which the state trajectories remain in a given compact set
Y , and certain (corresponding to these problems) infinite dimensional linear programming (IDLP) problems. We will introduce the problems dual with respect to this IDLP problems and state some duality results. We will construct necessary and sufficient optimality conditions for the optimal control problems under consideration, and we will give a characterization of the viability kernel of Y . We will also indicate a way of how one can use finite dimensional approximations of the IDLP problem and their respective duals for construction of near optimal feedback controls. Theoretical results will be illustrated with numerical examples.Tony Guttman ((University of Melbourne)
Spanning trees, lattice Green functions and
Calabi Yau equations
In recent work trying to calculate lattice Green functions for 4 dimensional lattices, we discovered that the ODEs satisfied by the Green functions are of Calabi-Yau type, and similar to those encountered in string theory. We also exploited a connection between the problem of enumerating spanning trees and lattice Green functions, and will attempt to present a cohesive view of these results.
Moshe Haviv (The Hebrew University of
Jerusalem) (Joint work with Yoav Kerner)
To queue or not to queue: The cases of partially and fully observable
M/G/1 queues
The intuition while observing the economy of queueing systems, is that one's motivation to join the system, decreases with its level of congestion. This is certainly true in the case where service times are memoryless or when the actual workloads are known.
However, as in the quite general queueing model we describe below, sometimes the opposite is the case.
The point of departure is the standard first-come first-served single server queue with Poisson arrivals. Customers commence service immediately if upon their arrival the server is idle. Otherwise, they are informed if the queue is empty or not. Then, they have to decide whether to join or not. We assume that the customers are homogeneous and when they consider their moves, they assess their queueing costs against their reward due to service completion. As the whereabouts of customers interact, we look for the (possibly mixed) join/do not join Nash equilibrium strategy, a strategy that if adopted by all, then under the resulting steady-state conditions, no one has any incentive not to follow it oneself. We show that when the queue is empty then, depending on the service distribution, both `avoid the crowd' (ATC) and `follow the crowd' (FTC) scenarios (as well as none-of-the-above) are possible. (Under ATC (FTC, reps.) one's best action is do the opposite of (same as, reps.) what all others do.) When the queue is not empty, the situation is always that of ATC. Also, we show that under Nash equilibrium it is possible (depending on the service distribution) that the joining probability when the queue is empty is smaller than it is when the queue is not empty.
The key technical difficulty in the above partially observable model is to assess the mean residual service times of the one who is currently in service, given the information of an empty or not empty line. This task becomes even harder in the fully observable case when the actual queue length is informed prior to action taking. This is due to the fact that the mean residual service time is queue-length dependent.
Moreover, as customers decide whether to join or not, a symmetric joining (mixed) policy prescribes a joining probability to each queue length. Thus, the resulting arrival process is no longer Poisson but one with queue-length dependent joining rates. We derive the Laplace-Stieltjes transform for the residual service time given the queue length and define a recursive procedure for the corresponding means for this state dependent arrival rate model. Implicit formulas for the equilibrium joining probabilities are then determined.
Roger Horn (University of Utah)
Matrix canonical forms
You are in your office; the door is open. A well-dressed visitor walks in confidently without knocking. He has a single sheet of wrinkled paper in his left hand and a partially open brown envelope in his right hand. Without any introduction, he strides to your desk and drops the paper and envelope on top of the ungraded midterm exams and un.nished referee reports. Glancing at the paper, you see a bold red "Eyes Only" stamp and a complex 7-by-7 matrix; visible in the envelope is a neat stack of crisp $100 bills.
"Tell me about that matrix," he says.How do you respond? "It is nilpotent and has Jordan blocks of sizes three and four", or "Its Hermitian part is positive semidefinite", or "It is congruent to a diagonal matrix'? Probably not a good way to begin. . . better to ask some questions: "Where do the data come from?", "Tell me about your experiment", "Does your problem have any symmetries or invariants?", or "Does this matrix interact with others in some way?"
The questions are intended to uncover any natural equivalence relations lurking behind your visitor.s matrix; if so, reducing it to a corresponding canonical form might be illuminating.
We give examples of a variety of matrix equivalence relations that arise in practice and discuss canonical forms corresponding to some of them. We pay special attention to an underappreciated alternative to the Jordan canonical form for similarity, and to a recently discovered canonical form for congruence that has helped solve an outstanding problem in quantum error detection.
Phil Howlett (UniSA) (joint work with Amie
Albrecht (UniSA) and Charles Pearce (UAdelaide)
Laurent series for inversion of linearly perturbed bounded linear
operators on Banach Space
(Joint work with Amie Albrecht and Charles Pearce.) We find necessary and sufficient conditions for the existence of a Laurent series expansion with a finite order pole at the origin for the inverse of a linearly perturbed bounded linear operator mapping one Banach space to another. In particular we show that the inversion defines linear projections that separate the Banach spaces into corresponding complementary subspaces. We present two pertinent examples.
Fima Klebaner (Monash University) (Joint
work with Robert Lipster)
Ruin Analysis in the Constant Elasticity of Variance Model
(Joint work with Robert Liptser) We give results on the probability of absorption at zero of the diffusion process with non-Lipschitz diffusion coefficient dX_t=\mu X_tdt+\sigma X^\gamma_tdB_t, with X_0=K, and 1/2\le \gamma<1. In finance this is known as the Constant Elasticity of Variance Model. Our results give information on the time to ruin \tau_{0}=\inf\{t:X_t=0\}. We show that $P(\tau_{0}\le T)>0 for all T, give the probability of ultimate ruin, and establish asymptotics for \lim\limits_{K\to\infty} \frac{1}{K^{2(1-\gamma)}}\log\mathsf{P}(\tau_{0 }\le T).
In addition we find an approximation to the most likely paths to ruin by solving a control problem.
Jacek Krawczyk (Victoria University of
Wellington)
Computation of a viability kernel for the four meta-state
monetary-policy macroeconomic problem
A small open-economy model where the exchange rate becomes an additional channel for the transmission of monetary policy can be presented as a four meta-state control system. Computation of the viability kernel for this system is crucial for the Reserve Bank to establish satisfying (or viable) policies. We characterise the viability kernel as the hypograph of a supersolution to the Bellman-Hamilton-Jacobi equation obtained for an auxiliary optimal control problem.
We approximate the kernel using a numerical optimisation method, suitable for stochastic optimal control problems (InfSOCSol).
Dirk Kroese (University of Queensland) (Joint
work with Zdravko Botev)
Efficient Monte Carlo Simulation via The Generalized Splitting Method
(Joint work with Zdravko Botev) We describe a new Monte Carlo algorithm for the consistent and unbiased estimation of multidimensional integrals and the efficient sampling from multidimensional densities. The algorithm is inspired by the classical splitting method and can be applied to general static simulation models. We provide examples from rare-event probability estimation, counting, and sampling, demonstrating that the proposed method can outperform existing Markov chain sampling methods in terms of convergence speed and accuracy.
Walter Murray (Stanford University) (Joint
work with Nick Henderson)
A gradient flow algorithm for linearly constrained optimization
There are two basic methods used in algorithms to find minima of smooth
problems: line search methods, and trust-region methods. In the first type a
direction of descent is first found and then a step length is determined. In
trust-region methods the size of step is first determined and then the
direction. To find points that satisfy second-order conditions as opposed to
finding only a stationary point requires knowing directions of negative
curvature. Incorporating such directions into line search and trust-region
methods results in algorithms that are not invariant to scaling. In an address
to American Mathematical Society in 1941 Courant proposed three methods for
solving PDEs. Two, finite differences and finite elements, have since become
well established. We shall describe a method for optimization that is in spirit
similar to Courant's third method. Specifically an ODE is defined and the search
for an improved iterate is made over the arc that solves the ODE. Giang Nguyen (UniSA)
Hamiltonian cycle problem and a PhD with Jerzy Filar
The famous Hamiltonian cycle problem (HCP) can be stated as follows: Given a
graph, find a cycle that passes through every single vertex exactly once, or
determine that such a cycle does not exist. We present an embedding of the
Hamiltonian cycle problem in a Markov decision process, which turns this
discrete problem into a continuous, stochastic, sequential decision problem. The
latter formulation leads to new characterisations of Hamiltonian cycles and new
algorithms. T. E. S. Raghavan
On discounted stochastic games with perfect information
An algorithm to locate optimal pure stationary strategies for discounted stochastic games with perfect information are given. This algorithm has some nice combinatorial structure intrinsic to discounted case.
Floske Spieksma (University of Leiden)
Deviation matrices: existence, unicity properties and perturbations
As the starting point we consider an irreducible and ergodic Markov chain on
a countable state space. Denote the corresponding transition matrix by P and
the stationary matrix by Pi. Then the deviation matrix D = lim_{\alpha \uparrow
1} \alpha^n (P^n - \Pi) exists as a finite limit if and only if the return
time to a single selected state has a finite second moment. If this is the
case, D is the unique solution to the system of equations
D = 0
I - \Pi + PD = D.
If we associate a reward r(x) with system state x, then the second equation becomes the Poisson equation
r - g + Pv = v, and we seek to find a solution pair (g, v), where g is a constant and v a vector on the state space. Under a suitable Lyapunov function condition, it is well-known that the Poisson equation has a solution pair (g^*; v^*), with g^* = \Pi r unique and v^* unique up to a constant in a certain Banach space. If the return time to a single state has a finite second moment, then, upto a constant, v = Dr. However, if the second moment is infinite, then a solution to the Poisson equation still exists even though the deviation matrix does not.
We will discuss the unicity issue extensively and discuss criteria for testing finiteness of the second moment of the return times.
Then we will turn to a parametrised set of Markov chains. The deviation matrix can be used to obtain a bound on the difference between the average rewards associated with different Markov chains from the collection. For obtaining these bounds an alternative expansion of the deviation matrix turns out to be useful.The parametrised set can be a collection of perturbations of a given Markov chain. In the case of a finite state space process, we will finally characterise regularity of a perturbation through the discounted deviation from stationarity. Peter Taylor (University of Melbourne)
Some thoughts on Parrondo's Games
Late in 1998 when I was working at the University of Adelaide, Derek Abbott, a colleague from the Electrical and Electronic Engineering Department, knocked on my door and showed me some interesting simulations. They were implementations of two games, developed by a Spanish physicist Juan Parrondo, which are both biased against the player. However, if the player alternates between the games or chooses which game to play in a random fashion, the ensuing game is biased in favour of the player.
I was initially sceptical of Derek's results. However, using only elementary probability theory, it is relatively easy to establish that his conclusions were correct. Since then, a large literature has grown dealing with various extensions and applications of Parrondo's games. My contributions have included some comments on the definition of what it means for a game to be fair; a rigorous proof that Parrondo's drift criteria do imply positive recurrence, null recurrence or transience of the corresponding birth and death process and the observation that the phenomenon observed by Parrondo should be thought of as ubiquitous, rather than unusual.
In this talk I will tell the story of my involvement with Parrondo's games.Peter Zograf (Steklov Mathematical Institute
Fractals and filars of regular graphs
We describe a a fractal threadlike structure of the class of all regular graphs associated with the spectra of their adjacency matrices. Points with coordinates given by the mean and variance of the exponentials of graph eigenvalues cluster around a line segment that we call a "filar" (i.e. a "threadlike object"; this term also recognizes J. Filar's initial contribution to the subject). Zooming-in reveals that this cluster splits into smaller segments (filars) labeled by the number of triangles in graphs, which, in turn, split into subfilars labeled by the number of quadrangles in graphs, etc. We give a mathematical justification of this phenomenon based on the Ihara-Selberg trace formula.