Growth of Replacements

Abstract

The following game in a similar formulation to Petri nets and chip-firing games is studied: Given a finite collection of baskets, each has an infinite number of balls of the same value. Initially, a ball from some basket is chosen to put on the table. Subsequently, in each step a ball from the table is chosen to be replaced by some 2 balls from some baskets. Which baskets to take depend only on the ball to be replaced and they are decided in advance. Given some n, the object of the game is to find the maximum possible sum of values g(n) for a table of n

balls.

In this article, the sequence g(n)/n for n=1,2,… will be shown to converge to a growth rate λ. Furthermore, this value λ is also the rate of a structure called pseudo-loop and the solution of a rather simple linear program. The structure and the linear program are closely related, e.g. a solution of the linear program gives a pseudo-loop with the rate λ in linear time of the number of baskets, and vice versa with the pseudo-loop giving a solution to the dual linear program. A method to test in quadratic time whether a given λ0 is smaller than λ is provided to approximate λ. When the values of the balls are all rational, we can compute the precise value of λ in cubic time, using the quadratic time rate test algorithm and the binary search with a special condition to stop. Four proofs of the limit λ are given: one just uses the relation between the baskets, one uses pseudo-loops, one uses the linear program and one uses Fekete's lemma (the latest proof assumes a condition on the rule of replacements).