| Random processes occur in many disciplines, ranging from physics to finance. Sometimes randomness is detrimental, sometimes it is helpful, and sometimes it is both. This thesis focuses on the use of randomness to optimize a set of dynamical processes—processes that we would like to complete quickly, but whose running time is a random variable. We show how to construct strategies to minimize the waiting time and its variance for three examples: Internet downloads, randomized algorithms and quantum computing.; In particular, we design restart strategies, in which a process is interrupted and restarted after a predetermined time. Restart strategies are shown to be optimal within a general class of strategies, and we determine the conditions under which they will on average outperform the original process.; We study the Internet congestion problem in more detail, to analyze the effect the use of such strategies has on the congestion itself. Provided a good implementation is available, restart strategies change the equilibrium but remain optimal.; We also generalize restart strategies to the cases when the properties of the original process are unknown, when the process is not stationary, and when multiple algorithms or multiple processors are available. |
