Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Bit flipping and time to recover
KTH, School of Electrical Engineering (EES).
2016 (English)In: Journal of Applied Probability, ISSN 0021-9002, E-ISSN 1475-6072, Vol. 53, no 3, 650-666 p.Article in journal (Refereed) Published
Abstract [en]

We call 'bits' a sequence of devices indexed by positive integers, where every device can be in two states: 0 (idle) and 1 (active). Start from the 'ground state' of the system when all bits are in 0-state. In our first binary flipping (BF) model the evolution of the system behaves as follows. At each time step choose one bit from a given distribution P on the positive integers independently of anything else, then flip the state of this bit to the opposite state. In our second damaged bits (DB) model a 'damaged' state is added: each selected idling bit changes to active, but selecting an active bit changes its state to damaged in which it then stays forever. In both models we analyse the recurrence of the system's ground state when no bits are active. We present sufficient conditions for both the BF and DB models to show recurrent or transient behaviour, depending on the properties of the distribution P. We provide a bound for fractional moments of the return time to the ground state for the BF model, and prove a central limit theorem for the number of active bits for both models.

Place, publisher, year, edition, pages
Applied Probability Trust , 2016. Vol. 53, no 3, 650-666 p.
Keyword [en]
Binary system, bit flipping, random walk on a group, Markov chain recurrence, critical behaviour
National Category
Mathematics
Identifiers
URN: urn:nbn:se:kth:diva-196625DOI: 10.1017/jpr.2016.32ISI: 000386349900002ScopusID: 2-s2.0-84991695785OAI: oai:DiVA.org:kth-196625DiVA: diva2:1047268
Note

QC 20161117

Available from: 2016-11-17 Created: 2016-11-17 Last updated: 2016-11-17Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Muratov, Anton
By organisation
School of Electrical Engineering (EES)
In the same journal
Journal of Applied Probability
Mathematics

Search outside of DiVA

GoogleGoogle Scholar

Altmetric score

Total: 4 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf