USC.edu

Richard Arratia

Professor of Mathematics
Richard Arratia
Email rarratia@usc.edu Office KAP 406C Office Phone (213) 740-3774

Center, Institute & Lab Affiliations

  • The Center for Applied Mathematical Sciences,

Biography

My research focusses on discrete probability questions, involving the interplay of dependence and independence, and approximations of probabilities, sometimes for very unlikely events. Sometimes the description of the limit for discrete systems involves a continuum model; for example my thesis study of the voter model led to my definition of the system of coalescing Brownian motions on the real number line. Other specific topics of interest include pattern matching for sequences, and logarithmic combinatorial structures, which include permutations decomposed into cycles, and ordinary integers factored into primes;  my book “Logarithmic combinatorial structures: a probabilistic approach,” joint with Simon Tavare of USC and A. D. Barbour of University of Zurich, appeared in 2003. Another topic is interlacement in graphs, which involves linear algebra over a finite field. I have a large number of citations for a mathematician; the ISI Web of Knowledge as of October 2008 listed 921 citations total for 33 of my papers, with each of 17 different papers having more than 17 citations.  September 2023 update:  at the American Mathematical Society site MathSciNet, I have 1487 citations by 1296 authors.  My paper Random Feedback Shift Registers, and the Limit Distribution for Largest Cycle Lengths, joint with Alfred Hales and E. Rodney Canfield, solving a 60 year old conjecture of Solomon Golomb, will appear in Combinatorics, Probability, and Computing.  I am also most proud of Probabilistic Divide-and-Conquer: a New Exact Simulation Method, with Integer Partitions as an Example, published with Stephen DeSalvo, and based on his USC PHD thesis.  An easy way to view these papers, and more, is via https://arxiv.org/search/math?searchtype=author&query=Arratia%2C+R  .

Education

  • B.S. , Massachusetts Institute of Technology
  • Ph.D. , University of Wisconsin, Madison

  • Summary Statement of Research Interests

    Professor Arratia studies probability, combinatorics and number theory, especially the relation between dependence and independence. He has written a book about logarithmic combinatorial structures, and
    papers about coalescing and annihilating random walks and brownian motions, symmetric exclusion processes, sequence matching, Poisson approximation, the interlace polynomial for graphs. A favorite topic is the similarity between factorizations of random integers on the one hand, and the cycle structure of random permutations on the other hand. He serves, jointly with Sergey Lotosky, as faculty advisor to Pi Mu Epsilon, the undergraduate math honors society.

  • Book

    • Arratia, R., Barbour, A. D., Tavare, S. (2003). Logarithmic combinatorial structures: a probabilistic approach. European Mathematical Society.

    Journal Article

    • Arratia, R., DeSalvo, S. (2011). Probabilistic divide-and-conquer: a new exact simulation method, with integer partitions as an example. Combinatorics Probability and Computing. arxiv
    • Arratia, R., DeSalvo, S. (2011). On The Singularity of Random Bernoulli Matrices — Novel Integer Partitions and Lower Bound Expansions. Annals of Combinatorics. arxiv
    • Arratia, R., Barbour, A. D., Tavare, S. (2006). A tale of three couplings: Poisson-Dirichlet and GEM approximations for random permutations. Combinatorics, Probability, and COmputing. Vol. pages 31-62
    • Arratia, R., Liggett, T. M. (2005). How likely is an i.i.d. degree sequence to be graphical?. Annals of Applied Probability. Vol. Vol. 15, pp. pp. 652-670.
    • Arratia, R., Goldstein, L., Langholz, B. (2005). Local Central Limit Theorems, the High Order Correlations of Rejective Sampling, and Applications to Conditional Logistic Likelihood Asymptotics . Annals of Statistics. Vol. vol 33, pp. pp.871-914.
    • Arratia, R., Tavare, S., Barbour, A. D. (2005). A probabilistic approach to analytic arithmetic on algebraic function fields. Math. Proc. Cambridge Philos. Soc.. Vol. Vol 139, pp. p. 1-26.
    • Arratia, R., Bollobas, B., Sorkin, G. (2004). A two-variable interlace polynomial. Combinatorica. Vol. Vol. 24, pp. pp. 567-584.
    • Arratia, R., Bollobas, B., Sorkin, G. (2004). The interlace polynomial of a graph. Journal of Combinatorial Theory, Serial B. Vol. Vol. 92, pp. pp. 199-233.
    • Arratia, R., Goldstein, L., Gordon, L. (1989). Two Moments Suffice for Poisson Approximations: The Chen-Stein Method. The Annals of Probability. Vol. vol. 17 (no. 1), pp. pp. 9-25.