Williams holds the Charles Lee Powell Chair in Mathematics at the UC San Diego. She is a mathematician who works in probability theory, especially on stochastic processes and their applications. She is particularly known for her foundational work on reflecting diffusion processes in domains with corners, for co-development with Maury Bramson of a systematic approach to proving heavy traffic limit theorems for multiclass queueing networks, and for the development of fluid and diffusion approximations for the analysis and control of more general stochastic networks, including those described by measure-valued processes. Her current research includes the study of stochastic models of complex networks, for example, those arising in Internet congestion control and systems biology.
Williams studied mathematics at the University of Melbourne where she earned her Bachelor of Science (Honours) and Master of Science degrees. She then studied at Stanford University where she earned her Ph.D. degree in Mathematics. She had a postdoc at the Courant Institute of Mathematical Sciences in New York before taking up a position as an assistant professor at UC San Diego. She has remained at UC San Diego during her career, where she is now a Distinguished Professor of Mathematics.
Williams is an elected member of the US National Academy of Sciences, an elected fellow of the American Academy of Arts and Sciences, an elected corresponding member of the Australian Academy of Science, an inaugural fellow of the American Mathematical Society, a fellow of the Institute for Operations Research and the Management Sciences, a fellow of the American Association for the Advancement of Sciences, and a fellow of the Institute of Mathematical Statistics. She is also a fellow of St. Hilda's College at the University of Melbourne, and received an honorary Doctor of Science degree from La Trobe University in Australia. Williams has been a Guggenheim Fellow, an Alfred P. Sloan Fellow and a National Science Foundation Presidential Young Investigator. She delivered a 45-minute invited address at the International Congress of Mathematicians in 1998.
Areas of Expertise (5)
Stochastic Processes and Applications
Complex networks (e.g., optimization and control, resource sharing, dimension reduction)
Award for the Advancement of Women in Operations Research and the Management Sciences, INFORMS
John von Neumann Theory Prize, Institute for Operations Research and the Management Sciences
President of the Institute of Mathematical Statistics
Best Publication Award of the INFORMS Applied Probability Society
Stanford University: Ph.D., Mathematics 1983
University of Melbourne: M.S., Mathematics
University of Melbourne: B.Sc. (Hons), Mathematics
Media Appearances (1)
UCSD Math Professor Awarded Prestigious Prize
NBC San Diego
Ruth Williams, Ph.D, was awarded the John von Neumann Theory Prize at the annual meeting of the Institute for Operations Research and the Management Sciences (INFORMS) in Nashville, TN on Sunday night. She shares the award with researcher Martin Reiman from the Department of Industrial Engineering and Operations Research at Columbia University...
Paul J Steiner, Ruth J Williams, Jeff Hasty, Lev S Tsimring
The contrast between the stochasticity of biochemical networks and the regularity of cellular behavior suggests that biological networks generate robust behavior from noisy constituents. Identifying the mechanisms that confer this ability on biological networks is essential to understanding cells. Here we show that queueing for a limited shared resource in broad classes of enzymatic networks in certain conditions leads to a critical state characterized by strong and long-ranged correlations between molecular species. An enzymatic network reaches this critical state when the input flux of its substrate is balanced by the maximum processing capacity of the network. We then consider enzymatic networks with adaptation, when the limiting resource (enzyme or cofactor) is produced in proportion to the demand for it. We show that the critical state becomes an attractor for these networks, which points toward the onset of self-organized criticality. We suggest that the adaptive queueing motif that leads to significant correlations between multiple species may be widespread in biological systems.
Ruth J Williams
Stochastic processing networks arise as models in manufacturing, telecommunications, transportation, computer systems, the customer service industry, and biochemical reaction networks. Common characteristics of these networks are that they have entities—such as jobs, packets, vehicles, customers, or molecules—that move along routes, wait in buffers, receive processing from various resources, and are subject to the effects of stochastic variability through such quantities as arrival times, processing times, and routing protocols. The mathematical theory of queueing aims to understand, analyze, and control congestion in stochastic processing networks. In this article, we begin by summarizing some of the highlights in the development of the theory of queueing prior to 1990; this includes some exact analysis and development of approximate models for certain queueing networks. We then describe some surprises of the early 1990s and ensuing developments of the past 25 years related to the use of approximate models for analyzing the stability and performance of multiclass queueing networks. We conclude with a description of recent developments for more general stochastic processing networks and point to some open problems.
V Pesic, RJ Williams
We consider a dynamic scheduling problem for parallel server systems. J. M. Harrison has proposed a scheme for using diffusion control problems to approximately solve such control problems for heavily loaded systems. This approach has been very successfully used in the special case when the diffusion control problem can be reduced to an equivalent one for a one-dimensional workload process. However, it remains a challenging open problem to make substantial progress on using Harrison’s scheme when the workload process is more than one-dimensional. Here we present some new structural results concerning the diffusion control problem for parallel server systems with arbitrary workload dimension. Specifically, we prove that a certain server-buffer graph associated with a parallel server system is a forest of trees. We then exploit this graphical structure to prove that there exists a matrix, used to define the workload process, that has a block diagonal-like structure. An important feature of this matrix is that, except when the workload is one-dimensional, this matrix is frequently different from a choice of workload matrix proposed by Harrison. We demonstrate that our workload matrix simplifies the structure of the control problem for the workload process by proving that when the original diffusion control problem has linear holding costs, the equivalent workload formulation also has a linear cost function. We also use this simplification to give sufficient conditions for a certain least control process to be an optimal control for the diffusion control problem with linear holding costs. Under these conditions, we propose a continuous review threshold-type control policy for the original parallel server system that exploits pooling of servers within trees in the server-buffer graph and uses non-basic activities connecting different trees in a critical manner. We call this partial pooling. We conjecture that this threshold policy is asymptotically optimal in the heavy traffic limit. We illustrate the solution of the diffusion control problem and our proposed threshold control policy for a three-buffer, three-server example.
David Lipshutz, Ruth J Williams
Deterministic dynamical system models with delayed feedback and nonnegativity constraints arise in a variety of applications in science and engineering. Under certain conditions oscillatory behavior has been observed and it is of interest to know when this behavior is periodic. Here we consider one-dimensional delay differential equations with nonnegativity constraints as prototypes for such models. We obtain sufficient conditions for the existence of slowly oscillating periodic solutions (SOPS) of such equations when the delay/lag interval is long and the dynamics depend only on the current and delayed state. Under further assumptions, including possibly longer delay intervals and restricting the dynamics to depend only on the delayed state, we prove uniqueness and exponential stability for such solutions. To prove these results, we develop a theory for studying perturbations of these constrained SOPS. We illustrate our results with simple examples of biochemical reaction network models and an Internet rate control model.
William H Mather, Jeff Hasty, Lev S Tsimring, Ruth J Williams
It has been shown experimentally that competition for limited translational resources by upstream mRNAs can lead to an anticorrelation between protein counts. Here, we investigate a stochastic model for this phenomenon, in which gene transcripts of different types compete for a finite pool of ribosomes. Throughout, we utilize concepts from the theory of multiclass queues to describe a qualitative shift in protein count statistics as the system transitions from being underloaded (ribosomes exceed transcripts in number) to being overloaded (transcripts exceed ribosomes in number). The exact analytical solution of a simplified stochastic model, in which the numbers of competing mRNAs and ribosomes are fixed, exhibits weak positive correlations between steady-state protein counts when total transcript count slightly exceeds ribosome count, whereas the solution can exhibit strong negative correlations when total transcript count significantly exceeds ribosome count. Extending this analysis, we find approximate but reasonably accurate solutions for a more realistic model, in which abundances of mRNAs and ribosomes are allowed to fluctuate randomly. Here, ribosomal fluctuations contribute positively and mRNA fluctuations contribute negatively to correlations, and when mRNA fluctuations dominate ribosomal fluctuations, a strong anticorrelation extremum reliably occurs near the transition from the underloaded to the overloaded regime.