| An algorithm can be defined as a set of computational steps that transform the input to the output. In the analysis of the efficiency for algorithms, usually upper bounds on the running time are being considered as the criteria. Probabilistic analysis of algorithms is the method of studying how algorithms perform when the input is taken from well defined probabilistic space. In design of algorithms to solve many important problems, randomized algorithms are either the fastest, or the simplest algorithms, and often both. Hence, randomization becomes an inevitable part of modern algorithm design.; In this study, different probabilistic methods and their usefulness will be investigated. Useful and well known bounds such as Chernoff bounds and Ramsey theory, first and second moment methods and Lovasz local lemma (LLL) are considered to analyze the algorithmic and combinatorial problems of interest. Matrix multiplication and randomized min-cut algorithms will be considered to show the power of these methods.; Reviewing the properties of Markov chains and random walks on random graphs, and electrical networks models for random walks on random graphs, we analyze and obtain some of the parameters which are important in computer networks, communications and signal detection. Pure and accelerated random search algorithms and some of their convergence properties will be considered in the last section.; We'll see that the gains in random algorithms come at a price that the answers may have some positive probability of being incorrect. Although it may seem unusual to design an algorithm that may be incorrect, if the probability of error is sufficiently small then the improvement in speed or memory requirements may well be worthwhile. |
