Waiting for the Next Record
Consider a sequence of independent, identically distributed, continuous data values , , …. A value is a record value (or a high-water mark) if it is the largest value among all the values that have been recorded up to time . Let be the record value, ; define . Let be the time at which the record occurred (). Let be the inter-record waiting time, that is, the number of steps needed to get the record after the record. This Demonstration shows the distribution of for .
Snapshot 1: Here is the distribution of , that is, probabilities of the number of steps needed to get the first record after the zeroth record . The first record appears very soon. Indeed, with a probability of , the first record is the next data value . (The median of the distribution is shown with a green color while the 90- and 95-percent quantiles are not shown in any special way in the figure.) With an approximate probability of 0.9, the first record is among , and with an approximate probability of 0.95, the first record is among .
Snapshot 2: The second record, too, occurs quite soon. With a probability of , the second record is the next data value after the first record. The approximate median is 4, that is, with an approximate probability of 0.5, the second record is among the four data values after the first record. The approximate 90- and 95-percent quantiles are 43 and 104, respectively. That is, with a probability of 0.9, the second record is among the 43 data values after the first record.
Snapshot 3: With a probability of , the third record is the next data value after the second record. The approximate median is 10. The 90- and 95-percent quantiles are 172 and 469, respectively. Thus, to be sure, we have to reserve some time to see the third record; with a probability of 0.05, even 469 new data values after the second record do not suffice.
In the following, we summarize the 50-, 90-, and 95-percent quantiles of , ..., :
: 1, 9, 19
: 4, 43, 104
: 10, 172, 469
: 26, 645, 1947
: 68, 2333, 7696
: 182, 8225, 29363
The 50-percent quantiles or medians are quite moderate. For example, with an approximate probability of 0.5 the waiting time for the sixth record is at most only 182 steps after the fifth record. However, the 90- and 95-percent quantiles show that the probability densities are, after the initial rapid decrease, very flat and decrease very slowly. For example, to see the sixth record after the fifth record with a probability of 0.95, we need 29363 new data values!
The probabilities of the inter-record waiting times are given by [1, p. 27]
The expectation of the inter-record waiting time is infinite for all . The 50-, 90-, and 95-percent quantiles given the Demonstration are the points at which the cumulative distribution function is at least 0.5, 0.9, or 0.95, respectively, for the first time. All the quantiles were calculated outside of the Demonstration.
The probabilities considered here are unconditional. The conditional inter-record waiting time of the next record, conditioned on the time of the current record, is considered in the Demonstration "Records in Sequences of Random Variables". Note also that the probabilities of the inter-record waiting times do not depend on the distribution of the data.
 B. C. Arnold, N. Balakrishnan, and H. N. Nagaraja, Records, New York: Wiley, 1998.