The paper investigates one of the main problems in the construction of quantum random number generators — obtaining a provably random output sequence from the results of physical measurements — the initial sequence generated by a physical random number generator. The questions of the fundamental possibility and the conditions under which it is possible to "reach out" to randomness, as well as what is meant by provable randomness, are discussed. Methods of extraction of provably random bit sequences from stationary Markov chains of finite order are considered, i.e. under the assumption on the ultimate depth of dependence of the results of physical measurements on prehistory, which is an adequate approximation to the real situation. The extraction of the output provably random bit sequence from the initial sequence of physical measurement results using the effective arithmetic coding method of V.F. Babkin is demonstrated. It is shown that even from the primary sequences of the results of physical measurements, which are dependent (correlated) to any finite depth (prehistory), it is possible to provably obtain random bit sequences. The goal set by the authors was to show the connection of various approximations that are used in the development and description of methods for obtaining random bit sequences with fundamental physical limitations of Nature. The mathematical proofs are brought to practical algorithms that are used in real random number generators. The necessary mathematical proofs are presented at an intuitive level for the physical audience, they do not require prior specialized knowledge and are available to undergraduate university students.