The Space Complexity of Generating Random Tent Codes

This paper is motivated by a question of whether it is possible to calculate a chaotic sequence efficiently, e.g., is it possible to get the n-th bit of a bit sequence generated by a chaotic map, such as <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\beta$</tex> -expansion, tent map, and logistic map in <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathrm{o}(n)\text{time}/\text{space}$</tex> ? From the viewpoint of theoretical computer science, this paper gives an affirmative answer to the question about the space complexity of a tent map. We prove that a tent code of n-bits with an initial condition uniformly at random is exactly generated in <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathrm{O}(\log^{2}n)$</tex> space in expectation.