SForm Apoed

192 PAG MB No. 0704-019

- |A 284 19 th bownte fcu1
o
r 1 t 4em mmWo WAIPV14. w#rdhwng N1
9
a~ta~ WwIa, rs.
oi"OdIeadeadlen SometW. a" hoey ow of ths
i lillill "I an~ dBdget awwor AedutacePfog(0794133. Wavuegto. DC 20503.
1. AGER S. REPORT PE ANO DATES COVERED
. TITLE A ,oT FINAL 15 OCT 93 - 14 APR 94
4.TIL AD U5iL FONDING NUMBER, S
FINITE MARKOV CHAINS AND RANDOM DISCRETE STRUCTUREU) AF/F49620-94-1
6. AUTNOR(S)
Avner-Friedman- -
Willard Miller, Jr.
7. PERFORMING ORGANIZATION NAME(S) AND ADORESS(ES) 8. PERFORMING ORGANIZATION
REPORT NUMBER
Institute for Mathematics and its Applications
University of Minnesota
IMA Final Report-1
514 Vincent Hall
206 Church Street SE AMTR- 9 4 052
V0.19Ji0GfNI i'V0N G AGENCY NAME(S) AND ADDRESS(ES) in MONITORING
ENa ERT NUMBER
Air Force Office of Scientific Rese ch D
110 Duncan Avenue, Suite B15 E TE
Boiling AFB, DC 20332-6448 0 .1994
11. SUPPLEMENTARY NOTES-
~F
See attached list
128. DISTIBUTION/AVAILAILITY STATEMENT 12b. DISTRIBUTION CODE
APPROVED FOR PUBLIC RELEASE:V
DISTRIBUTION UNLIMITED 1
13. ABSTRACT (Maximum 200 words)
This grant from the Air Force Office of Scientific Research supported the research related to the two IMA Work-
shops Finite Markov Chain Renaissance held on October 18-22, 1993 and Random Discrete Structures held on
November 15-19, 1993. The first workshop was organized by Persi Diaconis and David Aldous, while the second
one by David Aldous and Robin Pemantle. Both workshops were integral parts of the IMA 1993-1994 year-
long program on "EMERGING APPLICATIONS OF PROBABILITY." The October workshop addressed the
following issues: Theoretical computer science examples: successes and open problems; computation-Bayesian
statistics; Classical probability examples: successes and open problems; Mathematical theory and other aspects
of Markov Chains. The November workshop explored examples from Jung's work on synchronicity to recent
studies of parapsychology; random graphs; random permutations and Stein's method. In addition this workshop
addressed new questions concerning probability on discrete infinite structures.
The services of J. Michael Steele, a senior fellow was partially supported by this grant. Steele provided over-all
direction for the entire probability program. Similarly, the grant supported 8 one-month visitors and 21 workshop
participants.
Grant AF/F49620-94-1-009 also supported the publication of the technical research reports submitted by the
workshop participants for inclusion in the the IMA Preprint Series, and two IMA Proceedings Volumes.
14. SUBJECT TERMS 15. NUMBER OF PAGES
random discrete structures, theoretical computer science, Bayesian statistics, classi- 5
9 cal probability, Markov chains, Jung's work on synchronicity, random graphs, ran- 1W. PRICE CODE
dom permutations 1
17. SECURITY CLASSIFICATION It. SECURITY CLASSIFICATION 19. SECURITY CLASSIFICATION 20. LIMITATION OF ABSTRACT
OF REPORT Of THIS PAGE OF ABSTRACT
UNCLASSIFIED UNCLASSIFIED UNCLASSIFIED SAR
NSN 7S40-01-280-5500 '"Standard Form 298 (Rev. 2-89)
PItetdbed by ANSI Std Z35-I
. .- 298-02
-7r
- .
INSTITUTE FOR MATHEMATICS AND ITS APPLICATIONS
(1) CONTRACT OR GRANT NUMBER: AF/F49620-94-1-0009
(2) PERIOD COVERED BY REPORT: October 15, 1993-July 1994
(3) GRANT TITLE: FINITE MARKOV CHAINS AND RANDOM DISCRETE
STRUCTURES
(4) NAME OF INSTITUTION: UNIVERSITY OF MINNESOTA, MINNEAPO-
LIS
(5) AUTHOR OF REPORT: Avner Friedman
LIST OF MANUSCRIPTS SUBMITTED FOR THE IMA PROCEEDINGS
VOLUMES UNDER AFOSR SPONSORSHIP
DISCRETE PROBABILITY AND ALGORITHMS (workshop was held on Septem-
ber 20-24, and 1993 and October 18-22, 1993)
Editors: David Aldous, Persi Diaconis, J. Michael Steele and Joei Spencer
1. David Aldous, On simulating a Markov chain stationary distribution when
transition probabilities are unknown
2. Noga Alon, A note on network reliability
3. Persi Diaconis and Anil Cangolli, Rectangular arrays with fixed margins
4. Persi Diaconis and Susan Holmes, Three Examples of Monte-Carlo Markov
Chains: at the Interface between Statistical Computing, Computer Sci-
ence, and Statistical Mechanics
5. James Allen Fill and Robert P. Dobrow, The move-to-front rule for self-
organizing lists with Markov dependent requests
6. Anant P. Godbole, Daphne E. Skipper, and Rachel A. Sunley, The asymp-
totic lower bound on the diagonal ramsey numbers: A closer look
7. Anna R. Karlin and Prabhakar Raghavan, Random walks and undirected
graph connectivity: a survey
8. Joel Spencer and Prasad Tetali, Sidon sets with small gaps
9. J. Michael Steele, Variations on the monotone subsequence
10. Eli Shamir, Generalized chromatic numbers of random graphs
DTIC QUALITY fNPECITED 3
94-29018
IIIIIIlll igl-u|94 9 06 090
A F/F49620-94-1-0009 FINAL TECHNICAL REPORT 2
1I. Dominic Welsh, Randomised approximation schemes for Tutte-Gr6thendieck
invariants
12. J.E. Yukich, Quasi-Additive Euclidean Functionals
RANDOM DISCRETE STRUCTURES (workshop was held on November 15-
19, 1993)
Editors: David Aldous and Robin Pemantle
1. David Aldous, Probability distributions on cladograms
2. Robert M. Burton and William G. Faris, Stability of self-organizing pro-
cesses
3. Amir Dembo and Ofer Zeitouni, Large deviations for random distribution
of mass
4. Amir Dembo and Yosef Rinott, Some examples of normal approximations
by Stein's method
5. Luc Devroye and Olivier Kamoun, Random minimax game tress
6. Persi W. Diaconis, Susan Holmes, Svante Janson, Steven P. Lallek, and
Robin Pemantle, Metrics on compositions and coincidences among renewal
sequences
7. Bert Fristedt, Intersections and limits of regenerative sets
8. Martin Hildebrand, Random Processes of the form X,+, = anX, + b,
(mod p) where b, takes on a single value
9. Svante Janson, The second moment method, conditioning and approxi-
mation
10. Charles R. Johnson and John H. Drew, The no long odd cycle theorem
for completely positive matricies
11. Russell Lyons, How fast and where does a random walker move on a
random tree?
12. Sam Northshield, Recurrence, amenability, and the universal cover of Acce,.ior, For
graphs NTIS CRA&I
13. Robin Pemantle, Sharpness of second moment criteria for branching and DTIC TAB
tree-indexed processes. This paper is rejected by Pemantle himself. Unanrour'ced
Justification
14. Robin Pemantle and Yuval Peres, On which graphs are all random walks
in random environments transient? By
Distribution I
Ava,3!,. , ,
Dist Special
a-I
A F/F49620-94-1-0009 FINAL TECHNICAL REPORT
3
15. Thomas S. Salisbury, Energy, and intersections of Markov chains
16. Paul Erd6s, Svante Janson, Tomasz Luczak and Joel Spencer, A note on
triangle-free graphs
LIST OF MANUSCRIPTS PUBLISHED IN THE IMA PREPRINT SERIES
UNDER AFOSR SPONSORHIP
1166 Ruiben D. Spies, Local existence and regularity of solutions for a math-
ematical model of thermomechanical phase transitions in shape memory
materials with Landau-Ginzburg free energy
1168 Angelo Favini, Mary Ann Horn, Irena Lasiecka & Daniel Tataru,
Global existence, uniqueness and regularity of solutions to a Von Kirm'in
system with nonlinear boundary dissipation
1186 Mary Ann Horn & Irena Lasiecka, Uniform decay of weak solutions
to a von l(Armin plate with nonlinear boundary dissipation
1187 Mary Ann Horn, Irena Lasiecka & Daniel Tatarxi, Well-posedness
and uniform decay rates for weak solutions to a von Kirmin system with
nonlinear dissipative boundary condlitions
1189 Frank H. Sliaw & Charles J. Geyer, Constrained covariance compo-
nient models
1193 Svante Janson, Random regular graphs: Asymptotic distributions and
contiguity
1197 Steven P. Lalley, Random series in inverse Pisot powers
1200 J~nos Pacli, Farliad Sliabrokiii & Mario Szegedy, Application of
the crossing number
1202 Jnel Spencer, The Erd6s- IIanani conjecture via Tlalagrand 's ine-quality
1204 Rtiss'l1 Lyons, Robin Peinantle 8z Yuval Peres, WVhen does a branch-
ing p,-ocess grow like its mean? Conceptual proofs of L log L. criteria
1205 Robin Peinantle, Maxiirn variation of total risk
1206 Robin Pernantle & Vuival Peres, Galton-Wal-son trees with the same
mean have the same polar sets
1207 Robin Peniantle, A shuffle that mixes sets of ally fixed size tniidi faster
than it mixes the whole (deck
Al"F9620-94-1-l009 FINAL TECHINICAL REPORT '
1208 Itai Benijarniii, Robiin Pem-antle & Yuvfkl Peres, Martin capacity
for Markov chains and random walks in varying dimensions
1209 Wlodlziinierz Bryc & Aii-ir Demnbo, On large deviations of empirical
measures for stationary Gaussian processes
M R FORCE OF Srlc!TTFIC RESFA!RCH (AFSC)
C)TICE OF TI2 T4'L TO DTIiC
us t'r~~1hS
be-n rc..viewed and is
c~prm~. ~ iC release 1AW AFR 190-12
Joan by
STINFO Program Manager