Hard vs. soft bounds in probabilistic robustness analysis and generalized source coding and optimal web layout design

Part I. By extending the structured singular value mu framework to allow for probabilistic descriptions of uncertainty, probabilistic mu is defined to characterize the probability distribution of some performance function. Computation of probabilistic mu is even more complex than standard mu computation, a well-known NP-hard problem. In particular, providing sufficiently tight bounds in the tail of the distribution is extremely difficult. This thesis introduces three different methods for computing a hard upper bound on probabilistic mu, whose tightness can be tested by comparison with the soft bound provided by Monte-Carlo simulations. At the same time, the efficiency of the soft bounds can be significantly improved with the information from the hard bound computation, especially in the case of estimating the probability of extremely rare events. The performance of the three algorithms proposed is demonstrated and compared through numerical experiment results.;Part II. This thesis provides a natural and plausible explanation for the origin of heavy tails in Web traffic by introducing a series of simplified models for optimal Web layout design with varying levels of realism and analytic tractability. The basic approach is to view the minimization of the average file download time as a generalization of standard source coding for data compression, but with the design of the Web layout rather than the codewords. The results, however, are quite different from standard source coding. Analysis of a simple one-dimensional model and simulations on more complex graph-based models all produce power law tails in the resulting size distributions of the files transferred from the Web sites with a wide variety of assumptions on user behavior. This verifies our conjecture that heavy-tailed distributions result naturally from the tradeoff between the design objective and limited resources, and suggests a methodology for aiding in the design of high-throughput Web sites.