In this thesis, we present three works on queues. In chapter 1, we analyze two non-work-conserving variations of the M/G/1 preemptive LIFO queue, focusing on deriving expressions for the limiting distribution of workload and related quantities. In the first model, preempted customers return to the front of the queue with a new service time, while in the second, they return with their original service time. We use queueing theory methods such as the Rate Conservation Law, PASTA, regenerative process theory and Little's Law. Our results include stability and heavy-traffic limits, as well as tail asymptotics for stationary workload. In chapter 2, we analyze a queueing model with price-sensitive customers, where the service provider aims to maximize revenue and minimize the average queue length. Customers arrive according to a Poisson process, join the queue if their willingness-to-pay exceeds the offered price, and are served in a first-in first-out manner with exponential service times. Our model is applicable to cloud computing, make-to-order manufacturing, and food delivery. We provide performance guarantees for a class of static pricing policies that can achieve a constant fraction of the optimal revenue with a small increase in expected queue length. We present results for the single-server, multi-server, and multi-class cases and provide numerical findings to demonstrate the empirical performance of our policies. In chapter 3, we analyze the Adaptive Non-deterministic Transmission Policy (ANTP), a technique addressing the Massive Access Problem (MAP) in telecommunications, which involves delaying packets at the points of origin to reduce congestion. We frame these delays as time spent at a "cafe" before proceeding to the service facility. We present sample-path results, giving conditions under which ANTP does not change the total sojourn time of packets, and results under a general stochastic framework, focusing on stability and constructing proper stationary versions of the model. We prove Harris recurrence of an underlying Markov process and find positive recurrent regeneration points under i.i.d. assumptions.

Network data, particularly social network data, is widely collected in the context of interactions between users of online platforms, but it can also be observed directly, such as in the context of behaviours of animals in a group living environment. Such network data can reveal important insights into the latent structure present among the nodes of a network, such as the presence of a social hierarchy or of communities. This is generally done through the use of a latent variable model. Existing network models which are commonly used for such data often aggregate the dynamic events which occur, reducing complex dynamic events (such as the times of messages on a social network website) to a binary variable. Methods which can incorporate the continuous time component of these interactions therefore offer the potential to better describe the latent structure present. Using observed interactions between mice, we take advantage of the observed interactions’ timestamps, proposing a series of network point process models with latent ranks. We carefully design these models to incorporate important theories on animal behaviour that account for dynamic patterns observed in the interaction data, including the winner effect, bursting and pair-flip phenomena. Through iteratively constructing and evaluating these models we arrive at the final cohort Markov-Modulated Hawkes process (C-MMHP), which best characterizes all aforementioned patterns observed in interaction data. The generative nature of our model provides evidence for hypothesised phenomena and allows for additional insights compared to existing aggregate methods, while the probabilistic nature allows us to estimate the uncertainty in our ranking. In particular, our model is able to provide insights into the distribution of power within the hierarchy which forms and the strength of the established hierarchy. We compare all models using simulated and real data. Using statistically developed diagnostic perspectives, we demonstrate that the C-MMHP model outperforms other methods, capturing relevant latent ranking structures that lead to meaningful predictions for real data. While such network models can lead to important insights, there are inherent computational challenges for fitting network models, particularly as the number of nodes in the network grows. This is exacerbated when considering events between each pair of nodes. As such, new computational tools are required to fit network point process models to the large social networks commonly observed. We consider online variational inference for one such model. We derive a natural online variational inference procedure for this event data on networks. Using simulations, we show that this online learning procedure can accurately recover the true network structure. We demonstrate using real data that we can accurately predict future interactions by learning the network structure in this online fashion, obtaining comparable performance to more expensive batch methods.

The first chapter of this thesis is centered around a simple problem: to do or not to do something. As in life, every decision has an unknown outcome and planning agents try to balance the trade offs of such decision based on some relevant information. After processing the relevant information a decision is reached. In this chapter, the problem is formalized and parameterized in two frameworks: In the first framework discrete decision models known as decision trees are studied, where we design an optimization algorithm to solve the misclassification cost problem in this family of representations; The second framework studies continuously differentiable models (such as logistic regression and Deep Neural Networks) where we propose a two-step optimization procedure of the misclassification cost problem, as well as characterizing the statistical estimation problem relative to the sample size used for training. We illustrate the methodology by developing a computerized scheme to administer (or not) a preventive intervention to patients arriving to the hospital with the objective of minimizing their risk of acquiring a Hospital Acquired Infection (HAI). The second chapter expands on the idea of the first one to a sequential setting. The problem is framed as a Markov Decision Process algorithm using a state aggregation strategy based on Decision Trees. These incremental state aggregations are solved using a Linear Programming (LP) approach to obtain a compact policy that converges to the optimal one asymptotically, as well as showing that the computational complexity of our algorithm depends on the tree structure of the optimal policy rather than the cardinality of the state space. We illustrate the advantages of our approach using the widely known cartpole balancing environment against a Deep Neural Network based approach showing that with a similar computational complexity our algorithm performs better in certain instances of MDP. In the last two chapters we deal with modeling Emergency Medical Service (EMS) optimization such that the demand for medical services is met with the best possible supply allocation in the face of uncertainty of the demand in space and time. In the third chapter we develop a short-term prediction model for call volume at a 911 call center. The rationale of the model is to use the recent call volume to update a historically calibrated model of the call volume that in periods when the call volume distribution drastically changes, can be arbitrarily distant from its expected value. The model is casted as a linear correction of the historical estimation, calculating both the mean and variance of the correction. We justify the formulation using a regime switching doubly stochastic process framework to illustrate the type of distribution changes our model captures. We also propose a staffing model to preemptively staff a call center using our volume prediction as input for the call center demand such that the waiting times of the customers are minimized. This formulation can be casted as a Second Order Cone Program (SOCP) or a Linear Program (LP) with integrality constraints. We illustrate the methodology to predict the call volume during the Covid-19 pandemic to a 911 call center in New York City. In the fourth chapter we modify a well known set covering formulation to perform ambulance scheduling such that the supply of ambulances matches the demand in space and time. We enhance this model using a high resolution simulation model to correct an unknown steady-state service rate of the system (dependent on many exogenous and endogenous factors such as the ambulance dispatch policy and time-varying traffic patterns) as a constraint in the scheduling formulation. We show that this formulation effectively makes the system faster by maximizing the minimum slack between supply and demand during a 24-hour period. We present an algorithm to iteratively solve the scheduling formulation while correcting the implied location and time dependent service rate of the ambulance system using the simulation generated ambulance waiting times of patients in the city. We illustrate our algorithm to schedule municipally managed ambulances in New York City as a case study.

This thesis consists of four chapters. In Chapter 1, we focus on a class of transportation inequalities known as the transportation-information inequalities. These inequalities bound optimal transportation costs in terms of relative Fisher information, and are known to characterize certain concentration properties of Markov processes around their invariant measures. We provide a characterization of the quadratic transportation-information inequality in terms of a dimension-free concentration property for i.i.d. copies of the underlying Markov process, identifying the precise high-dimensional concentration property encoded by this inequality. We also illustrate how this result is an instance of a general convex-analytic tensorization principle. In Chapter 2, we study the entropic gradient flow property of McKean--Vlasov diffusions via a stochastic analysis approach. We formulate a trajectorial version of the relative entropy dissipation identity for these interacting diffusions, which describes the rate of relative entropy dissipation along every path of the diffusive motion. As a first application, we obtain a new interpretation of the gradient flow structure for the granular media equation. Secondly, we show how the trajectorial approach leads to a new derivation of the HWBI inequality. In Chapter 3, we further extend the trajectorial approach to a class of degenerate diffusion equations that includes the porous medium equation. These equations are posed on a bounded domain and are subject to no-flux boundary conditions, so that their corresponding probabilistic representations are stochastic differential equations with normal reflection on the boundary. Our stochastic analysis approach again leads to a new derivation of the Wasserstein gradient flow property for these nonlinear diffusions, as well as to a simple proof of the HWI inequality in the present context. Finally, in Chapter 4, we turn our attention to mean field approximation -- a method widely used to study the behavior of large stochastic systems of interacting particles. We propose a new approach to deriving quantitative mean field approximations for any strongly log-concave probability measure. Our framework is inspired by the recent theory of nonlinear large deviations, for which we offer an efficient non-asymptotic perspective in log-concave settings based on functional inequalities. We discuss three implications, in the contexts of continuous Gibbs measures on large graphs, high-dimensional Bayesian linear regression, and the construction of decentralized near-optimizers in high-dimensional stochastic control problems.

This thesis shows how to use Operations Research tools, e.g. Markov chains, optimization, game theory, and matchings, to understand problems that appear in biological contexts. We focus on two biological systems – the activation of the immune system in response to pathogens, and the metabolism of communities of different species of microbes. In Chapter 1, we study a Markov chain model of the activation of individual T-cells, and use the model to analyze how cells make trade-offs between various metrics such as speed and accuracy. In Chapter 2, we provide a detailed model of microbial community metabolism and show how incorporating aspects of game theory and dynamic stability can improve predictions of the behavior of microbial communities. Chapter 3 takes a matching approach to modeling microbial community metabolism by modeling the relationship between species and their environment using the stable marriage problem.

No description available.

This thesis consists of studies of two important problems in transfer learning: binary classification under covariate-shift transfer, and off-policy evaluation in reinforcement learning. First, the problem of binary classification under covariate shift is considered, for which the first efficient procedure for optimal pruning of a dyadic classification tree is presented, where optimality is derived with respect to a notion of 𝒂𝒗𝒆𝒓𝒂𝒈𝒆 𝒅𝒊𝒔𝒄𝒓𝒆𝒑𝒂𝒏𝒄𝒚 between the shifted marginal distributions of source and target. Further, it is demonstrated that the procedure is adaptive to the discrepancy between marginal distributions in a neighbourhood of the decision boundary. It is shown how this notion of average discrepancy can be viewed as a measure of 𝒓𝒆𝒍𝒂𝒕𝒊𝒗𝒆 𝒅𝒊𝒎𝒆𝒏𝒔𝒊𝒐𝒏 between distributions, as it relates to existing notions of information such as the Minkowski and Renyi dimensions. Experiments are carried out on real data to verify the efficacy of the pruning procedure as compared to other baseline methods for pruning under transfer. The problem of off-policy evaluation for reinforcement learning is then considered, where two minimax lower bounds for the mean-square error of off-policy evaluation under Markov decision processes are derived. The first of these gives a non-asymptotic lower bound for OPE in finite state and action spaces over a model in which the mean reward is perturbed arbitrarily (up to a given magnitude) that depends on an average weighted chi-square divergence between the behaviour and target policies. The second provides an asymptotic lower bound for OPE in continuous state-space when the mean reward and policy ratio functions lie in a certain smoothness class. Finally, the results of a study that purported to have derived a policy for sepsis treatment in ICUs are replicated and shown to suffer from excessive variance and therefore to be unreliable; our lower bound is computed and used as evidence that reliable off-policy estimation from this data would have required a great deal more samples than were available.

Discrete exponential families have drawn a lot of attention in probability, statistics, and machine learning, both classically and in the recent literature. This thesis studies in depth two discrete exponential families of concrete interest, (i) Exponential Random Graph Models (ERGMs) and (ii) Ising Models. In the ERGM setting, this thesis consider a “degree corrected” version of standard ERGMs, and in the Ising model setting, this thesis focus on Ising models on dense regular graphs, both from the point of view of statistical inference. The first part of the thesis studies the problem of testing for sparse signals present on the vertices of ERGMs. It proposes computably efficient tests for a wide class of ERGMs. Focusing on the two star ERGM, it shows that the tests studied are “asymptotically efficient” in all parameter regimes except one, which is referred to as “critical point”. In the critical regime, it is shown that improved detection is possible. This shows that compared to the standard belief, in this setting dependence is actually beneficial to the inference problem. The main proof idea for analyzing the two star ERGM is a correlations estimate between degrees under local alternatives, which is possibly of independent interest. In the second part of the thesis, we derive the limit of experiments for a class of one parameter Ising models on dense regular graphs. In particular, we show that the limiting experiment is Gaussian in the “low temperature” regime, non Gaussian in the “critical” regime, and an infinite collection of Gaussians in the “high temperature” regime. We also derive the limiting distributions of commonlt studied estimators, and study limiting power for tests of hypothesis against contiguous alternatives (whose scaling changes across the regimes). To the best of our knowledge, this is the first attempt at establishing the classical limits of experiments for Ising models (and more generally, Markov random fields).

Biomolecular machines are responsible for carrying out a host of essential cellular processes. In accordance to the wide range of functions they execute, the architectures of these also vary greatly. Yet, despite this diversity in both structure and function, they have some common characteristics. They are all large macromolecular complexes that enact multiple steps during the course of their functions. They are also ’Brownian’ in nature, i.e., they rectify the thermal motions of their surroundings into work. Yet how these machines can utilise their surrounding thermal energy in a directional manner, and do so in a cycle over and over again, is still not well understood. The work I present in this thesis spans the development, evaluation and use of biophysical, in particular single-molecule, tools in the study of the functional mechanisms of biomolecular machines. In Chapter 2, I describe a mathematical framework which utilises both the framework of Bayesian inference to relate any experimental data to an ideal template irrespective of the scale, background and noise in the data. This framework may be used for the analysis of data generated by multiple experimental techniques in an accurate, fast, and human-independent manner. One such application is described in Chapter 3, where this framework is used to evaluate the extent of spatial information present in experimental data generated using cryogenic electron microscopy (cryoEM). This application will not only aid the study of biomolecular structure using cryoEM by structural biologists, but also enable biophysicists and biochemists who use structural models to interpret and design their experiments to evaluate the cryoEM data they need to use for their investigations. In Chapter 4, I describe an investigation into the use of one class of analytical models, hidden Markov models (HMMs) to accurately extract kinetic information from single-molecule experimental data, such as the data generated by single-molecule fluorescence resonance energy transfer (smFRET) experiments. Finally in Chapter 5, I describe how single-molecule experiments have led to the discovery of a mechanism by which ligands can modulate and drive the conformational dynamics of the ribosome in a manner that facilitates ribosome-catalysed protein synthesis. This mechanism has implications to our understanding of the functional mechanisms of the ribosome in particular, and of biomolecular machines in general.

The progress of a unimolecular chemical degradation reaction is used in representing a component failure mechanism. The component is said to fail when the concentration of reaction product accumulates beyond an acceptable level. The process of accumulating reaction product is modelled as a Markov pure birth process which, in turn, is used in developing the failure time distribution. The model is analyzed under the assumption that the reaction rate is constant. Also, the initial state and the final state of the degradation process are assumed to be Poisson variables. Based on numerical examples, it is found that the failure model can be described as a three-parameter or two-parameter Weibull distribution. / Master of Science