A probabilistic approach to generalized Zeckendorf decompositions

DOI10.1137/140996859zbMATH Open1372.11013arXiv1405.2379OpenAlexW2964221473MaRDI QIDQ2813348FDOQ2813348

Authors: Iddo Ben-Ari, Steven J. Miller 

Publication date: 23 June 2016

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: Generalized Zeckendorf decompositions are expansions of integers as sums of elements of solutions to recurrence relations. The simplest cases are base-$b$ expansions, and the standard Zeckendorf decomposition uses the Fibonacci sequence. The expansions are finite sequences of nonnegative integer coefficients (satisfying certain technical conditions to guarantee uniqueness of the decomposition) and which can be viewed as analogs of sequences of variable-length words made from some fixed alphabet. In this paper we present a new approach and construction for uniform measures on expansions, identifying them as the distribution of a Markov chain conditioned not to hit a set. This gives a unified approach that allows us to easily recover results on the expansions from analogous results for Markov chains, and in this paper we focus on laws of large numbers, central limit theorems for sums of digits, and statements on gaps (zeros) in expansions. We expect the approach to prove useful in other similar contexts.

Full work available at URL: https://arxiv.org/abs/1405.2379

Recommendations

• Generalized Zeckendorf expansions
• The average gap distribution for generalized Zeckendorf decompositions
• Central limit theorems for gaps of generalized Zeckendorf decompositions
• The distribution of gaps between summands in generalized Zeckendorf decompositions (with an appendix by Iddo Ben-Ari and Steven J. Miller)
• Limiting distributions in generalized Zeckendorf decompositions

zbMATH Keywords

Markov processesfinite alphabetlongest gapZeckendorf decompositionspositive linear recurrence relationsdistribution of gaps

Mathematics Subject Classification ID

Convergence of probability measures (60B10) Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Fibonacci and Lucas numbers and polynomials and generalizations (11B39) Density, gaps, topology (11B05) Numerical aspects of recurrence relations (65Q30)

Cites Work

• Probability. Theory and examples.
• Fibonacci and Lucas numbers with applications. Volume I
• Central limit theorems for additive functionals of Markov chains.
• Systems of Numeration
• Title not available (Why is that?)
• Contributions to digit expansions with respect to linear recurrences
• Title not available (Why is that?)
• Title not available (Why is that?)
• Probabilistic approach to Perron root, the group inverse, and applications
• A generalization of Zeckendorf's theorem via circumscribed \(m\)-gons
• Generalized Zeckendorf expansions
• Systèmes de numération et fonctions fractales relatifs aux substitutions. (Numeration systems and fractal functions related to substitutions)
• The distribution of the sum-of-digits function
• Corrigendum to ``Generalized Zeckendorf expansions
• A generalization of a theorem of Lekkerkerker to Ostrowski's decomposition of natural numbers
• On the number of summands in Zeckendorf decompositions
• Differences of multiple Fibonacci numbers
• Generalizing Zeckendorf's theorem to \(f\)-decompositions
• Power and Exponential Sums of Digital Sums Related to Binomial Coefficient Parity
• From Fibonacci numbers to central limit type theorems
• Distribution of the sum-of-digits function of random integers: a survey
• Title not available (Why is that?)
• The distribution of gaps between summands in generalized Zeckendorf decompositions (with an appendix by Iddo Ben-Ari and Steven J. Miller)
• Gaussian behavior in generalized Zeckendorf decompositions
• The average gap distribution for generalized Zeckendorf decompositions
• A counting based proof of the generalized Zeckendorf's theorem
• Representation of Natural Numbers as Sums of Generalised Fibonacci Numbers
• Title not available (Why is that?)
• Title not available (Why is that?)
• Numeration systems, linear recurrences, and regular sets
• Title not available (Why is that?)
• Title not available (Why is that?)
• Gaussian asymptotic properties of the sum-of-digits function
• A generalization of Fibonacci far-difference representations and Gaussian behavior
• Generalizing Zeckendorf's Theorem: The Kentucky Sequence
• Numeration systems on a regular language
• Greedy numeration systems and regularity
• Distribution of additive functions with respect to numeration systems on regular languages
• Legal decompositions arising from non-positive linear recurrences
• New Behavior in Legal Decompositions Arising from Non-positive Linear Recurrences

Cited In (6)

• Benford Behavior of Generalized Zeckendorf Decompositions
• Title not available (Why is that?)
• Gaussian Behavior in Zeckendorf Decompositions From Lattices
• Zeckendorf representations and mixing properties of sequences
• Probabilistic equidimensional decomposition
• A generalization of a theorem of Lekkerkerker to Ostrowski's decomposition of natural numbers

This page was built for publication: A probabilistic approach to generalized Zeckendorf decompositions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2813348)