Poster Session and Refreshments

Thursday, June 25, 2015 - 5:15pm - 6:30pm
Lind 400
  • Stochastic Integral Equations for Walsh Semimartingales
    Tomoyuki Ichiba (University of California)
    We construct a class of planar semimartingales which includes the Walsh Brownian motion as a special case, and derive stochastic integral equations and a change-of-variable formula for these so-called Walsh semimartingales. Through the study of appropriate martingale problems, we examine uniqueness of the probability distribution for such processes in Markovian settings, and study some examples. This is joint work with I. Karatzas, V. Prokaj and M. Yan.
  • Hydrodynamic Limit of Order Book Dynamics
    Xuefeng Gao (Chinese University of Hong Kong)
    Motivated by optimal trade execution, we study the temporal evolution of the shape of a limit order book over a time horizon that is large compared with the length of time between order book events, with the aim of approximating the transient distribution of the shape. Relying on the stochastic order book model in Cont et al. (2010), we show that when the tick size approaches zero, a pair of measure-valued processes representing the sell-side shape and buy-side shape of an order book converges to a pair of deterministic measure-valued processes in a certain sense. Moreover, we describe the density profile of the
    limiting processes through ordinary differential equations which can be solved explicitly. We also perform experiments to test our limiting model against data. The empirical results suggest that the approximation is effective. This is joint work with Jim Dai, Ton Dieker and Shijie Deng.
  • Determining the Validity of Hill Functions in Stochastic Simulations
    Jae Kyoung Kim (The Ohio State University)
    The non-elementary reaction functions (e.g. Michaelis-Menten or Hill functions) are used to reduce the model of biochemical network. Such deterministic reductions are frequently a basis for heuristic stochastic models in which non-elementary reaction functions are used as propensities of Gillespie algorithm. Despite their popularity, it remains unclear when such stochastic reductions are valid. Here, we first identify the validity condition for using non-elementary reaction functions for the stochastic simulations. This provides a simple and computationally inexpensive way to test the accuracy of reduced stochastic model.
  • Diffusion Approximation for Efficiency-driven Queues: A Space-time Scaling Approach
    Shuangchi He (National University of Singapore)
    Motivated by call center practice, we propose a tractable model for GI/GI/n+GI queues in the efficiency-driven (ED) regime. We use a one-dimensional diffusion process to approximate the virtual waiting time process that is scaled in both space and time, with the number of servers and the mean patience time as the respective scaling factors. Using this diffusion model, we obtain the steady-state distributions of the virtual waiting time and the queue length, which in turn yield approximate formulas for performance metrics such as the service level and the effective abandonment fraction. The resulting formulas are generally accurate when the mean patience time is several times longer than the mean service time. To justify the diffusion model, we formulate an asymptotic framework by considering a sequence of queues, in which both the number of servers and the mean patience time go to infinity. We prove that the space-time scaled virtual waiting time process converges in distribution to the diffusion process. A fundamental result for proving the diffusion limit is a functional central limit theorem (FCLT) for the superposition of time-scaled renewal processes. We prove that the superposition of $n$ independent, identically distributed stationary renewal processes, after being centered, scaled, and normalized in both space and time, converges in distribution to a Brownian motion as $n$ goes large.
  • Fluid Models for FCFS Parallel Skilled Based Service Systems
    Gideon Weiss (Haifa University)
    In a skilled based parallel service system there are several types of customers and several type of servers and a bipartite compatibility graph between them. Under FCFS all customers wait in one queue and servers pick the longest waiting compatible customer. A Brownian control heuristic for this type of model was suggested by Harrison and Lopez 1999, and a fluid model for this type of system under FCFS was partially analyzed by Talreja and Whitt 2008. When arrivals are Poisson and service durations are exponentially distributed and depend only on the type of server a complete analysis was presented by Adan and Weiss 2014. In the current paper we extend some of the results to renewal arrivals and general service times by analyzing the fluid limit models of this system. We obtain general fluid trajectories for some models and for more general models we relate the trajectories to the matching rates of compatible type server customer pairs. We list several open questions for this model.
  • Pathwise Differentiability of Semimartingale Reflected Brownian Motion in Convex Polyhedrons
    David Lipshutz (Brown University)
    We consider the pathwise differentiability of semimartingale obliquely reflected Brownian motions (SRBMs) with state dependent drifts in simple convex polyhedrons. In particular, we consider derivatives with respect to input parameters that determine the initial condition and the drift of the SRBMs. We characterize these derivatives as solutions to time-dependent Skorokhod type problems associated with the SRBMs. We use these results to characterize derivatives of stochastic flows for SRBMs and obtain a Bismut-Elworthy type formula. As a second application, we obtain results on the sensitivity of SRBMs to small perturbations of the drift function.

    This is joint work with Kavita Ramanan.
  • Asymptotically Optimal Control of N-Systems with Many-Server and H_2^* Service Times
    Keguo Huang (Iowa State University)
    We are seeking an optimal control policy for a queueing system, which is known as N-system, under the Halfin-Whitt regime. An N-system has two customer classes and two server pools, where servers from one pool can serve both customer classes, while servers from the other pool can only serve one customer class. Also, impatient customers will renege from his queue if the waiting time exceeds his patient time. The service time distribution is only pool-dependent, not class-dependent, and it follows a special case of hyper-exponential distributions, $H^*_2$ distribution. A static priority policy $\pi^*$ is proposed, and this policy is shown to be asymptotically optimal in minimizing the total cost caused by queue length growth and customer abandonment.

    This is joint work with Prof. Arka P Ghosh.
  • Analysis and Design of Genetic Control Circuits for Metabolism

    Cell survival depends on the interaction between biochemical networks that sense and process environmental cues. In particular, the interplay between genetic networks and metabolic networks allows cells to switch pathways on or off in response to environmental conditions. Cells implement this control strategy with intricate arrays of feedback loops between metabolites and gene expression. In this talk I will give an overview of our recent progress on the analysis and design of genetic feedback circuits for metabolism. We use novel theoretical analyses to learn how the feedback architecture and parameters shape the long-term dynamics of a pathway. We use these results to understand the function of natural regulatory systems, as well as to design control circuits for next-generation metabolic engineering and to quantify the propagation of intracellular noise between gene expression and metabolic activity.


    Oyarzún, Chaves & Hoff-Hoffmeyer-Zlotnik, Multistability and oscillations in genetic control of metabolism, Journal of Theoretical Biology, 295, 2012.

    Oyarzún, Lugagne & Stan, Noise propagation in synthetic gene circuits for metabolic control, ACS Synthetic Biology, 4(2), 2015.

    Weisse, Oyarzún, Danos & Swain, Mechanistic links between cellular trade-offs, gene expression, and growth. PNAS, 112(9), 2015.
  • Finite Point Configurations and Fourier Analysis
    Krystal Taylor
    We study the existence of certain geometric congurations in sub-
    sets of Euclidean space. In particular, we establish that a set with
    sufficient structure contains an arbitrarily long chain with vertices
    in the set and preassigned admissible gaps. A \(k\)-chain in \(E \subset \mathbb{R}^d\) with
    gaps \( \left\{ t_i \right\}^k_{i=1} \) is a sequence
    $$ \left\{ x^1, x^2, \dots, x^{k+1}, x^j, \subset E ; \left x^{i+1} - x^{i} \right = t_i; 1 \leq i \leq k \right\} . $$

    In order to prove this result, we establish \( L^p(\mu) \rightarrow L^q(\nu) \) mapping
    properties of the convolution operator \( T_\lambda f(x) = \lambda * (f\mu)(x) \); where \(\lambda\)
    is a tempered distribution, and \(\mu\) and \(\nu\) are compactly supported measures satisfying the
    growth bounds \( \mu(B(x, r)) \leq Cr^{s_\mu} \) and \( \nu(B(x,r)) \leq Cr^{s_\nu} \)
  • Steady State Approximation of Generalized Jackson Networks: A Generator Approach
    Anton Braverman (Cornell University)
    Diffusion approximations of stochastic systems are commonly justified by heavy-traffic limit theorems for stochastic processes. However, these limit theorems do not justify steady-state approximations, as process level convergence does not imply convergence of stationary distributions. Gamarnik and Zeevi (2006) were the first to justify it for the queue length process of a generalized Jackson network (GJN).

    Their paper has inspired many researchers to study these types of problems in the last 10 years. Based on process level convergence, they justify limit-interchange, which is commonly done by showing that the sequence of stationary distributions is tight. This step requires significant effort to produce a suitable Lyapunov function and must be done on a case-by-case basis.

    We propose a new approach, which is applicable for various queueing systems that can be represented as Markov processes consisting of 'core' and 'background' variables. The diffusion process approximates only the core variables, with the background variables collapsing in heavy-traffic. We focus on the GJN, where the core process is the queue length process and the background variables are the residual inter-arrival and service times. Our approach starts with the Basic Adjoint Relationship (BAR) for the pre-limit Markov processes. A key step in our approach is a careful choice of test function for the BAR, which results in state space collapse. Our approach also requires the tightness of the prelimit stationary distributions. We verify tightness without using Lyapunov functions under a general framework whenever the limiting process is a semimartingale reflecting Brownian motion (SRBM) whose reflection matrix is an M-matrix.

    Joint work with J.G. Dai and Masakiyo Miyazawa.
  • Necktie knots, formal languages and network security

    A chore for some, space for personal expression for others, the necktie knot used to have very few specific knots in widespread use. In their 1999 paper, Fink & Mao Designing tie knots by random walks. Nature 398, no. 6722 (1999): 31-32) list all possible ways to tie a necktie. They limit their enumeration task by focusing on knots that present a flat front just like all the classical tie knots. This way they established a list of 85 possible tie knots.

    Tie knots with intricate patterns of the necktie winding into symmetric but no longer at front displays have emerged in the past decade, introduced by the movie Matrix Reloaded and recreated hobbyists. These tie knots are tied with the narrow end of the tie, wrapping it to create patterns on the surface of the tie knot. As such these knots are not covered by the listing proposed by Fink & Mao.

    With a team of collaborators I have extended the listing by Fink and Mao to cover these new tie knots. While doing this we have been able to determine the computational complexity classes of the grammar that describes tie knots.

    The formal language techniques that help us analyze the tie knot grammars are used in contemporary security research: a large class of security problems online emerge from different implementations of a communications protocol disagreeing on the actual grammar used. We will talk about the connections between the language techniques for tie knots and those that help us analyze security.