Premium
Colliding stacks: A large deviations analysis
Author(s) -
Maier Robert S.
Publication year - 1991
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.3240020404
Subject(s) - stack (abstract data type) , wkb approximation , markov chain , statistical physics , formalism (music) , mathematics , large deviations theory , collision , physics , computer science , quantum mechanics , statistics , art , musical , computer security , visual arts , programming language
Abstract We analyze the performance of a prototypical scheme for shared storage allocation: two initially empty stacks evolving in a contiguous block of memory of size m. We treat the case in which the stacks are more likely to shrink than grow, but with the probabilities of insertion and deletion allowed to depend arbitrarily on stack height as a fraction of m. New results are obtained on the m → ∞ asymptotics of the stack collision time, and of the final stack heights. The results of Wentzell and Freidlin on the large deviations of Markov chains are used, and the relation of their formalism to the Hamiltonian formulation of classical mechanics is emphasized. Certain results on higher‐order asymptotics follow from WKB expansions.