A Recursive Formula for the Height of a Random Walk

The height of a binary sequence serves as a metric that captures the randomness of a sequence. In this work, the height of a finite binary sequence, which was a missing random variable in the recent work published at SETA 2024, is defined, and an explicit formula is derived for the probability values of a sequence of lengthn, to have a height equal tot, in terms of binomial coefficients. While this formula yields useful insights, computing exact values of binomial coefficients and those probability values becomes infeasible asngets larger. A method to overcome this problem is to use asymptotic approaches, which cause some errors when used in randomness tests. In this work, a recursive formula is derived for the same probability values, and the exact probability values for sequences of length up to at least 4096 is obtained. Using these exact values in a random walk randomness test, one can obtain more accurate results. In addition, formulas for the expected value and variance of the random variable that assigns the number of balanced points in a binary sequence of length n were derived, which had not been addressed in the previous work published at SETA 2024. A new randomness test is proposed based on random walk height.