Probability: Algorithms, Stochastic Analysis, & Applications Part 2

Speaker(s)

• Cecilia Holmgren (University of Cambridge)
• Manuel Lladser (University of Colorado, Boulder)
• Ravi Kalpathy (George Washington University)
• Jeffrey Gaither (Purdue University)

Description

The theory of probability and stochastic processes is as diverse as there are ways to apply it. Probability is at the core of all models of uncertainty, while stochastic processes include the additional component of time evolution for phenomena which would otherwise seem hopelessly unpredictable. A hallmark of continuous-time stochastic evolutions is the erratic character of their paths. A recent revolutionary development in this respect is the study of "rough paths", at the confines of functional analysis and probability, while more classical treatments of such models, based on Brownian motion and semi-martingales, continue to be widely used, and discrete probability models present a distinct set of challenges and opportunities. This Session will bring together early-career and internationally recognized experts to explore how these fruitful tools might be applied to a variety of topics in areas outside of probability, including engineering questions in applied control theory, stochastic PDEs in large-scale fluid dynamics such as global circulation and climate models, and the analysis of algorithms in computational complexity. 

Schedule

Sun, June 24 - Location: STEW 314

Time	Speaker	Title
8:30-9:25AM	Cecilia Holmgren	The total path length of split trees
	Abstract: We consider the model of random trees introduced by Devroye [SIAM J Comput 28, 409—432, 1998]. The model encompasses many important randomized algorithms and data structures. The pieces of data (items) are stored in a randomized fashion in the nodes of a tree. The total path length (sum of depths of the items) is a natural measure of the efficiency of the algorithm/data structure. Using renewal theory, we prove convergence in distribution of the total path length towards a distribution characterized uniquely by a fixed point equation. Our result covers, using a unified approach, many data structures such as binary search trees, m-ary search trees, quad trees, median-of-(2k+1) trees, and simplex trees.
9:30-9:55AM	Manuel Lladser	Estimation of dissimilarity in urn models
	Abstract: Consider two urns, urn-x and urn-y, each composed by colored balls. We define the (expected) dissimilarity of urn-x relative to k-draws from urn-y as the probability that the color of a random ball from urn-x is not observed in k random draws from urn-y. Using the theory of U-statistics, we can estimate this quantity in the non-parametric case via a uniformly minimum variance unbiassed estimator over a range for k determined by the sample size from urn-y. Furthermore, we can provide uniformly consistent estimates of the variance of our estimator via a jackknife approach. Although our estimator of dissimilarity exposes a non-Markovian behavior when applied sequentially over k, in non-pathological configurations, we can show uniform convergence in probability as well as approximately Gaussian marginal distributions when the sample sizes from each urn tend to infinity. Our analysis is motivated by the challenging problem allocating in a somewhat optimal manner samples among an ensemble of various microbial environments (each represented as an urn) so as to better understand what is unique and shared by the environments in the ensemble. Due to the wide generality of our urn model, however, other applications are foreseeable. For instance, each urn could represent a random RNA pool and each colored ball a possible solution to a particular binding site problem over that pool. This research is in collaboration with J. Hampton.
10:00-10:30AM	Break
10:30-10:55	Ravi Kalpathy	Perpetuities in Fair Leader Election Algorithms
	Abstract: We consider a broad class of fair leader election algorithms and we study the overall cost of the algorithm and the duration or equivalently the number of rounds a randomly selected contestant stays in the contest. We obtain sufficient conditions for the limiting distribution (after suitable normalization) to be a perpetuity. The contraction method in the Wasserstein metric space is used to show that the limit approaches a fixed-point solution of a perpetuity distributional equation.
11:00-11:25AM	Jeffrey Gaither	2-protected Nodes in Tries and Suffix Trees
	Abstract: We investigate the asymptotic proportions of 2-protected nodes (nodes that are at least two edges away from every leaf) in binary retrieval trees (tries) and binary suffix trees. We also consider the variance of the number of 2-protected nodes in a binary trie. We employ methods from probability, combinatorics and complex analysis, and cover both the uniform and non-uniform cases.
11:30-11:55	Group Discussion