Санкт-Петербургское отделение Математического института им. В.А.Стеклова РАН

ПРЕПРИНТ 11/2022

ВЕРОЯТНОСТНЫЕ СВОЙСТВА ИЗБЫТОЧНЫХ СИСТЕМ СЧИСЛЕНИЯ

This preprint was accepted October 3, 2022

АННОТАЦИЯ:

Данная работа посвящена изучению некоторых вероятност-
ных свойств эффективных систем счисления, примеры которых были
построены ранее в [AB4]. В частности, рассматривается вопрос об есте-
ственном распределении вероятностей на цифрах таких систем, и о под-
счёте количества различных n-значных чисел в таких системах. Оказы-
вается, что конечный автомат, проверяющий равенство в эффективной
системе счисления, может быть естественным образом преобразован в
некоторую цепь Маркова, свойства которой тесно связаны с упомянуты-
ми выше вопросами. Мы изучаем спектральный радиус и спектр матри-
цы переходов этой цепи Маркова, и даём полный ответ для некоторого
интересного класса эффективных систем счислений. При этом возникает
интересный новый класс многочленов, похожих на многочлены Эрмита
или на многочлены Кравчука.

Ключевые слова:   
 Абсолютная геометрия, эффективная система счис-
ления, цепь Маркова, матрица переходов цепи Маркова, многочлены Эр-
мита, многочлены Кравчука.
 

N. V. Durov



Probabilistic properties of redundant numeral systems




ABSTRACT:

 This work is dedicated to the study of some of the probabilistic properties
of the efficient numeral systems that were previously constructed in [AB4].
In particular, we consider the existence of natural probability
distributions on the set of digits of such numeral systems, and also
discuss how the number of distinct $n$-digit numbers in such systems may be
computed. It turns out that the finite automaton that checks two numbers
for equality in an efficient numeral system may be naturally transformed
into a Markov chain, the properties of which are relevant to the questions
mentioned above. We study the spectral radius and the spectrum itself of
the transition matrix of this Markov chain, and present a complete answer
for an interesting family of efficient numeral systems. An interesting new
class of polynomials appears in the process, somewhat similar to Hermite or
Krawtchouk polynomials.
   
  

Key words: 
Absolute geometry, efficient numeral system, Markov chain, transition
matrix of a Markov chain, Hermite polynomials, Krawtchouk polynomials.
 

 
 

 [Full text:
   (.pdf.gz)]






Back to all preprints


Back to the Steklov
Institute of Mathematics at St.Petersburg