Thresholds in semi-random processes and graph embeddings

A stochastic process consists of a sequence of steps where a new random input is provided at every step. Stochastic processes are central in the study of probability theory and describe many natural phenomena in the physical world. However, due to the unsupervised nature of most stochastic processes, it often turns out that introducing a deterministic influence (for example, introducing an observer) could drastically improve the properties of the outcome and make it more suitable for given practical purposes. The aim of the current project is to study instances of stochastic processes controlled by an observer. More concretely, the project aims to develop several natural (combinatorial and geometric) variations of the well-studied power of two choices paradigm described as follows. An observer is given initially empty bins. At every step, two uniformly random bins are proposed to them. The observer is then allowed to throw a ball in one of the two bins. As it turns out, the observer manages to reduce significantly the maximum load of a bin after steps compared to the purely random (unsupervised) setting. This process is a simplified stochastic model in the field of load balancing whose practical applications include parallel computing and task scheduling.