top of page

Prof. Andrew Wade

Wednesday 20th November 2019

One plus one is typically at most two: subadditivity and probability

Subadditivity is a simple property of the growth of sequences of real numbers which can be used to deduce existence of various limits. We will look at some simple applications of subadditivity in various contexts, and then turn to its role in some probability and counting problems, such as bin packing and self-avoiding walk. Two beautiful applications of subadditivity ideas in probability are the problem of long increasing subsequences of a random permutation (where much progress has been made recently) and the random travelling salesman problem, concerning the length of the shortest path that visits a large number of randomly distributed cities, where some of the main problems still resist mathematical analysis.

bottom of page