-
Model-based clustering of time-dependent observations with common structural changes
Authors:
Riccardo Corradin,
Luca Danese,
Wasiur R. KhudaBukhsh,
Andrea Ongaro
Abstract:
We propose a novel model-based clustering approach for samples of time series. We assume as a unique commonality that two observations belong to the same group if structural changes in their behaviours happen at the same time. We resort to a latent representation of structural changes in each time series based on random orders to induce ties among different observations. Such an approach results i…
▽ More
We propose a novel model-based clustering approach for samples of time series. We assume as a unique commonality that two observations belong to the same group if structural changes in their behaviours happen at the same time. We resort to a latent representation of structural changes in each time series based on random orders to induce ties among different observations. Such an approach results in a general modeling strategy and can be combined with many time-dependent models known in the literature. Our studies have been motivated by an epidemiological problem, where we want to provide clusters of different countries of the European Union, where two countries belong to the same cluster if the spreading processes of the COVID-19 virus had structural changes at the same time.
△ Less
Submitted 12 October, 2024;
originally announced October 2024.
-
Enzyme kinetic reactions as interacting particle systems: Stochastic averaging and parameter inference
Authors:
Arnab Ganguly,
Wasiur R. KhudaBukhsh
Abstract:
We consider a stochastic model of multistage Michaelis--Menten (MM) type enzyme kinetic reactions describing the conversion of substrate molecules to a product through several intermediate species. The high-dimensional, multiscale nature of these reaction networks presents significant computational challenges, especially in statistical estimation of reaction rates. This difficulty is amplified whe…
▽ More
We consider a stochastic model of multistage Michaelis--Menten (MM) type enzyme kinetic reactions describing the conversion of substrate molecules to a product through several intermediate species. The high-dimensional, multiscale nature of these reaction networks presents significant computational challenges, especially in statistical estimation of reaction rates. This difficulty is amplified when direct data on system states are unavailable, and one only has access to a random sample of product formation times. To address this, we proceed in two stages. First, under certain technical assumptions akin to those made in the Quasi-steady-state approximation (QSSA) literature, we prove two asymptotic results: a stochastic averaging principle that yields a lower-dimensional model, and a functional central limit theorem that quantifies the associated fluctuations. Next, for statistical inference of the parameters of the original MM reaction network, we develop a mathematical framework involving an interacting particle system (IPS) and prove a propagation of chaos result that allows us to write a product-form likelihood function. The novelty of the IPS-based inference method is that it does not require information about the state of the system and works with only a random sample of product formation times. We provide numerical examples to illustrate the efficacy of the theoretical results.
△ Less
Submitted 10 September, 2024;
originally announced September 2024.
-
Local times of self-intersection and sample path properties of Volterra Gaussian processes
Authors:
Olga Izyumtseva,
Wasiur R. KhudaBukhsh
Abstract:
We study a Volterra Gaussian process of the form $X(t)=\int^t_0K(t,s)d{W(s)},$ where $W$ is a Wiener process and $K$ is a continuous kernel. In dimension one, we prove a law of the iterated logarithm, discuss the existence of local times and verify a continuous dependence between the local time and the kernel that generates the process. Furthermore, we prove the existence of the Rosen renormalized…
▽ More
We study a Volterra Gaussian process of the form $X(t)=\int^t_0K(t,s)d{W(s)},$ where $W$ is a Wiener process and $K$ is a continuous kernel. In dimension one, we prove a law of the iterated logarithm, discuss the existence of local times and verify a continuous dependence between the local time and the kernel that generates the process. Furthermore, we prove the existence of the Rosen renormalized self-intersection local times for a planar Gaussian Volterra process.
△ Less
Submitted 6 September, 2024;
originally announced September 2024.
-
On the Fidelity Distribution of Link-level Entanglements under Purification
Authors:
Karim Elsayed,
Wasiur R. KhudaBukhsh,
Amr Rizk
Abstract:
Quantum entanglement is the key to quantum communications over considerable distances. The first step for entanglement distribution among quantum communication nodes is to generate link-level Einstein-Podolsky-Rosen (EPR) pairs between adjacent communication nodes. EPR pairs may be continuously generated and stored in a few quantum memories to be ready for utilization by quantum applications. A ma…
▽ More
Quantum entanglement is the key to quantum communications over considerable distances. The first step for entanglement distribution among quantum communication nodes is to generate link-level Einstein-Podolsky-Rosen (EPR) pairs between adjacent communication nodes. EPR pairs may be continuously generated and stored in a few quantum memories to be ready for utilization by quantum applications. A major challenge is that qubits suffer from unavoidable noise due to their interaction with the environment, which is called decoherence. This decoherence results in the known exponential decay model of the fidelity of the qubits with time, thus, limiting the lifetime of a qubit in a quantum memory and the performance of quantum applications.
In this paper, we evaluate the fidelity of the stored EPR pairs under two opposite dynamical and probabilistic phenomena, first, the aforementioned decoherence and second purification, i.e. an operation to improve the fidelity of an EPR pair at the expense of sacrificing another EPR pair. Instead of applying the purification as soon as two EPR pairs are generated, we introduce a Purification scheme Beyond the Generation time (PBG) of two EPR pairs. We analytically show the probability distribution of the fidelity of stored link-level EPR pairs in a system with two quantum memories at each node allowing a maximum of two stored EPR pairs. In addition, we apply a PBG scheme that purifies the two stored EPR pairs upon the generation of an additional one. We finally provide numerical evaluations of the analytical approach and show the fidelity-rate trade-off of the considered purification scheme.
△ Less
Submitted 27 October, 2023;
originally announced October 2023.
-
Towards inferring network properties from epidemic data
Authors:
István Z. Kiss,
Luc Berthouze,
Wasiur R. KhudaBukhsh
Abstract:
Epidemic propagation on networks represents an important departure from traditional massaction models. However, the high-dimensionality of the exact models poses a challenge to both mathematical analysis and parameter inference. By using mean-field models, such as the pairwise model (PWM), the complexity becomes tractable. While such models have been used extensively for model analysis, there is l…
▽ More
Epidemic propagation on networks represents an important departure from traditional massaction models. However, the high-dimensionality of the exact models poses a challenge to both mathematical analysis and parameter inference. By using mean-field models, such as the pairwise model (PWM), the complexity becomes tractable. While such models have been used extensively for model analysis, there is limited work in the context of statistical inference. In this paper, we explore the extent to which the PWM with the susceptible-infected-recovered (SIR) epidemic can be used to infer disease- and network-related parameters. The widely-used MLE approach exhibits several issues pertaining to parameter unidentifiability and a lack of robustness to exact knowledge about key quantities such as population size and/or proportion of under reporting. As an alternative, we considered the recently developed dynamical survival analysis (DSA). For scenarios in which there is no model mismatch, such as when data are generated via simulations, both methods perform well despite strong dependence between parameters. However, for real-world data, such as foot-and-mouth, H1N1 and COVID19, the DSA method appears more robust to potential model mismatch and the parameter estimates appear more epidemiologically plausible. Taken together, however, our findings suggest that network-based mean-field models can be used to formulate approximate likelihoods which, coupled with an efficient inference scheme, make it possible to not only learn about the parameters of the disease dynamics but also that of the underlying network.
△ Less
Submitted 5 February, 2023;
originally announced February 2023.
-
Likelihood-Free Dynamical Survival Analysis Applied to the COVID-19 Epidemic in Ohio
Authors:
Colin Klaus,
Matthew Wascher,
Wasiur R. KhudaBukhsh,
Grzegorz A. Rempala
Abstract:
The Dynamical Survival Analysis (DSA) is a framework for modeling epidemics based on mean field dynamics applied to individual (agent) level history of infection and recovery. Recently, DSA has been shown to be an effective tool in analyzing complex non-Markovian epidemic processes that are otherwise difficult to handle using standard methods. One of the advantages of DSA is its representation of…
▽ More
The Dynamical Survival Analysis (DSA) is a framework for modeling epidemics based on mean field dynamics applied to individual (agent) level history of infection and recovery. Recently, DSA has been shown to be an effective tool in analyzing complex non-Markovian epidemic processes that are otherwise difficult to handle using standard methods. One of the advantages of DSA is its representation of typical epidemic data in a simple although not explicit form that involves solutions of certain differential equations. In this work we describe how a complex non-Markovian DSA model may be applied to a specific data set with the help of appropriate numerical and statistical schemes. The ideas are illustrated with a data example of the COVID-19 epidemic in Ohio.
△ Less
Submitted 31 July, 2022;
originally announced August 2022.
-
Hypergraphon Mean Field Games
Authors:
Kai Cui,
Wasiur R. KhudaBukhsh,
Heinz Koeppl
Abstract:
We propose an approach to modelling large-scale multi-agent dynamical systems allowing interactions among more than just pairs of agents using the theory of mean field games and the notion of hypergraphons, which are obtained as limits of large hypergraphs. To the best of our knowledge, ours is the first work on mean field games on hypergraphs. Together with an extension to a multi-layer setup, we…
▽ More
We propose an approach to modelling large-scale multi-agent dynamical systems allowing interactions among more than just pairs of agents using the theory of mean field games and the notion of hypergraphons, which are obtained as limits of large hypergraphs. To the best of our knowledge, ours is the first work on mean field games on hypergraphs. Together with an extension to a multi-layer setup, we obtain limiting descriptions for large systems of non-linear, weakly-interacting dynamical agents. On the theoretical side, we prove the well-foundedness of the resulting hypergraphon mean field game, showing both existence and approximate Nash properties. On the applied side, we extend numerical and learning algorithms to compute the hypergraphon mean field equilibria. To verify our approach empirically, we consider a social rumor spreading model, where we give agents intrinsic motivation to spread rumors to unaware agents, and an epidemics control problem.
△ Less
Submitted 27 October, 2022; v1 submitted 30 March, 2022;
originally announced March 2022.
-
Dynamic Survival Analysis for non-Markovian Epidemic Models
Authors:
Francesco Di Lauro,
Wasiur R. KhudaBukhsh,
Istvan Z. Kiss,
Eben Kenah,
Max Jensen,
Grzegorz A. Rempala
Abstract:
We present a new method for analyzing stochastic epidemic models under minimal assumptions. The method, dubbed DSA, is based on a simple yet powerful observation, namely that population-level mean-field trajectories described by a system of PDE may also approximate individual-level times of infection and recovery. This idea gives rise to a certain non-Markovian agent-based model and provides an ag…
▽ More
We present a new method for analyzing stochastic epidemic models under minimal assumptions. The method, dubbed DSA, is based on a simple yet powerful observation, namely that population-level mean-field trajectories described by a system of PDE may also approximate individual-level times of infection and recovery. This idea gives rise to a certain non-Markovian agent-based model and provides an agent-level likelihood function for a random sample of infection and/or recovery times. Extensive numerical analyses on both synthetic and real epidemic data from the FMD in the United Kingdom and the COVID-19 in India show good accuracy and confirm method's versatility in likelihood-based parameter estimation. The accompanying software package gives prospective users a practical tool for modeling, analyzing and interpreting epidemic data with the help of the DSA approach.
△ Less
Submitted 20 February, 2022;
originally announced February 2022.
-
Motif-based mean-field approximation of interacting particles on clustered networks
Authors:
Kai Cui,
Wasiur R. KhudaBukhsh,
Heinz Koeppl
Abstract:
Interacting particles on graphs are routinely used to study magnetic behaviour in physics, disease spread in epidemiology, and opinion dynamics in social sciences. The literature on mean-field approximations of such systems for large graphs is limited to cluster-free graphs for which standard approximations based on degrees and pairs are often reasonably accurate. Here, we propose a motif-based me…
▽ More
Interacting particles on graphs are routinely used to study magnetic behaviour in physics, disease spread in epidemiology, and opinion dynamics in social sciences. The literature on mean-field approximations of such systems for large graphs is limited to cluster-free graphs for which standard approximations based on degrees and pairs are often reasonably accurate. Here, we propose a motif-based mean-field approximation that considers higher-order subgraph structures in large clustered graphs. Numerically, our equations agree with stochastic simulations where existing methods fail.
△ Less
Submitted 14 July, 2022; v1 submitted 13 January, 2022;
originally announced January 2022.
-
A Machine Learning Model for Nowcasting Epidemic Incidence
Authors:
Saumya Yashmohini Sahai,
Saket Gurukar,
Wasiur R. KhudaBukhsh,
Srinivasan Parthasarathy,
Grzegorz A. Rempala
Abstract:
Due to delay in reporting, the daily national and statewide COVID-19 incidence counts are often unreliable and need to be estimated from recent data. This process is known in economics as nowcasting. We describe in this paper a simple random forest statistical model for nowcasting the COVID - 19 daily new infection counts based on historic data along with a set of simple covariates, such as the cu…
▽ More
Due to delay in reporting, the daily national and statewide COVID-19 incidence counts are often unreliable and need to be estimated from recent data. This process is known in economics as nowcasting. We describe in this paper a simple random forest statistical model for nowcasting the COVID - 19 daily new infection counts based on historic data along with a set of simple covariates, such as the currently reported infection counts, day of the week, and time since first reporting. We apply the model to adjust the daily infection counts in Ohio, and show that the predictions from this simple data-driven method compare favorably both in quality and computational burden to those obtained from the state-of-the-art hierarchical Bayesian model employing a complex statistical algorithm.
△ Less
Submitted 5 April, 2021;
originally announced April 2021.
-
Incorporating age and delay into models for biophysical systems
Authors:
Wasiur R. KhudaBukhsh,
Hye-Won Kang,
Eben Kenah,
Grzegorz A. Rempala
Abstract:
In many biological systems, chemical reactions or changes in a physical state are assumed to occur instantaneously. For describing the dynamics of those systems, Markov models that require exponentially distributed inter-event times have been used widely. However, some biophysical processes such as gene transcription and translation are known to have a significant gap between the initiation and th…
▽ More
In many biological systems, chemical reactions or changes in a physical state are assumed to occur instantaneously. For describing the dynamics of those systems, Markov models that require exponentially distributed inter-event times have been used widely. However, some biophysical processes such as gene transcription and translation are known to have a significant gap between the initiation and the completion of the processes, which renders the usual assumption of exponential distribution untenable. In this paper, we consider relaxing this assumption by incorporating age-dependent random time delays into the system dynamics. We do so by constructing a measure-valued Markov process on a more abstract state space, which allows us to keep track of the "ages" of molecules participating in a chemical reaction.
We study the large-volume limit of such age-structured systems. We show that, when appropriately scaled, the stochastic system can be approximated by a system of Partial Differential Equations (PDEs) in the large-volume limit, as opposed to Ordinary Differential Equations (ODEs) in the classical theory. We show how the limiting PDE system can be used for the purpose of further model reductions and for devising efficient simulation algorithms. In order to describe the ideas, we use a simple transcription process as a running example. We, however, note that the methods developed in this paper apply to a wide class of biophysical systems.
△ Less
Submitted 2 July, 2020; v1 submitted 1 July, 2020;
originally announced July 2020.
-
Pairwise accelerated failure time regression models for infectious disease transmission in close-contact groups with external sources of infection
Authors:
Yushuf Sharker,
Zaynab Diallo,
Wasiur R. KhudaBukhsh,
Eben Kenah
Abstract:
Many important questions in infectious disease epidemiology involve the effects of covariates (e.g., age or vaccination status) on infectiousness and susceptibility, which can be measured in studies of transmission in households or other close-contact groups. Because the transmission of disease produces dependent outcomes, these questions are difficult or impossible to address using standard regre…
▽ More
Many important questions in infectious disease epidemiology involve the effects of covariates (e.g., age or vaccination status) on infectiousness and susceptibility, which can be measured in studies of transmission in households or other close-contact groups. Because the transmission of disease produces dependent outcomes, these questions are difficult or impossible to address using standard regression models from biostatistics. Pairwise survival analysis handles dependent outcomes by calculating likelihoods in terms of contact interval distributions in ordered pairs of individuals. The contact interval in the ordered pair ij is the time from the onset of infectiousness in i to infectious contact from i to j, where an infectious contact is sufficient to infect j if they are susceptible. Here, we introduce a pairwise accelerated failure time regression model for infectious disease transmission that allows the rate parameter of the contact interval distribution to depend on infectiousness covariates for i, susceptibility covariates for j, and pairwise covariates. This model can simultaneously handle internal infections (caused by transmission between individuals under observation) and external infections (caused by environmental or community sources of infection). In a simulation study, we show that these models produce valid point and interval estimates of parameters governing the contact interval distributions. We also explore the role of epidemiologic study design and the consequences of model misspecification. We use this regression model to analyze household data from Los Angeles County during the 2009 influenza A (H1N1) pandemic, where we find that the ability to account for external sources of infection is critical to estimating the effect of antiviral prophylaxis.
△ Less
Submitted 24 October, 2023; v1 submitted 6 January, 2019;
originally announced January 2019.
-
Survival Dynamical Systems for the Population-level Analysis of Epidemics
Authors:
Wasiur R. KhudaBukhsh,
Boseung Choi,
Eben Kenah,
Grzegorz A. Rempala
Abstract:
Motivated by the classical Susceptible-Infected-Recovered (SIR) epidemic models proposed by Kermack and Mckendrick, we consider a class of stochastic compartmental dynamical systems with a notion of partial ordering among the compartments. We call such systems unidirectional Mass Transfer Models (MTMs). We show that there is a natural way of interpreting a uni-directional MTM as a Survival Dynamic…
▽ More
Motivated by the classical Susceptible-Infected-Recovered (SIR) epidemic models proposed by Kermack and Mckendrick, we consider a class of stochastic compartmental dynamical systems with a notion of partial ordering among the compartments. We call such systems unidirectional Mass Transfer Models (MTMs). We show that there is a natural way of interpreting a uni-directional MTM as a Survival Dynamical System (SDS) that is described in terms of survival functions instead of population counts. This SDS interpretation allows us to employ tools from survival analysis to address various issues with data collection and statistical inference of unidirectional MTMs. In particular, we propose and numerically validate a statistical inference procedure based on SDS-likelihoods. We use the SIR model as a running example throughout the paper to illustrate the ideas.
△ Less
Submitted 2 January, 2019;
originally announced January 2019.
-
A Comprehensive Analysis of Swarming-based Live Streaming to Leverage Client Heterogeneity
Authors:
Wasiur R. KhudaBukhsh,
Julius Rückert,
Julian Wulfheide,
David Hausheer,
Heinz Koeppl
Abstract:
Due to missing IP multicast support on an Internet scale, over-the-top media streams are delivered with the help of overlays as used by content delivery networks and their peer-to-peer (P2P) extensions. In this context, mesh/pull-based swarming plays an important role either as pure streaming approach or in combination with tree/push mechanisms. However, the impact of realistic client populations…
▽ More
Due to missing IP multicast support on an Internet scale, over-the-top media streams are delivered with the help of overlays as used by content delivery networks and their peer-to-peer (P2P) extensions. In this context, mesh/pull-based swarming plays an important role either as pure streaming approach or in combination with tree/push mechanisms. However, the impact of realistic client populations with heterogeneous resources is not yet fully understood. In this technical report, we contribute to closing this gap by mathematically analysing the most basic scheduling mechanisms latest deadline first (LDF) and earliest deadline first (EDF) in a continuous time Markov chain framework and combining them into a simple, yet powerful, mixed strategy to leverage inherent differences in client resources. The main contributions are twofold: (1) a mathematical framework for swarming on random graphs is proposed with a focus on LDF and EDF strategies in heterogeneous scenarios; (2) a mixed strategy, named SchedMix, is proposed that leverages peer heterogeneity. The proposed strategy, SchedMix is shown to outperform the other two strategies using different abstractions: a mean-field theoretic analysis of buffer probabilities, simulations of a stochastic model on random graphs, and a full-stack implementation of a P2P streaming system.
△ Less
Submitted 29 December, 2018;
originally announced December 2018.
-
Bounds on the spectral radius of real-valued non-negative Kernels on measurable spaces
Authors:
Wasiur R. KhudaBukhsh,
Mark Sinzger,
Heinz Koeppl
Abstract:
In this short technical note, we extend a recently published result [Liao2017] on the Perron root (or the spectral radius) of non-negative matrices to real-valued non-negative kernels on an arbitrary measurable space $(\mathrm{E}, \mathcal{E})$. To be precise, for any real-valued non-negative kernel $K : \mathrm{E}\times \mathcal{E} \rightarrow \mathbb{R}$, we prove that the spectral radius…
▽ More
In this short technical note, we extend a recently published result [Liao2017] on the Perron root (or the spectral radius) of non-negative matrices to real-valued non-negative kernels on an arbitrary measurable space $(\mathrm{E}, \mathcal{E})$. To be precise, for any real-valued non-negative kernel $K : \mathrm{E}\times \mathcal{E} \rightarrow \mathbb{R}$, we prove that the spectral radius $ρ(K)$ of $K$ satisfies $$
\inf_{x \in \mathrm{E} } \frac{ \mathcal{R} K \cdotp L (x) }{ \mathcal{R} L (x) } \le ρ(K) \le \sup_{x \in \mathrm{E} } \frac{ \mathcal{R} K\cdotp L (x) }{ \mathcal{R} L (x) }, $$ where $L$ is an arbitrary Kernel on $(\mathrm{E}, \mathcal{E})$, which is integrable with respect to the left eigenmeasure of $K$ and satisfies $ \mathcal{R} L (x) >0 $ for all $x \in \mathrm{E}$, and the operator $\mathcal{R}$ is defined by $\mathcal{R}L (x) :=\int_{\mathrm{E}} L(x, \mathrm{d}y) $.
△ Less
Submitted 31 August, 2018; v1 submitted 1 August, 2018;
originally announced August 2018.
-
Approximate lumpability for Markovian agent-based models using local symmetries
Authors:
Wasiur R. KhudaBukhsh,
Arnab Auddy,
Yann Disser,
Heinz Koeppl
Abstract:
We study a Markovian agent-based model (MABM) in this paper. Each agent is endowed with a local state that changes over time as the agent interacts with its neighbours. The neighbourhood structure is given by a graph. In a recent paper [Simon et al. 2011], the authors used the automorphisms of the underlying graph to generate a lumpable partition of the joint state space ensuring Markovianness of…
▽ More
We study a Markovian agent-based model (MABM) in this paper. Each agent is endowed with a local state that changes over time as the agent interacts with its neighbours. The neighbourhood structure is given by a graph. In a recent paper [Simon et al. 2011], the authors used the automorphisms of the underlying graph to generate a lumpable partition of the joint state space ensuring Markovianness of the lumped process for binary dynamics. However, many large random graphs tend to become asymmetric rendering the automorphism-based lumping approach ineffective as a tool of model reduction. In order to mitigate this problem, we propose a lumping method based on a notion of local symmetry, which compares only local neighbourhoods of vertices. Since local symmetry only ensures approximate lumpability, we quantify the approximation error by means of Kullback-Leibler divergence rate between the original Markov chain and a lifted Markov chain. We prove the approximation error decreases monotonically. The connections to fibrations of graphs are also discussed.
△ Less
Submitted 3 April, 2018;
originally announced April 2018.
-
Collaborative Uploading in Heterogeneous Networks: Optimal and Adaptive Strategies
Authors:
Wasiur R. KhudaBukhsh,
Bastian Alt,
Sounak Kar,
Amr Rizk,
Heinz Koeppl
Abstract:
Collaborative uploading describes a type of crowdsourcing scenario in networked environments where a device utilizes multiple paths over neighboring devices to upload content to a centralized processing entity such as a cloud service. Intermediate devices may aggregate and preprocess this data stream. Such scenarios arise in the composition and aggregation of information, e.g., from smartphones or…
▽ More
Collaborative uploading describes a type of crowdsourcing scenario in networked environments where a device utilizes multiple paths over neighboring devices to upload content to a centralized processing entity such as a cloud service. Intermediate devices may aggregate and preprocess this data stream. Such scenarios arise in the composition and aggregation of information, e.g., from smartphones or sensors. We use a queuing theoretic description of the collaborative uploading scenario, capturing the ability to split data into chunks that are then transmitted over multiple paths, and finally merged at the destination. We analyze replication and allocation strategies that control the mapping of data to paths and provide closed-form expressions that pinpoint the optimal strategy given a description of the paths' service distributions. Finally, we provide an online path-aware adaptation of the allocation strategy that uses statistical inference to sequentially minimize the expected waiting time for the uploaded data. Numerical results show the effectiveness of the adaptive approach compared to the proportional allocation and a variant of the join-the-shortest-queue allocation, especially for bursty path conditions.
△ Less
Submitted 19 December, 2017; v1 submitted 12 December, 2017;
originally announced December 2017.
-
Quasi-steady-state approximations derived from the stochastic model of enzyme kinetics
Authors:
Hye-Won Kang,
Wasiur R. KhudaBukhsh,
Heinz Koeppl,
Grzegorz A. Rempała
Abstract:
In this paper we derive several quasi steady-state approximations (QSSAs) to the stochastic reaction network describing the Michaelis-Menten enzyme kinetics. We show how the different assumptions about chemical species abundance and reaction rates lead to the standard QSSA (sQSSA), the total QSSA (tQSSA), and the reverse QSSA (rQSSA) approximations. These three QSSAs have been widely studied in th…
▽ More
In this paper we derive several quasi steady-state approximations (QSSAs) to the stochastic reaction network describing the Michaelis-Menten enzyme kinetics. We show how the different assumptions about chemical species abundance and reaction rates lead to the standard QSSA (sQSSA), the total QSSA (tQSSA), and the reverse QSSA (rQSSA) approximations. These three QSSAs have been widely studied in the literature in deterministic ordinary differential equation (ODE) settings and several sets of conditions for their validity have been proposed. By using multiscaling techniques introduced in Kang (and Kurtz 2013) and Ball et al. (2006) we show that these conditions for deterministic QSSAs largely agree with the ones for QSSAs in the large volume limits of the underlying stochastic enzyme kinetic network.
△ Less
Submitted 7 November, 2017;
originally announced November 2017.
-
Functional Central Limit Theorem For Susceptible-Infected Process On Configuration Model Graphs
Authors:
Wasiur R. KhudaBukhsh,
Casper Woroszylo,
Grzegorz A. Rempała,
Heinz Koeppl
Abstract:
We study a stochastic compartmental susceptible-infected (SI) epidemic process on a configuration model random graph with a given degree distribution over a finite time interval $[0,T],$ for some $ T>0$. In this setting, we split the population of graph nodes into two compartments, namely, $S$ and $I$, denoting the susceptible and infected nodes, respectively. In addition to the sizes of these two…
▽ More
We study a stochastic compartmental susceptible-infected (SI) epidemic process on a configuration model random graph with a given degree distribution over a finite time interval $[0,T],$ for some $ T>0$. In this setting, we split the population of graph nodes into two compartments, namely, $S$ and $I$, denoting the susceptible and infected nodes, respectively. In addition to the sizes of these two compartments, we study counts of $SI$-edges (those connecting a susceptible and an infected node) and $SS$-edges (those connecting two susceptible nodes). We describe the dynamical process in terms of these counts and present a functional central limit theorem (FCLT) for them, a scaling limit of the dynamical process as $n$, the number of nodes in the random graph, grows to infinity. To be precise, we show that these counts, when appropriately scaled, converge weakly to a continuous Gaussian vector martingale process the usual Skorohod space of real 3-dimensional vector-valued \cadlag\, functions on $[0,T]$ endowed with the Skorohod topology. We assume certain technical requirements for this purpose. We discuss applications of our FCLT in percolation theory (from a non-equilibrium statistical mechanics point of view), and in computer science in the context of spread of computer viruses. We also provide simulation results for some common degree distributions.
△ Less
Submitted 14 October, 2021; v1 submitted 18 March, 2017;
originally announced March 2017.
-
A Generalized Performance Evaluation Framework for Parallel Systems with Output Synchronization
Authors:
Wasiur R. KhudaBukhsh,
Sounak Kar,
Amr Rizk,
Heinz Koeppl
Abstract:
Frameworks, such as MapReduce and Hadoop are abundant nowadays. They seek to reap benefits of parallelization, albeit subject to a synchronization constraint at the output. Fork-Join (FJ) queuing models are used to analyze such systems. Arriving jobs are split into tasks each of which is mapped to exactly one server. A job leaves the system when all of its tasks are executed.
As a metric of perf…
▽ More
Frameworks, such as MapReduce and Hadoop are abundant nowadays. They seek to reap benefits of parallelization, albeit subject to a synchronization constraint at the output. Fork-Join (FJ) queuing models are used to analyze such systems. Arriving jobs are split into tasks each of which is mapped to exactly one server. A job leaves the system when all of its tasks are executed.
As a metric of performance, we consider waiting times for both work-conserving and non-work conserving server systems under a mathematical set-up general enough to take into account possible phase-type behavior of the servers, and as suggested by recent evidences, bursty arrivals.
To this end, we present a Markov-additive process framework for an FJ system and provide computable bounds on tail probabilities of steady-state waiting times, for both types of servers separately. We apply our results to three scenarios, namely, non-renewal (Markov-modulated) arrivals, servers showing phase-type behavior, and Markov-modulated arrivals and services. We compare our bounds against estimates obtained through simulations and also provide a theoretical conceptualization of provisions in FJ systems. Finally, we calibrate our model with real data traces, and illustrate how our bounds can be used to devise provisions.
△ Less
Submitted 16 December, 2016;
originally announced December 2016.
-
Optimizing Stochastic Scheduling in Fork-Join Queueing Models: Bounds and Applications
Authors:
Wasiur R. KhudaBukhsh,
Amr Rizk,
Alexander Frömmgen,
Heinz Koeppl
Abstract:
Fork-Join (FJ) queueing models capture the dynamics of system parallelization under synchronization constraints, for example, for applications such as MapReduce, multipath transmission and RAID systems. Arriving jobs are first split into tasks and mapped to servers for execution, such that a job can only leave the system when all of its tasks are executed.
In this paper, we provide computable st…
▽ More
Fork-Join (FJ) queueing models capture the dynamics of system parallelization under synchronization constraints, for example, for applications such as MapReduce, multipath transmission and RAID systems. Arriving jobs are first split into tasks and mapped to servers for execution, such that a job can only leave the system when all of its tasks are executed.
In this paper, we provide computable stochastic bounds for the waiting and response time distributions for heterogeneous FJ systems under general parallelization benefit. Our main contribution is a generalized mathematical framework for probabilistic server scheduling strategies that are essentially characterized by a probability distribution over the number of utilized servers, and the optimization thereof. We highlight the trade-off between the scaling benefit due to parallelization and the FJ inherent synchronization penalty. Further, we provide optimal scheduling strategies for arbitrary scaling regimes that map to different levels of parallelization benefit. One notable insight obtained from our results is that different applications with varying parallelization benefits result in different optimal strategies. Finally, we complement our analytical results by applying them to various applications showing the optimality of the proposed scheduling strategies.
△ Less
Submitted 2 February, 2017; v1 submitted 16 December, 2016;
originally announced December 2016.
-
Inverse Reinforcement Learning in Swarm Systems
Authors:
Adrian Šošić,
Wasiur R. KhudaBukhsh,
Abdelhak M. Zoubir,
Heinz Koeppl
Abstract:
Inverse reinforcement learning (IRL) has become a useful tool for learning behavioral models from demonstration data. However, IRL remains mostly unexplored for multi-agent systems. In this paper, we show how the principle of IRL can be extended to homogeneous large-scale problems, inspired by the collective swarming behavior of natural systems. In particular, we make the following contributions t…
▽ More
Inverse reinforcement learning (IRL) has become a useful tool for learning behavioral models from demonstration data. However, IRL remains mostly unexplored for multi-agent systems. In this paper, we show how the principle of IRL can be extended to homogeneous large-scale problems, inspired by the collective swarming behavior of natural systems. In particular, we make the following contributions to the field: 1) We introduce the swarMDP framework, a sub-class of decentralized partially observable Markov decision processes endowed with a swarm characterization. 2) Exploiting the inherent homogeneity of this framework, we reduce the resulting multi-agent IRL problem to a single-agent one by proving that the agent-specific value functions in this model coincide. 3) To solve the corresponding control problem, we propose a novel heterogeneous learning scheme that is particularly tailored to the swarm setting. Results on two example systems demonstrate that our framework is able to produce meaningful local reward models from which we can replicate the observed global system dynamics.
△ Less
Submitted 24 March, 2017; v1 submitted 17 February, 2016;
originally announced February 2016.
