EconPapers    
Economics at your fingertips  
 

COORDINATION THROUGH DE BRUIJN SEQUENCES

Olivier Gossner and Penelope Hernandez (penelope.hernandez@uv.es)

Working Papers. Serie AD from Instituto Valenciano de Investigaciones Económicas, S.A. (Ivie)

Abstract: Let µ be a rational distribution over a finite alphabet, and ( ) be a n-periodic sequences which first n elements are drawn i.i.d. according to µ. We consider automata of bounded size that input and output at stage t. We prove the existence of a constant C such that, whenever , with probability close to 1 there exists an automaton of size m such that the empirical frequency of stages such that is close to 1. In particular, one can take , where and .

Keywords: Coordination; complexity; De Bruijn sequences; automata (search for similar items in EconPapers)
Pages: 12 pages
Date: 2005-02
New Economics Papers: this item is included in nep-mic
References: Add references at CitEc
Citations: View citations in EconPapers (2)

Published by Ivie

Downloads: (external link)
http://www.ivie.es/downloads/docs/wpasad/wpasad-2005-05.pdf Fisrt version / Primera version, 2005 (application/pdf)

Related works:
Working Paper: Coordination through De Bruijn sequences (2006)
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ivi:wpasad:2005-05

Access Statistics for this paper

More papers in Working Papers. Serie AD from Instituto Valenciano de Investigaciones Económicas, S.A. (Ivie) Contact information at EDIRC.
Bibliographic data for series maintained by Departamento de Edición (edicion@ivie.es).

 
Page updated 2024-12-28
Handle: RePEc:ivi:wpasad:2005-05