On the Evolution of Islands

Let n cells be arranged in a ring, or alternatively, in a row. Initially, all cells are unmarked. Sequentially, one of the unmarked cells is chosen at random and marked until, after n steps, each cell is marked. After the kth cell has been marked the configuration of marked cells defines some number of islands: maximal sets of adjacent marked cells. Let ξ k denote the random number of islands after k cells have been marked. We give explicit expressions for moments of products of ξ k ’s and for moments of products of 1/ξ k ’s. These are used in a companion paper to prove that if a random graph on the natural number is made by drawing an edge betweeni≧1 andj>i with probabilityλ/j, then the graph is almost surely connected ifλ>1/4 and almost surely disconnected ifλ≦1/4.