-1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – vzn Nov 22 '13 at 16:20
3
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ do not disagree except the assertion that its not at least a question of interest in CS, because it seems to relate to whether the PRNG is "biased", which is very relevant to the design of PRNGs in general. $\endgroup$ – vzn Nov 19 '13 at 1:21
  • 1
    $\begingroup$ also the answer misses that even with a uniformly distributed PRNG its actually a slightly biased random walk... $\endgroup$ – vzn Nov 19 '13 at 2:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.