Scenery Reconstruction for Random Walk on Random Scenery Systems
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2019
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911461536694272 |
|---|---|
| author | Lakrec, Tsviqa |
| author_facet | Lakrec, Tsviqa |
| contents | Consider a simple random walk on $\mathbb{Z}$ with a random coloring of $\mathbb{Z}$. Look at the sequence of the first $N$ steps taken in the random walk, together with the colors of the visited locations. We call this the record. From the record one can deduce the coloring of of the interval in $\mathbb{Z}$ that was visited, which is of size approximately $\sqrt{N}$. This is called scenery reconstruction. Now suppose that an adversary may change $δN$ entries in the record that was obtained. What can be deduced from the record about the scenery now? In this paper we show that it is likely that we can still reconstruct a large part of the scenery.
More precisely, we show that for any $θ<0.5,p>0,ε>0$, there are $N_{0}$ and $δ_{0}$ such that if $N>N_{0}$ and $δ<δ_{0}$ then with probability $>1-p$, the walk is such that we can reconstruct the coloring of $>N^θ$ integers, up to a number of possible reconstructions that is less than $2^{εs}$, where $s$ is the number of integers whose color we reconstruct. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1909_07470 |
| institution | arXiv |
| publishDate | 2019 |
| record_format | arxiv |
| spellingShingle | Scenery Reconstruction for Random Walk on Random Scenery Systems Lakrec, Tsviqa Probability Dynamical Systems 60C05, 37A35 Consider a simple random walk on $\mathbb{Z}$ with a random coloring of $\mathbb{Z}$. Look at the sequence of the first $N$ steps taken in the random walk, together with the colors of the visited locations. We call this the record. From the record one can deduce the coloring of of the interval in $\mathbb{Z}$ that was visited, which is of size approximately $\sqrt{N}$. This is called scenery reconstruction. Now suppose that an adversary may change $δN$ entries in the record that was obtained. What can be deduced from the record about the scenery now? In this paper we show that it is likely that we can still reconstruct a large part of the scenery. More precisely, we show that for any $θ<0.5,p>0,ε>0$, there are $N_{0}$ and $δ_{0}$ such that if $N>N_{0}$ and $δ<δ_{0}$ then with probability $>1-p$, the walk is such that we can reconstruct the coloring of $>N^θ$ integers, up to a number of possible reconstructions that is less than $2^{εs}$, where $s$ is the number of integers whose color we reconstruct. |
| title | Scenery Reconstruction for Random Walk on Random Scenery Systems |
| topic | Probability Dynamical Systems 60C05, 37A35 |
| url | https://arxiv.org/abs/1909.07470 |