Workshop on

The Center for Applied Probability at Georgia Tech will hold a Special Topic Two-Day Workshop focusing on decision processes, entitled

The Workshop is centered around four main speakers, with one speaker for each of four areas of decision process applications. The speakers and topics for the Workshop are the following.

Professor P. R. Kumar (Department of Electrical and Computer
Engineering and Coordinated Science Laboratory, University
of Illinois at Urbana) will speak on
*New Directions in Scheduling Manufacturing
Systems: Performance Analysis and Design.*

Professor Stanley R. Pliska (Department of Finance, University of Illinois at Chicago) will speak on mathematical finance.

Professor David O. Siegmund (Department of Statistics,
Stanford University) will speak on *Change-point Problems
and Applications.*

Professor William D. Sudderth (School of Statistics, University of Minnesota at Minneapolis) will speak on gambling and stochastic games.

The speaker for each area is being asked to give two one-hour talks, with the two hours containing some background, having some breadth, mentioning some important recent results and techniques in the area, and giving some good open problems in the area. Although much of the talks should not require too much background, each of the speakers has prepared a reading list with both some general and specific readings in the area related to their talk, for those who may wish to preview the areas of application before the talks. Here are the reading lists prepared by the speakers.

(Requests for further information may be addressed to Bob Kertz, preferably by email (kertz@math.gatech.edu), by telephone (404-894-2700), or by regular mail (School of Mathematics). More information about this workshop can be found from our World Wide Web page at http://nanjing.isye.gatech.edu/cap/96-workshop/workshop.html).

"New Directions in Scheduling Manufacturing Systems: Performance Analysis and Design"

Department of Electrical and Computer Engineering

and Coordinated Science Laboratory

University of Illinois at Urbana

Many manufacturing and other systems, e.g., communication networks and
computer systems, are modeled as queueing networks. Frequently one
wants to control such systems by an appropriate choice of a scheduling
policy.

On the descriptive side, in the 1950s, Jackson obtained the explicit formulas for the steady-state distribution of certain queueing networks. This class was expanded in the 1970s through the work of Baskett, Chandy, Muntz and Palacios, and Kelly, and others. However, most queueing networks do not satisfy the stringent and fragile assumptions of this theory.

Recently, we have developed new methods for addressing questions related to the performance of such networks. Instead of seeking exact explicit answers, the goal of this new approach is to reduce issues related to performance analysis to the well developed computational approach of solving linear programs.

This approach allows one to obtain bounds on the steady-state or transient performance of key quantities such as mean delay or throughput, establish the stability or efficiency of systems, address issues related to heavy traffic performance such as asymptotic loss or pole multiplicity, and obtain dominating functional expansions.

On the prescriptive side, over the past few years we have developed new approaches whose philosophy is to introduce feedback, stability and dynamics into the modeling, analysis and synthesis of manufacturing systems. By this approach one seeks to avoid static formulations which often lead to intractable combinatorial optimization problems over a finite time horizon. By studying the dynamics of systems, one hopes to design distributed policies which can be implemented in real-time and which yield good performance. Such an approach has led to the design of scheduling policies for systems with set-up times, due-dates, etc., and to new results concerning some commonly mentioned dispatching rules. It has also led to new approaches for scheduling large scale plants.

The two talks will attempt to address these new approaches.

An excellent reference for the classical work on performance evaluation for queueing networks is,

F. P. Kelly, *Reversibility and Stochastic Networks.*
New York, NY: John Wiley and Sons, 1979.

Early accounts of sequencing and scheduling can be found in the following two books,

K. Baker, *Introduction to Sequencing and Scheduling.*
New York, NY: John Wiley and Sons, 1974,

and

R. W. Conway, W. L. Maxwell, and L. W. Miller, *Theory
of Scheduling.*
Reading, MA: Addison--Wesley, 1967.

An up to date account of the above approach to scheduling is given in the excellent survey,

E. L.Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, and D. B. Shmoys,
``Sequencing and Scheduling: Algorithms and Complexity,''
in S. C. Graves et al., Eds., *Handbooks in OR and MS*, vol. 4,
pp. 445--522, Elsevier Science Publishers, Amsterdam, 1993.

Now we turn to the topics addressed in these talks. These are mostly taken from the following articles, many of which are available at the following WWW location:

http://black.csl.uiuc.edu/prkumar

If you need hard copies, please send a message to:

Kumar, P. R. (1994). *Scheduling Manufacturing Systems of Re-Entrant
Lines, pages 325--360, in Stochastic Modeling and Analysis of
Manufacturing Systems*, Springer-Verlag, New York, NY, David
D. Yao (ed.).

Kumar, P. R. (1994). "Scheduling queueing networks: Stability, performance
analysis and design." Technical report, Coordinated Science
Laboratory, University of Illinois, Urbana, IL. To appear in
*Stochastic Networks*, IMA Volumes in Mathematics and its
Applications, Frank Kelly and Ruth Williams, Editors,
Springer-Verlag.

Kumar, P. R. (1995). "A tutorial on some new methods for performance
evaluation of queueing networks." *IEEE Journal on Selected Areas
in Communications: Special Issue on -- Advances in the Fundamentals
of Networking -- Part I: Bridging Fundamental Theory and Networking*
13 (6), 970--980.

Bielecki, T. and Kumar, P. R. (1988). "Optimality of zero-inventory policies
for unreliable manufacturing systems." *Operations Research* 36,
(4), 532--541.

Perkins, J. R. and Kumar, P. R. (1989). "Stable distributed real-time
scheduling of flexible manufacturing/assembly/disassembly systems."
*IEEE Transactions on Automatic Control* AC-34 (2), 139--148.

Kumar, P. R. and Seidman, T. I. (1990). "Dynamic instabilities and
stabilization methods in distributed real-time scheduling of
manufacturing systems." *IEEE Transactions on Automatic Control*
AC-35 (3), 289--298.

Perkins, J. R. , Humes, Jr., C. and Kumar, P. R. (1994). "Distributed
scheduling of flexible manufacturing systems: Stability and
performance." *IEEE Transactions on Robotics and Automation:
Special Section on Computer Integrated Manufacturing* 10 (2), 133--141.

Lu, S. H. and Kumar, P. R. (1991). "Distributed scheduling based on due
dates
and buffer priorities". *IEEE Transactions on Automatic Control*
AC-36 (12), 1406--1416.

Winograd, G. I. and Kumar, P. R. (1994). "Stable network topologies, bounds
on
traffic burstiness and delay, and control by regulators." To appear in
*Mathematical and Computer Modelling: Special Issue on Recent
Advances in Discrete Event Systems.*

Perkins, J. R. and Kumar, P. R. (1995). "Optimal control of pull manufacturing systems." Technical report, University of Illinois, Urbana, IL. submitted to the 1994 ACC.

D. Bertsimas, I. C. Paschalidis, and J. N. Tsitsiklis, ``Optimization of
multiclass queueing networks: Polyhedral and nonlinear characterizations of
achievable performance,'' *Annals of Applied Probability*, vol. 4,
pp. 43--75, 1994.

Kumar, S. and Kumar, P. R. (1994). "Performance bounds for queueing networks
and scheduling policies." *IEEE Transactions on Automatic
Control* AC-39, 1600--1611.

Kumar, P. R. and Meyn, S. P. (1995). "Stability of queueing networks and
scheduling policies." *IEEE Transactions on Automatic Control*
40 (2), 251--260.

Kumar, P. R. and Meyn, S. P. (1993). "Duality and linear programs for stability
and performance analysis of queueing networks and scheduling policies."
Technical report, C. S. L., University of Illinois. To appear
in *IEEE Transactions on Automatic Control.*

Jin, H., Ou, J. and Kumar, P. R. (1994). "The throughput of closed queueing
networks--functional bounds, asymptotic loss, efficiency, and the
Harrison-Wein conjectures." Submitted to *Mathematics of
Operations Research.*

Humes, Jr., C., Ou, J. and Kumar, P. R. (1995). *Delay and throughput
bounds
for open and closed queueing networks: Uniform functional expansions,
heavy traffic pole multiplicities, stability and efficiency.*
Coordinated Science Laboratory, University of Illinois.

Department of Finance

University of Illinois at Chicago

It is easy to pinpoint the birth of mathematical finance: the thesis "Theory of Speculation," presented to the Faculty of Sciences of the Academy of Paris on March 29, 1900, by Louis Bachelier for the degree Docteur es Sciences Mathematiques. Bachelier not only made a brilliant application of mathematics to the problem of evaluating the price of a call option, but he invented what came to be called Brownian motion for the purpose of modeling the price of the underlying stock. Unfortunately, Bachelier's fantastic work was ignored and forgotten for half a century. It is unclear why he did not receive more credit for inventing Brownian motion, but perhaps he received little attention for his option pricing model because Brownian motions become negative, whereas stock prices do not. In any event, an English translation of Bachelier's thesis is found in Cootner (1964), a collection of various papers, most of which deal with statistical aspects of stock market prices.

During the 1950s and 1960s, financial research primarily addressed statistical and economic problems, but one problem that challenged many was the same as Bachelier's: what is the correct price of a call option? Researchers soon agreed that geometric Brownian motion is a good model for the price of a stock, but they could not agree on much else until 1971, when Black and Scholes provided the critical insight. They argued that if the value of a portfolio of traded securities coincided almost surely with the payoff of the call option, then the earlier value of the call option must coincide with the earlier value of the portfolio. They showed how a portfolio involving the underlying stock coupled with borrowing and lending at a constant interest rate could replicate the call option's payoff, they derived a partial differential equation whose solution is the value of the option, and they solved this equation to obtain their now famous ``Black and Scholes formula." Not only did they invent a formula that is commonly used by speculators around the world, but they kicked off ``arbitrage pricing theory" and they triggered research in what is now called mathematical finance.

During the 1970s, much of the research in mathematical finance had a partial differential equation orientation, with geometric Brownian motion models of the security prices lurking in the background. For example, Merton made some significant applications of the pde technology to portfolio management problems (most of his papers are collected in his 1990 book). There were some successful attempts to combine arbitrage pricing theory with other models of security prices (notably the discrete time, binomial option pricing model treated in the book by Cox and Rubinstein), but advancements seemed to be held back by the lack of general theory. A major breakthrough was provided by Harrison and Kreps (1979), who recognized that for a securities market model to be sensible from the economic standpoint, the discounted security prices must be martingales after a change of probability measure. Moreover, they recognized that the gain or loss of a portfolio should be modeled as a stochastic integral of the trading strategy with respect to the price process, leading to very general risk neutral valuation principles for determining the price of a derivative. Their work was quickly fleshed out and elucidated by Harrison and Pliska (1981), who also developed important linkages with the powerful techniques of modern stochastic calculus. The foundations were then in place for the analysis of very general derivatives in conjunction with very general models of security prices.

Hence during the 1980s, mathematical finance turned away (somewhat) from partial differential equation toward a probabilistic approach. By the end of the decade there was a good understanding of the basic theory, as evidenced, for example, by the excellent 1989 survey by Karatzas, who confines his attentions to price process models having continuous sample paths. Recent research can be classified into several main categories, such as attempts to obtain improvements of the Black and Scholes formula by considering more realistic models of the underlying security or by considering the impact of transaction costs. Considerable attention was also given to the valuation of exotic options and other derivatives. But perhaps the main theme in recent years has been the development of term structure models of interest rates, used for the valuation of interest rate based derivatives. Some key papers here are by Vasicek (1977), Cox, Ingersoll, and Ross (1985), and Heath, Jarrow, and Morton (1992).

Cootner, P. (1964).*The Random Character of Stock Market Prices. *
The
M.I.T. Press, Cambridge, MA

Cox, J. Ingersoll, J.
and Ross, S. (1985). "A theory of the term structure of interest rates."
*Econometrica* 53 385-408.

Cox, J. and Rubinstein, M. (1985).*Options Markets.*
Prentice Hall, Englewood Cliffs, New Jersey.

Harrison, J. and
Kreps, D. (1979). "Martingales and arbitrage in multiperiod securities
markets."
*J. Economic Theory* 20 381-408.

Harrison, J. and Pliska, S. (1981).
"Martingales and stochastic integrals in the theory of continuous trading."
*Stochastic Processes and Their Applications* 11 215--260.

Heath, D.
Jarrow, R. and Morton, A. (1992). "Bond pricing and the term structure
of interest
rates: a new methodology for contingent claims valuation." *Econometrica*
60 77--105.

Karatzas, I. (1989). "Optimization problems in the theory
of continuous trading." *SIAM J. Control and Optimization * 27
1221--1259.

Merton, R. (1990). *Continuous-Time Finance. Basil Blackwell,*
Cambridge,
MA.

Vasicek, O. (1977). "An equilibrium characterization
of the term structure." *J. Fin. Econ.* 5 177--188.

Duffie, D. (1988).
*Security Markets -- Stochastic Models.* Academic Press, New York.

Duffie, D. (1992).
*Dynamic Asset Pricing Theory.* Princeton University Press,
Princeton, NJ.

Ingersoll, J. (1987). *Theory of Financial Decision
Making*. Rowman and Littlefield, Totowa, NJ.

"Change Point Problems and Applications"

Department of Statistics

Stanford University

The list of references for the talks on "Change Point Problems and Applications" are given below. Some are overview articles, and some are quite technical. My suggestions for preliminary study are Worsley (1986), Feingold (1993), and Siegmund (1986, 1989).

Siegmund (1988) and Siegmund and Venkatraman (1995) are in my opinion the most interesting mathematically, but they get quite technical. Similar material is presented in Siegmund (1992) with slightly more streamlined proofs.

Although I have not yet made a final decision about content, I expect the first talk to be general and the second to emphasize applications to genetics. I can easily explain the minimal genetics background. The papers by Risch and by Lander and Botstein (in addition to Feingold (1993)) would be useful to someone who wanted more than the minimal background. I suspect it would make sense to read them afterwards, if one wants to know more about the application, rather than in advance.

Feingold, E. (1993). "Markov processes for modeling and analyzing a
new genetic mapping
method." *Jour. of Appl. Probab.* 30, 766--779.

Feingold, E., Brown, P. O., Siegmund, D. (1993). "Gaussian models for
genetic linkage
analysis using complete high resolution maps of identity-by-descent."
*Am. J. Hum. Genetics*
53, 234--251.

James, B., James, K. L., and Siegmund, D. (1987). "Tests for a change-point."
*Biometrika*
74, 71--83.

Lander, E. S. and Botstein, D. (1989). "Mapping Mendelian factors underlying
quantitative
traits using RFLP linkage maps." *Genetics* 121, 185--199.

Risch, N. (1990a, b). "Linkage strategies for genetically complex traits
I, II:
The power of affected relative pairs." *Am. J. Hum. Genetics* 46,
222--228, 229--241.

Siegmund, D. (1986). "Boundary crossing probabilities and statistical
applications."
*Ann. Statist.* 14, 361--404.

Siegmund, D. (1988). "Tail approximations for the maxima of some random
fields."
*Ann. Probab.* 16, 487--501.

Siegmund, D. (1989). "Confidence sets in change-point problems."
*International
Statistical Review* 56, 31--48.

Siegmund, D. (1992). "Tail approximations for maxima of random fields,"
in
*Probability Theory: Proceedings of the 1989 Singapore Probability
Conference,*
edited by L. H. Y. Chen, K. P. Choi, Kaiyuan Yu, Jiann-Hua Lou, de Gruyter,
Berlin.

Siegmund, D. and Venkatraman, E. S. (1995). "Using the generalized
likelihood ratio
statistic for sequential detection of a change-point." *Ann. Statist.*
23, 255--271.

Worsley, K. (1986). "Confidence regions and tests for a change-point
in a sequence
of exponential family random variables." *Biometrika* 73, 91--104.

Worsley, K. J., Evans, A. C., Marrett, S. and Neelin, P. (1992). "A
three dimensional
statistical analysis for CBF activation studies in human brain." *J.
of Cerebral
Blood Flow and Metabolism* 12, 900--918.

Worsley, K. and Siegmund, D. (1995). "Testing for a signal with unknown
location and
scale in a stationary Gaussian random field". *Ann. Statist.* 23,
608--639.

Gambling and Stochastic Games

School of Statistics

University of Minnesota

The now classic work *How to Gamble If You Must: Inequalities for
Stochastic Processes* by Dubins and Savage (1965) uses gambling terminology
and examples to develop and motivate an elegant, deep, and quite general
theory of discrete-time stochastic control. A gambler ``controls" the
stochastic process of his or her successive fortunes by choosing
which games to play and what bets to make.

The first lecture will introduce the ideas of Dubins and Savage as well as some more recent developments in gambling theory. The second lecture will apply gambling techniques to two-person, zero-sum stochastic games. These are games in which two players control a stochastic process jointly but have opposing goals.

Dubins, L., Maitra, A., Purves, R. and Sudderth, W. (1989).
"Measurable, nonleavable gambling problems" *Israel J. Math.* 67
257--271.

Maitra, A. and Sudderth, W. (1995). "Stochastic games and
operators," in *Topics in Contemporary Probability and its Applications,*
J. L. Snell, editor, CRC Press, New York.

Maitra, A. and Sudderth, W. (1992). "An operator solution of
stochastic games." *Israel J. Math.* 78 33--49.

Milnor, J. and Shapley, L. S. (1957). "On games of survival."
*Contributions to the Theory of Games III,* edited by M. Dresher,
A. W. Tucker, and P. Wolfe, Princeton University Press.

Raghavan, T. E. S., Ferguson, T., Parthasarathy, T.,
and Vrieze, O. J. (1991). *Stochastic Games and Related
Topics in Honor of Professor L. S. Shapley.* Kluwer Academic Publishers,
Boston.

Maitra, A. and Sudderth, w. (to appear). *Discrete
Gambling and Stochastic Games,* Springer-Verlag, New York.

*Last updated: January 11, 1996 by J. Shear ( joannas@isye.gatech.edu)*