proof of convergence in arbitrary precision PRNGs

Question

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.

Answer 1

You ask us for a proof this program will always halt for all initial seeds, but no such proof is possible in general. For instance, if the PRNG always outputs the number 66, then this will never halt (assuming you use big integers). Obviously that would be a really lousy PRNG, but if you aren't willing to assume that the PRNG is good, then no proof is possible.

On the other hand, if you assume that the PRNG is good (i.e., computationally indistinguishable from truly random values), then this is not really a question about PRNGs. Indeed, it's not even a question about computer science. It is a question about whether a particular random walk will eventually return to its starting point. (As such, this question really belongs on a mathematics site, not CS.SE.)

You ask for a proof that the random walk will never return to its starting point (that the probability of return to the initial point is exactly zero). I do not think any such proof is possible, because I do not think the statement is actually true.