Ballot theorems and the heights of trees

A ballot theorem is a theorem that yields information about the conditional probability that a random walk stays above its mean, given its value St after some specified amount of time t. In the first part of this thesis, ballot theorems are proved for all walks whose steps consist of independent, identically distributed random variables that are in the range of attraction of the normal distribution. With a mild assumption on the moments of the steps, the results are strengthened; the latter results are shown to be within a constant factor of optimal when the value of the random walk at time t is of order t . Farther results are proved for random walks whose value after time t is of order O(t).In the second part of the thesis, two questions about the heights of random trees are studied. The random trees that are studied are of interest from both a purely probabilistic, and an algorithmic perspective. It turns out that in two seemingly very distinct settings, the height of a random tree turns out to be closely linked to the behavior of a random walk, in particular to the probability that a random walk stays above its mean. The tools developed in the first part of the thesis, together with additional results, are then used to derive information about the moments of the height of these random trees. We also demonstrate that this information can be used to bound the moments of the minima of certain branching random walks