The size of the largest common subtree (maximum agreement subtree) of two independent uniform random binary trees on $n$ leaves is known to be between orders $n^{1/8}$ and $n^{1/2}$. By a construction based on recursive splitting and analyzable by standard “stochastic fragmentation" methods, we improve the lower bound to order $n^\beta$ for $\beta = \frac{\sqrt{3} - 1}{2} = 0.366$. Improving the upper bound remains a challenging problem.

A very simple example of an algorithmic problem solvable by dynamic programming is to maximize, over $A\subseteq\{1,2,\ldots,n\}$, the objective function $|A|-\sum_i\xi_i{\rm1\hspace{-0.90ex}1}(i\in A,i+1\in A)$ for given $\xi_i>0$. This problem, with random $(\xi_i)$, provides a test example for studying the relationship between optimal and near-optimal solutions of combinatorial optimization problems. We show that, amongst solutions differing from the optimal solution in a small proportion $\delta$ of places, we can find near-optimal solutions whose objective function value differs from the optimum by a factor of order $\delta^2$ but not of smaller order. We conjecture this relationship holds widely in the context of dynamic programming over random data, and Monte Carlo simulations for the Kauffman–Levin NK model are consistent with the conjecture. This work is a technical contribution to a broad program initiated in [D. J. Aldous and A. G. Percus, Proc. Natl. Acad. Sci. USA, 100 (2003), pp. 11211–11215] of relating such scaling exponents to the algorithmic difficulty of optimization problems.

We can view certain randomized optimization algorithms as rules for randomly moving a particle around in a state space; each state might correspond to a distinct solution to the optimization problem, or more generally, the state space might express some other structure underlying the optimization algorithm. In this setting, a general paradigm for designing heuristics is to run several simulations of the algorithm simultaneously, and every so often classify the particles as "doing well" or "doing badly", and move each particle that is "doing badly" to the position of one that is "doing well". In this paper, we give a rigorous analysis of such a "go with the winners" scheme in the concrete setting of searching for a deep leaf in a tree. There are two relevant parameters of the tree: its depth d, and another parameter /spl kappa/ which is a measure of the imbalance of the tree. We prove that the running time of the "go with the winners" scheme (to achieve 99% probability of success) is bounded by a polynomial in d and /spl kappa/. By contrast, the simple restart scheme: run several independent simulations and pick the deepest leaf encountered takes time exponential in /spl kappa/ and d in the worst-case. We also show that any algorithm that guarantees a constant probability of success must have worst case running time at least /spl kappa/d.>

The dynamic data structure management technique called hashing with lazy deletion (HwLD) is studied. A table managed under HwLD is built by a sequence of insertions and deletions of items. When hashing with lazy deletions, one does not delete items as soon as possible but keeps more items in the data structure than would be the case with immediate-deletion strategies. This deferral allows the use of a simpler deletion algorithm, leading to a lower overhead—in space and time—for the HwLD implementation. It is of interest to know how much extra space is used by HwLD. This paper investigates the maximum size and the excess space used by HwLD, under general probabilistic assumptions, by using the methodology of queueing theory. In particular, for the Poisson arrivals and general lifetime distribution of items, the excess space does not exceed the number of buckets in HwLD. As a byproduct of the analysis, the limiting distribution of the maximum queue length in an $M|G|\infty $ queueing system is also derived. The results generalize previous work in this area.

A model of learning that expands on the Valiant model is introduced. The point of departure from the Valiant model is that the learner is placed in a Markovian environment. The environment of the learner is a (exponentially large) graph, and the examples reside on the vertices of the graph, one example on each vertex. The learner obtains the examples while performing a random walk on the graph. At each step, the learning algorithm guesses the classification of the example on the current vertex using its current hypothesis. If its guess is incorrect, the learning algorithm updates its current working hypothesis. The performance of the learning algorithm in a given environment is judged by the expected number of mistakes made as a function of the number of steps in the random walk. The predictive value of Occam algorithms under this weaker probabilistic model of the learner's environment is studied.>

A random walk on a finite graph can be used to construct a uniform random spanning tree. It is shown how random walk techniques can be applied to the study of several properties of the uniform random spanning tree: the proportion of leaves, the distribution of degrees, and the diameter.

When several users simultaneously transmit over a shared communication channel, the messages are lost and must be retransmitted later. Various protocols specifying when to retransmit have been proposed and studied in recent years. One protocol is "binary exponential back-off," used in the local area network Ethernet. A mathematical model with several idealizations (discrete time slots, infinite users, no deletions) is shown to be unstable in that the asymptotic rate of successful transmissions is zero, however small the arrival rate.