Theses Doctoral

# Topics in Simulation: Random Graphs and Emergency Medical Services

Simulation is a powerful technique to study complex problems and systems. This thesis explores two different problems. Part 1 (Chapters 2 and 3) focuses on the theory and practice of the problem of simulating graphs with a prescribed degree sequence. Part 2 (Chapter 4) focuses on how simulation can be useful to assess policy changes in emergency medical services (EMS) systems. In particular, and partially motivated by the COVID-19 pandemic, we build a simulation model based on New York City’s EMS system and use it to assess a change in its hospital transport policy.

In Chapter 2, we study the problem of sampling uniformly from discrete or continuous product sets subject to linear constraints. This family of problems includes sampling weighted bipartite, directed, and undirected graphs with given degree sequences. We analyze two candidate distributions for sampling from the target set. The first one maximizes entropy subject to satisfying the constraints in expectation. The second one is the distribution from an exponential family that maximizes the minimum probability over the target set. Our main result gives a condition under which the maximum entropy and the max-min distributions coincide. For the discrete case, we also develop a sequential procedure that updates the maximum entropy distribution after some components have been sampled. This procedure sacrifices the uniformity of the samples in exchange for always sampling a valid point in the target set. We show that all points in the target set are sampled with positive probability, and we find a lower bound for that probability. To address the loss of uniformity, we use importance sampling weights. The quality of these weights is affected by the order in which the components are simulated. We propose an adaptive rule for this order to reduce the skewness of the weights of the sequential algorithm. We also present a monotonicity property of the max-min probability.

In Chapter 3, we leverage the general results obtained in the previous chapter and apply them to the particular case of simulating bipartite or directed graphs with given degree sequences. This problem is also equivalent to the one of sampling 0–1 matrices with fixed row and column sums. In particular, the structure of the graph problem allows for a simple iterative algorithm to find the maximum entropy distribution. The sequential algorithm described previously also simplifies in this setting, and we use it in an example of an inter-bank network. In additional numerical examples, we confirm that the adaptive rule, proposed in the previous chapter, does improve the importance sampling weights of the sequential algorithm.

## Files

• LelodeLarreaAndrade_columbia_0054D_16770.pdf application/pdf 1.45 MB Download File