Applications and Analysis of Probabilistic Techniques

Prasad V. Tetali


The thesis illustrates the strength of randomness by applying some recent probabilistic techniques to solve problems in number theory, graph theory and computer science.

The first part of the thesis is concerned with random construction of integer sequences with certain additive properties. A set of natural numbers is called an asymptotic basis of order k, if every number (sufficiently large) can be expressed as a sum of k distinct numbers from the set. We prove that for every fixed k, there exists an asymptotic basis of order k such that the number of representations of n is $\Theta (\log n)$. The case k=2 was proved in 1956 by Paul Erdos.

The second part deals with analysis of random walks on graphs. Random walks on graphs have been known to have interesting analogies in electrical networks. A precise characterization of effective resistance in electrical networks is provided in this thesis in terms of random walks on the underlying graphs. The interpretation of effective resistance yields interesting new results and new proofs for some known results. The main result here is an exact formula for the hitting time between two vertices in terms of the effective resistances in the network, settling an open question. This is much in the spirit of the commute time result by Ashok Chandra et al.