Strong law of large numbers on graphs and groups

Natalia Mosina, Alexander Ushakov

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

We consider (graph-)group-valued random element ξ, discuss the properties of a mean-set E(ξ), and prove the generalization of the strong law of large numbers for graphs and groups. Furthermore, we prove an analogue of the classical Chebyshev's inequality for ξ and Chernoff-like asymptotic bounds. In addition, we prove several results about configurations of mean-sets in graphs and discuss computational problems together with methods of computing mean-sets in practice and propose an algorithm for such computation.

Original languageEnglish
Pages (from-to)67-103
Number of pages37
JournalGroups, Complexity, Cryptology
Volume3
Issue number1
DOIs
StatePublished - May 2011

Keywords

  • Average
  • Chebyshev inequality
  • Chernoff bound
  • Configuration of mean-sets
  • Expectation
  • Free group
  • Mean-set
  • Probability measures on graphs and groups
  • Shift search problem
  • Strong law of large numbers

Fingerprint

Dive into the research topics of 'Strong law of large numbers on graphs and groups'. Together they form a unique fingerprint.

Cite this