A Recursive Formula for the Height of a Random Walk

Date

2026-01-01

Author

Uğuz, Muhiddin

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

64
views

7
downloads

Cite This

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 length n, to have a height equal to t, in terms of binomial coefficients. While this formula yields useful insights, computing exact values of binomial coefficients and those probability values becomes infeasible as n gets 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.

Subject Keywords

Expected value, graph of a binary sequence, height of a random walk, random walk, variance

URI

https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=105027519473&origin=inward
https://hdl.handle.net/11511/118668

Collections

Department of Mathematics, Article