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 language | English |
---|---|
Pages (from-to) | 67-103 |
Number of pages | 37 |
Journal | Groups, Complexity, Cryptology |
Volume | 3 |
Issue number | 1 |
DOIs | |
State | Published - 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