Analysis of Carries in Signed Digit Expansions

• Published in 2015
• Added on 2017-02-06

The number of positive and negative carries in the addition of two independent random signed digit expansions of given length is analyzed asymptotically for the $(q, d)$-system and the symmetric signed digit expansion. The results include expectation, variance, covariance between the positive and negative carries and a central limit theorem. Dependencies between the digits require determining suitable transition probabilities to obtain equidistribution on all expansions of given length. A general procedure is described to obtain such transition probabilities for arbitrary regular languages. The number of iterations in von Neumann's parallel addition method for the symmetric signed digit expansion is also analyzed, again including expectation, variance and convergence to a double exponential limiting distribution. This analysis is carried out in a general framework for sequences of generating functions.

Links

• http://arxiv.org/abs/1503.08816v3
• http://arxiv.org/pdf/1503.08816v3

Other information

BibTeX entry

@article{AnalysisofCarriesinSignedDigitExpansions,
	key = {AnalysisofCarriesinSignedDigitExpansions},
	type = {article},
	title = {Analysis of Carries in Signed Digit Expansions},
	author = {Clemens Heuberger and Sara Kropf and Helmut Prodinger},
	abstract = {The number of positive and negative carries in the addition of two
independent random signed digit expansions of given length is analyzed
asymptotically for the {\$}(q, d){\$}-system and the symmetric signed digit
expansion. The results include expectation, variance, covariance between the
positive and negative carries and a central limit theorem.
  Dependencies between the digits require determining suitable transition
probabilities to obtain equidistribution on all expansions of given length. A
general procedure is described to obtain such transition probabilities for
arbitrary regular languages.
  The number of iterations in von Neumann's parallel addition method for the
symmetric signed digit expansion is also analyzed, again including expectation,
variance and convergence to a double exponential limiting distribution. This
analysis is carried out in a general framework for sequences of generating
functions.},
	comment = {},
	date_added = {2017-02-06},
	date_published = {2015-10-09},
	urls = {http://arxiv.org/abs/1503.08816v3,http://arxiv.org/pdf/1503.08816v3},
	collections = {Basically computer science},
	url = {http://arxiv.org/abs/1503.08816v3 http://arxiv.org/pdf/1503.08816v3},
	urldate = {2017-02-06},
	archivePrefix = {arXiv},
	eprint = {1503.08816},
	primaryClass = {math.CO},
	year = 2015
}