# proof of convergence in arbitrary precision PRNGs

consider a program that generates a random walk using a PRNG, as in following pseudocode. it uses arbitrary precision arithmetic such that there is no limit on variable values (ie no overflow).

srand(x)
z = 0
while (z >= 0)
{
r = rand(100)
if (r <= 50) z -= 1
else z += 1
}


the PRNG is inited with seed x (also arbitrary precision). the PRNG rand(100) generates a value between 0..99. hence for 51 values the accumulator var z is decremented, for 49 values it is incremented.

it is expected due to the law of large numbers that this program will halt for all initial seeds x. however,

how does one prove it will halt for all initial seeds x?

it seems such a proof must depend on the details of the construction of the PRNG. am assuming there exist PRNGs such that a different random sequence is generated for every initial seed x (ie the infinite set of naturals). that in itself may be up for question. are such PRNGs known? where are they used? etc.. so an answer may come up with an arbitrary PRNG for the purposes of the question. a single example fulfilling the criteria would be an acceptable answer.

looking for related literature, similar problems/proof considered, etc.

• further thought/proof sketch: a simple proof is possible assuming a finite period (apparently the case with all PRNGs in use in computer science) & relates to all values seen over the finite period of the PRNG. its also possible considering a PRNG that creates a permutations of values over finite periods. – vzn Nov 22 '13 at 16:20