Random insertion into a priority queue structure

The average number of levels that a new element moves up when inserted into a heap is investigated. Two probabilistic models under which such an average might be computed are proposed. A `Lemma of Conservation of Ignorance´ is formulated and used in the derivation of an exact formula for the average in one of these models. It is shown that this average is bounded by a constant and its asymptotic behaviour is discussed. Numerical data for the second model are also provided and analyzed.