Iain M MacPhee

Department of Mathematical Sciences

Job: Lecturer
Address: Dept. of Mathematical Sciences,
University of Durham,
South Road,
Durham DH1 3LE,
England
FAX: (0191 or +44 191) 334 3051
E-mail: i.m.macphee@durham.ac.uk
Phone: (0191 or +44 191) 334 3106

My research interests and links to publications

I have interests in a range of probability and operations research areas. My recent work is on problems such as

Some years ago now I worked on

Random walks with weak homogeneity assumptions

Since his arrival in Durham I have worked with Mikhail Menshikov on various problems concerning the long-term behaviour (recurrence, transience) of discrete time random walks. Our approach is via a collection of results on local expected drifts of the process (Foster's criterion is a simple result of this type) rather than using stationarity conditions or transform theory. This allows us to relax assumptions about homogeneity of jump distributions though we do need conditions on the moments of the jumps.

Very complex models can be studied in this way. We have applied these techniques to interacting particle systems with hybrid interaction, long term behaviour of random walk in the plane with mild regularity conditions, various phenomena displayed by random walks on two-dimensional complexes (collections of quarter planes connected at their boundaries) inspired by models from computer science.

Random walks and particle systems

In recent years Misha and I, together with Andrew Wade who has recently moved to Strathclyde University in Glasgow, have put a great deal of effort into various models using local expected drifts and Lyapunov functions to study stability and long-term behaviour. We found some stability results for a recent interacting particle system with mixed voter-exclusion moves. A draft of "Passage-time moments and hybrid zones for the exclusion-voter model" can be found on arxiv at can be found here . This paper has been accepted by Bernoulli to appear in 2010. We still have some ideas to explore in the particle system model. We have also established necessary and sufficient conditions for a.s. finite exit times of weakly homogeneous random walks from cones. We have a large number of results which we have recently organised into two papers. A preliminary draft, "Exit times from cones for non-homogeneous random walk with asymptotically zero drift" can be found here . A rather different version of some of the results here, which we've called Angular asymptotics ... has been accepted by Markov Chains and Related Fields to appear in 2010.

Models inspired by polling systems

Polling systems have many queues with a single server and a rule to determine the order the queues are serviced in and when the server should change queue. A random walk on a complex made by connecting a set of orthants at their boundaries provides a natural model of any queueing systems where occasional control decisions e.g. movement of the server in a polling system or more generally re-arrangement of servers in a queueing system, change the process dynamics in a wholesale way. In 2006/07 Misha and I worked with Dimitri Petritis and Serguei Yu Popov on a polling system model (exponential service times and Poisson arrivals) with parameter regeneration. By this we mean that the arrival and service rates can change each time the server switches to another queue. Our results have now appeared in the Annals of Applied Probability: the case where there are only two stations in 2007 and the general case in 2008. This model displays some interesting behaviour. Even though all service times have exponential moments there can be a thick region of the parameter space where the process is null recurrent. Similarly there can be regions where the process is positive recurrent but return times to the empty state have only finitely many moments. This heavy-tail type behaviour arises because the system sometimes has an overall arrival rate larger than the service rate so that extremely large queues develop.

In 2003/04 we wrote, together with Serguei Popov and Stas Volkov, a paper on periodic behaviour for a type of stochastic billiards model that arises from projecting the trajectories of a transient three queue exhaustive polling system onto the unit simplex. It appeared in the Annals of Applied Probability in 2006 and can be downloaded from Project Euclid here. We expected that under a greedy switching rule (go to the queue with the most work) the server would eventually visit the queues in some periodic order but found that chaotic switching could occur on a parameter set of measure zero.

My first paper with Misha appeared in the Annals of Applied Probability in 2003. It contains a detailed analysis of the possible behaviours of a critical random walk on a complex of quarter planes joined at their boundaries - with just two quarter planes this would model a polling system with two queues.

Stability of controlled queueing systems

Most recently I have been looking at the supermarket model together with Misha and Marina Vachkovskaia. In this model arrivals are routed to queues through a neighbourhood structure. The long term dynamics of a random walk based on this model shows some interesting clustering behaviour which we have tried to explain here .

From 2004 to 2006 I worked with a PhD student Lisa Müller on identifying criteria for stability and instability of two queue systems which have a range of different service regimes - these each have Poisson arrival streams and exponential service times but the parameters vary between regimes. Our aim was to specify all sets of system parameters such that there exist control policies (state dependent rules for deciding which service regime to apply) under which the system is stable or alternatively when the system is unstable under any control.

The notion of service regimes is a useful one as it allows very general purpose models but lets us describe the decision problem in a simple manner. It also fits together well with the available Lyapunov function or semi-martingale methods, see e.g. Fayolle, Malyshev and Menshikov's book , which deal very well with systems where the transition law is homogeneous over large regions.

In the course of the work it became clear to me that under some mild requirements on the available controls the very natural conditions we had found for stability of the two queue system could be extended to larger systems. The conditions are described in terms of the convex hull of the set of one step drift vectors (one for each service regime). The resulting paper appeared in Queueing Systems, V52 #3 in 2006. Here is a link to an earlier draft if you are interested in reading about our model and results.

We have also looked at extensions of our result for N queue sytems to Lu-Kumar type systems where some queues only receive jobs forwarded from other servers within the system - such systems do not satisfy the boundary reflection condition used in the QSys paper but there is a simple condition that permits the results to be extended. We have written a further paper which appeared in Methodology and Computing in Applied Probability V9 #3 in 2007 (here is a link to a draft). It contains an application of our ideas to a model studied by Nino-Mora and Glazebrook (J. Appl. Prob 2000).

We also have some results for the model with phase type service distributions and some ideas for treating switching times of various types. Lisa in now working the cycling organisation Sustrans so progress has slowed but I plan to return to this work when I have time.

Reliability for low structure models

My colleague Frank Coolen is very interested in foundational issues in statistics and decision theory and their application within operations research problems. He has many publications in the field of nonparametric predictive inference (NPI). In discussion with Pauline Coolen-Schrijner it became clear that there was a a potentially elegant solution to an interesting application of NPI to a system reliability model. Pauline and I made a good start on this problem and a joint paper with Pauline and Frank on this work has appeared in the Journal of Risk and Reliability, V222, pp 463-476.

I am now supervising another graduate student, Ahmad Aboalkhair, who started in May 2008. We are working together with Frank Coolen on extending the system reliability model discussed above. Progress so far has been good and we have had a paper proving an extension of the results with Coolen-Schrijner and Coolen accepted by JRR.

Admission and routing in queueing networks

I worked for quite a while on admissions and routing problems in queueing networks, particularly loss networks where arrivals that overflow buffers are lost. I have a paper with Ilze Ziedins , `Admission controls for loss networks with diverse routing' in Stochastic Networks , a 1996 O.U.P. book edited by Kelly, Zachary and Ziedins.

Moving target search

From 1993 to 1995 I had a PhD student called Ben Jordan who became very interested in search problems, particularly the problem of searching a finite number of sites for a target that moves from site to site. Each search of site i costs C_i and fails to find the target a) if it is not there; b) with chance a_i even if it is there.

The problem with only 2 sites and Markovian dynamics had a conjectured solution due to Sheldon Ross sometime in the 1970s. Before each search calculate p, the probability that the target is at site 1. Ross suggests we search site 1 precisely when p > = P* (a threshold that depends on the costs, overlook probabilities and transition matrix) and otherwise search site 2.

Ben and I wrote a paper establishing the conjecture for almost all transition matrices which was published in PEIS V9, pp159-182. Here is a .pdf file of a draft of the paper for those who do not have easy access to the 1995 issues of PEIS.

Ben did a lot of numerical work and symbolic manipulation on the two site problem but also on cases with three and four sites. Alas he went to work as a currency trader before completing this work.

Last updated: 19/3/09