text:
# Violation of self-similarity in the expansion of a 1D Bose gas

## I Introduction

The experimental achievement of Bose-Einstein condensation (BEC) BEC  has aroused a large interest in the physics of ultracold atomic gases. Among the topics related to this field, the physics of low dimensional atomic gases has recently attracted significant attention. The development of the trapping techniques has allowed for the realization of very anisotropic geometries, where the confinement is so strong in one or two dimensions, that at low temperatures the transversal motion is “frozen”, and does not contribute to the dynamics of the system. In this way two- MIT ; Safonov ; Hansel ; Florence  and one-dimensional MIT ; Salomon ; Greiner1  systems have been accomplished. Low-dimensional gases present significantly different properties compared to the three-dimensional ones. A remarkable example is provided by the existence of quasi-condensation Petrov1D ; Kagan ; Petrov2D ; Petrov3D , whose effects have been recently observed experimentally quasiBECexp .

During the last years, the 1D Bose gases have been the subject of growing interest, in particular the limit of impenetrable bosons Girardeau60 , which behave to a large extent as a noninteracting Fermi system, acquiring some remarkable properties. The conditions for the experimental realization of strongly correlated 1D gases are rather restrictive Petrov1D ; Olshanii1 , since a large radial compression, a sufficiently small density, and eventually a large scattering length are needed. Fortunately, recent experimental developments have opened perspectives in this sense. Especially interesting is the possibility to modify at will the interatomic interactions by means of Feshbach resonances Cornish , and the capability of loading an atomic gas in an optical lattice Greiner .

From the theoretical side, the physics of 1D Bose gases was first investigated by Girardeau Girardeau60 , who considered the limit of impenetrable bosons, also called Tonks-Girardeau (TG) gas, pointing out a non trivial relation with the physics of ideal Fermi gases. This analysis was later extended by Lieb and Liniger Lieb63 , who solved analytically the problem for any regime of interactions, using Bethe Ansatz. Yang and Yang yang  extended the analysis including finite temperature effects. Recently, the experimental accessibility of trapped gases, have encouraged the investigation of the harmonically trapped case. The Bose-Fermi (BF) mapping has been employed to the case of an inhomogeneous gas in the TG limit Wright2 . However, there is unfortunately, to the best of our knowledge, no exact solution for arbitrary interaction strength in the case of trapped gases. The problem of the equilibrium of a trapped gas can be analyzed using a local density approximation and employing the Lieb-Liniger (LL) equation of state locally to evaluate the equilibrium density profiles Olshanii2 . A similar formalism has been recently employed to analyze the collective oscillations in the presence of harmonic trapping Chiara . Both Refs. Olshanii2  and Chiara  have shown the occurrence of a continuous transition from the mean field (MF) regime to the TG one as the intensity of the interaction is varied. Recently, Gangardt and Shlyapnikov Gangardt  have discussed the stability and phase coherence of 1D trapped Bose gases. These authors have analyzed the local correlation properties and found that inelastic decay processes, such as three body recombination, are suppressed in the TG regime, and intermediate regimes between MF and TG. This fact opens promising perspectives towards the accomplishment of strongly interacting 1D Bose gases with large number of particles. This analysis have been very recently extended to the case of finite temperatures Kheruntsyan .

The expansion of a one-dimensional Bose gas in a guide was analyzed in Ref. Letter , by means of a hydrodynamic approach based on the local LL model. The expansion dynamics was shown to be different for different interaction strengths, and its analysis could be employed to discern between the TG and MF regimes. In particular, the self-similar solution is violated.

In this paper, we extend the analysis of Ref.Letter  by introducing a variational approach, which permits us to study the asymptotic regime at large expansion times. This method is shown to be in excellent agreement with previous direct numerical simulations, and additionally permits us to recover the results of Refs. Olshanii2  and Chiara . More importantly, our variational approach allows us to determine the regime of parameters for which the self-similarity of the expansion is violated.

The paper is organized as follows. In Sec. II we introduce the local LL model which we employ to analyze the expansion dynamics. In Sec. III we briefly discuss the numerical results obtained in Ref. Letter . In Sec. IV we present a variational approach which allows us to investigate in detail the expansion dynamics for arbitrary regimes of parameters. Finally we conclude in Sec. V.

## II Local Lieb-Liniger model

We analyze in the following a dilute gas of $`N`$ bosons confined in a very elongated harmonic trap with radial and axial frequencies $`\omega _\rho `$ and $`\omega _z`$ ($`\omega _\rho \omega _z`$). We assume that the transversal confinement is strong enough so that the interaction energy per particle is smaller than the zero-point energy $`\mathrm{}\omega _\rho `$ of the transversal trap. In this way, the transversal dynamics is effectively “frozen” and the system can be considered as dynamically 1D. In this section we briefly review the formalism introduced in Ref. Olshanii2 .

We assume that the interparticle interaction can be approximated by a delta function pseudopotential. Therefore the Hamiltonian that describes the physics of the 1D gas becomes

$$\widehat{H}_{1\mathrm{D}}=\widehat{H}_{1\mathrm{D}}^0+\underset{j=i}{\overset{N}{}}\frac{m\omega _z^2z_i^2}{2}$$
(1)
where

$$\widehat{H}_{1\mathrm{D}}^0=\frac{\mathrm{}^2}{2m}\underset{j=1}{\overset{N}{}}\frac{^2}{z_j^2}+g_{1\mathrm{D}}\underset{i=1}{\overset{N1}{}}\underset{j=i+1}{\overset{N}{}}\delta \left(z_iz_j\right)$$
(2)
is the homogeneous Hamiltonian in absence of the harmonic trap, $`m`$ is the atomic mass and $`g_{1\mathrm{D}}=2\mathrm{}^2/ma_{1\mathrm{D}}`$. The scattering problem under one-dimensional constraints was analyzed in detail by Olshanii Olshanii1 , and it is characterized by the one-dimensional scattering length $`a_{1\mathrm{D}}=(a_\rho ^2/2a)[1𝒞(a/a_\rho )]`$, with $`a`$ the three-dimensional scattering length, $`a_\rho =\sqrt{2\mathrm{}/m\omega _\rho }`$ the oscillator length in the radial direction, and $`𝒞=1.4603\mathrm{}`$. As shown by Lieb and Liniger Lieb63 , the homogeneous Hamiltonian $`\widehat{H}_{1\mathrm{D}}^0`$ can be diagonalized exactly by means of Bethe Ansatz Kor . In the thermodynamic limit, a 1D gas at zero temperature with a given linear density $`n`$, is characterized by the energy per particle

$$ϵ(n)=\frac{\mathrm{}^2}{2m}n^2e(\gamma (n)),$$
(3)
where $`\gamma =2/n|a_{1\mathrm{D}}|`$. The function $`e(\gamma )`$ fulfills

$$e(\gamma )=\frac{\gamma ^3}{\lambda ^3(\gamma )}_1^1g\left(x|\gamma \right)x^2𝑑x,$$
(4)
where $`g\left(x|\gamma \right)`$ and $`\lambda (\gamma )`$ are the solutions of the LL system of equations Lieb63

$`g\left(x|\gamma \right)`$ $`=`$ $`{\displaystyle \frac{1}{2\pi }}+{\displaystyle \frac{1}{2\pi }}{\displaystyle _1^1}{\displaystyle \frac{2\lambda (\gamma )}{\lambda ^2(\gamma )+(yx)^2}}g\left(y|\gamma \right)𝑑y`$ (5)
$`\lambda (\gamma )`$ $`=`$ $`\gamma {\displaystyle _1^1}g\left(x|\gamma \right)𝑑x.`$ (6)
We assume next that at each point $`z`$ the gas is in local equilibrium, with local energy per particle provided by Eq. (3). Then, one can obtain the corresponding hydrodynamic equations for the density and the atomic velocity

$`{\displaystyle \frac{}{t}}n+{\displaystyle \frac{}{z}}(nv)`$ $`=`$ $`0`$ (7)
$`{\displaystyle \frac{}{t}}v+v{\displaystyle \frac{}{z}}v`$ $`=`$ $`{\displaystyle \frac{1}{m}}{\displaystyle \frac{}{z}}(\mu _{le}(n)+{\displaystyle \frac{1}{2}}m\omega _z^2z^2).`$ (8)
where

$$\mu _{le}(n)=\left(1+n\frac{}{n}\right)ϵ(n)$$
(9)
is the Gibbs free energy per particle.

Note that for the case of $`n|a_{1D}|\mathrm{}`$, one obtains $`\mu _{le}(n)=g_{1D}n`$, retrieving the 1D Gross-Pitaevskii equation (GPE) Gross , whereas for the case $`n|a_{1D}|0`$, one gets $`\mu _{le}(n)=\pi ^2\mathrm{}^2n^2/2m`$, and the equation of Ref. Kolomeisky  is recovered. The system has only one control parameter Petrov1D ; Olshanii2 ; Chiara , namely $`A=N|a_{1D}|^2/a_z^2`$, where $`a_z=\sqrt{\mathrm{}/m\omega _z}`$ is the harmonic oscillator length in the $`z`$ direction. The regime $`A1`$ corresponds to the MF limit, in which the stationary-state density profile has a parabolic form. On the other hand, the regime $`A1`$ corresponds to the TG regime, which is characterized by a stationary-state density profile with the form of a square root of a parabola.

## III Numerical results

In Ref. Letter , equations (3),(5),(6),(9) were employed to simulate numerically the expansion of a 1D gas in the framework of the hydrodynamic formalism. The expansion follows the sudden removal of the axial confinement, while the radial one is kept fixed. In particular, it was observed that during the expansion the density profile is well described by the expression

$$n(z,t)=n_m(t)\left(1\left(\frac{z}{R(t)}\right)^2\right)^{s(t)}$$
(10)
where $`n_m(t)`$ provides the appropriate normalization, $`R(t)`$ is the radius of the cloud, and the exponent $`s(t)`$ takes the value $`s(0)=1`$ for an initial MF gas. The function $`s(t)`$ decreases monotonically in time, approaching an asymptotic value (see Fig. 1). Therefore, contrary to the expansion dynamics for a BEC Castin ; Kagan1 ; Minniti , the self-similarity of the density profile is violated.

At this point we discuss the physics behind this violation of the self-similarity. If the local chemical potential presents a fixed power law dependence on the density, $`\mu _{le}n^\lambda `$, it is easy to show from the hydrodynamic equations (7) and (8), that there exists a self-similar solution of the form $`n=(n_0/b)(1(z/bR)^2)^{1/\lambda }`$, where $`\ddot{b}=\omega _z^2/b^{\lambda +1}`$. For the particular case of the TG gas, the scaling law can be also obtained from the exact BF mapping Letter . However, since $`\mu _{le}`$ is obtained from the LL equations, the dependence of $`\mu _{le}`$ on $`n`$ is quadratic for a low density and linear for a large one. Therefore, $`\mu _{le}`$ does not fulfill a fixed power law dependence during the expansion, and the self-similarity is violated. In particular, as the expansion proceeds the whole system approaches the low density regime, and consequently the exponent $`s`$ decreases monotonically. In the next section, we analyze in more detail this effect.

## IV Variational calculation

In this section, we complete our understanding of the expansion of a one-dimensional Bose gas in a guide by means of a variational Ansatz using a Lagrangian formalism. The Lagrangian density for the system is of the form

$`=mn{\displaystyle \frac{\varphi }{t}}{\displaystyle \frac{1}{2}}mn\left({\displaystyle \frac{\varphi }{z}}\right)^2{\displaystyle \frac{1}{2}}m\omega _z^2z^2n\epsilon (n)n`$ (11)
where the velocity field is defined as $`v=\varphi /z`$. The equations of motion are obtained from the functional derivation of the action $`𝒜=𝑑t𝑑z`$: $`\delta 𝒜/\delta \varphi =0`$ (continuity equation), $`\delta 𝒜/\delta n=0`$ (which after partial derivation with respect to $`z`$ provides the Euler equation). From the numerical results we have observed that the density is at any time well described by Eq. (10). Therefore, we assume the following Ansatz for the density

$$n=\frac{C(s)}{b}\left(1\frac{z^2}{R^2b^2}\right)^s,$$
(12)
where $`b`$ and $`s`$ are time dependent variables, $`R`$ is the initial Thomas-Fermi radius, and $`C(s)`$ is related to the normalization to the total number of particles. For the $`\varphi `$ field we consider the following form:

$$\varphi =\frac{1}{2}\alpha z^2+\frac{1}{4}\beta z^4,$$
(13)
where $`\alpha `$ and $`\beta `$ are time dependent parameters. We stress at this point, that in the analysis of the self-similar expansion of a BEC Castin ; Kagan1 ; Minniti , a quadratic ansatz (in $`z`$) for the $`\varphi `$ field provides the exact solution. However, for the problem under consideration in this paper, it is necessary to include higher order terms to account for the violation of the self-similarity. We have checked that terms of higher order than $`z^4`$ introduces only small corrections, and therefore we reduce to the form of Eq. (13).

We are interested in the dynamics of the parameters $`b`$ and $`s`$, related to the size and the shape of the cloud, respectively. Integrating the Lagrangian density in $`z`$, $`L=𝑑z`$, one finds a Lagrangian for the above mentioned parameters:

$`L(\dot{\alpha },`$ $`\alpha ,\dot{\beta },\beta ,b,s)=`$ (14)
$`{\displaystyle \frac{mNR^2}{2}}\{{\displaystyle \frac{\dot{\alpha }b^2}{2s+3}}{\displaystyle \frac{3}{2}}{\displaystyle \frac{\dot{\beta }b^4}{(2s+5)(2s+3)}}\mathrm{\Gamma }0`$
$`{\displaystyle \frac{\alpha ^2b^2}{2s+3}}2{\displaystyle \frac{\alpha \beta b^4}{(2s+5)(2s+3)}}`$
$`{\displaystyle \frac{\beta ^2b^6}{(2s+7)(2s+5)(2s+3)}}`$
$`\mathrm{\Gamma }0{\displaystyle \frac{b^2\omega _z^2}{2s+3}}\}{\displaystyle }dznϵ(n).`$
We perform a gauge transformation footnote2

$`L(t,q,\dot{q})L(t,q,\dot{q})+{\displaystyle \frac{d}{dt}}g(t,q),`$ (15)
where

$$g(t,q)=\frac{mNR^2}{2}\left\{\frac{\alpha b^2}{2s+3}\frac{3}{2}\frac{\beta b^4}{(2s+5)(2s+3)}\right\}.$$
(16)
The resulting Lagrangian is of the form $`L=L(\alpha ,\beta ,\dot{b},b,\dot{s},s)`$. Imposing the conservation laws $`L/\alpha =L/\beta =0`$, we obtain a Lagrangian depending only on the two relevant parameters $`s`$ and $`b`$, of the form $`L=KV`$, where

$`{\displaystyle \frac{V}{E_{1D}}}`$ $`=`$ $`\left({\displaystyle \frac{B(b,s)}{f_0(s)}}+{\displaystyle \frac{A^2b^2}{[\eta _0f_0(s_0)]^2}}{\displaystyle \frac{1}{2s+3}}\right),`$ (17)
$`{\displaystyle \frac{K}{E_{1D}}}`$ $`=`$ $`{\displaystyle \frac{A^2\left(M_{11}\dot{b}^2+2M_{12}\dot{b}\dot{s}+M_{22}\dot{s}^2\right)}{[\eta _0f_0(s_0)]^2(2s+3)}},`$ (18)
where $`E_{1D}=\mathrm{}^2/2m|a_{1D}|^2`$ is the typical energy associated with the interatomic interactions. In Eq. (17), we use the function $`B(b,s)=𝑑y(1y^2)^sϵ(n(y))/E_{1D}`$, where we integrate over the rescaled axial coordinate $`y=z/Rb`$. In Eqs. (17) and (18), we define the dimensionless central density $`\eta _0=n_0|a_{1D}|`$, where $`n_0`$ is the initial central density, and the parameter $`s_0=s(t=0)`$. We have additionally employed the auxiliary functions $`f_n(s)=y^n(1y^2)^s𝑑y`$, and the coefficients

$`M_{11}`$ $`=`$ $`1,`$ (19)
$`M_{12}`$ $`=`$ $`{\displaystyle \frac{b}{2s+3}}`$ (20)
$`M_{22}`$ $`=`$ $`{\displaystyle \frac{b^2(121+186s+96s^2+16s^3)}{4(s+1)(2s+3)^2(2s+5)^2}}`$ (21)
From the Lagrangian $`L`$, one obtains the corresponding Euler-Lagrange equations for the parameters $`b`$ and $`s`$. In order to find the initial conditions $`\eta _0`$ and $`s_0`$ for the expansion, we have numerically minimized the potential $`V`$ in the presence of the harmonic trap for different values of $`A`$, assuming $`b=1`$ (see Fig. 2). When $`A1`$, $`s_0`$ tends to $`1`$, as expected for the MF case. On the contrary, when $`A1`$, $`s_0`$ tends to $`1/2`$ (TG profile). As expected from Ref. Olshanii2 , for $`A1`$, $`\eta _0A^{1/2}`$, whereas for $`A1`$, the MF dependence $`\eta _0A^{2/3}`$ is recovered.

Our variational approach allows us to calculate the lowest compressional mode, offering an alternative method as the one discussed in Ref. Chiara . Expanding the potential $`V`$ around the equilibrium solution up to second order in $`b`$ (see Fig. 3), and neglecting for small oscillations the time-dependence of $`s`$, we obtain

$`{\displaystyle \frac{\omega _m^2}{\omega _z^2}}=1+{\displaystyle \frac{1}{2A^2}}{\displaystyle \frac{[\eta _0^2f_0(s_0)]^2}{f_2(s_0)}}\mathrm{\Gamma }0{\displaystyle \frac{^2B}{b^2}}|_{b=1}.`$ (22)
Our results show a continuous transition from the MF value, $`\omega _m=\sqrt{3}\omega _z`$, to the TG one, $`\omega _m=2\omega _z`$, in excellent agreement with the results obtained by means of a sum rule formalism Chiara .

From the corresponding Euler-Lagrange equations, we have obtained the dynamics of $`b(t)`$ and $`s(t)`$. We have checked in all our calculations that the energy and number of particles remain a constant of motion. We have compared the variational results with our simulations based on the exact resolution of the hydrodynamic equations Letter , obtaining an excellent agreement (see Fig. 1).

We have analyzed the asymptotic value, $`\dot{b}_{\mathrm{}}`$, for different values of $`A`$. It is easy to obtain, that for a power law dependence of the local chemical potential $`\mu _{le}n^\lambda `$, the derivative of the scaling parameter asymptotically approaches a value $`\dot{b}_{\mathrm{}}=\sqrt{2/\lambda }\omega _z`$. Therefore a continuous transition from $`\dot{b}_{\mathrm{}}=\omega _z`$ (TG) to $`\dot{b}_{\mathrm{}}=\sqrt{2}\omega _z`$ (MF) is expected. We recover this dependence from our variational calculations (see Fig. 4).

We have analyzed the behavior of $`s`$ during the expansion dynamics for different values of $`A`$. In particular, we have defined the asymptotic ratio $`\xi =s_{\mathrm{}}/s_0`$, with $`s_{\mathrm{}}=s(t\mathrm{})`$ (see Fig. 5). Deeply in the TG regime ($`A1`$) or in the MF one ($`A1`$), $`\xi 1`$, i.e. in those extreme regimes, the expansion is well-described by a self-similar solution. However, for intermediate values, $`\xi <1`$, i.e. the expansion is not self-similar. The self-similarity is maximally violated in the vicinity of $`A=1`$, although $`\xi `$ departs significantly from $`1`$ for a range $`0.01A100`$. The behavior at large $`A`$ can be understood as follows. If the gas is at $`t=0`$ deeply in the MF regime, the change of the functional dependence of $`\mu _{le}`$ with the density occurs at very long expansion times, when the initial interaction energy of the gas has been fully transferred into kinetic energy. Therefore, for large values of $`A`$ the self-similarity is recovered.

## V Conclusions

In this paper, we have extended the analysis of Ref. Letter  on the expansion dynamics of a one-dimensional Bose gas in a guide. We have shown that the expansion violates under certain conditions the self-similarity, and in this sense differs significantly from the expansion dynamics of a BEC. We have shown that the problem can be solved by employing the hydrodynamic approach, and the local Lieb-Liniger model. We have developed a variational approach based on a Lagrangian formalism to study the expansion for any regime of parameters. We have identified the possible physical situations at which self-similarity is violated. This should occur in a rather wide range of parameters ($`0.01A100`$). The particular properties of the expansion of a gas in the strongly-interacting regime could therefore be employed to discern between mean-field and strongly-interacting regimes. In addition, the asymptotic behavior of the expanded cloud could be employed to discriminate between different initial interaction regimes of the system.

Our discussion has been restricted to the analysis of the density properties. In fact the present formalism cannot describe the dynamics of the coherence in the system, i.e. we are limited to the diagonal terms of the corresponding single-particle density matrix. The description of the non diagonal terms lies beyond the scope of this paper, and requires other techniques of analysis Gangardt ; Giorgini .

We acknowledge support from Deutsche Forschungsgemeinschaft (SFB 407), the RTN Cold Quantum gases, ESF PESC BEC2000+, Royal Society of Edinburgh, and the Ministero dell’Istruzione, dell’Università e della Ricerca (MIUR). L. S. and P. P. wish to thank the Alexander von Humboldt Foundation, the Federal Ministry of Education and Research and the ZIP Programme of the German Government. Discussions with M. D. Girardeau, M. Lewenstein, D. S. Petrov, and G. V. Shlyapnikov are acknowledged. We especially thank C. Menotti for providing us with the data of Ref. Chiara .


format: text

text:
# Dieudonné Determinants for Skew Polynomial Rings

## 1. The Dieudonné determinant over skew polynomial rings

In this section we recall some properties of skew polynomial rings and of matrices over skew fields. We then state and prove the main result.

### 1.1. Skew polynomial rings

This short treatment is based on chapter 1 of \[Cohn 1977\]. Proofs can be found in there.

Let $`k`$ be a field endowed with an endomorphism $`\alpha :kk:aa^\alpha `$ and an $`\alpha `$-derivation $`\delta `$. The latter is an additive map $`\delta :kk:aa^\delta `$ such that

$$(ab)^\delta =a^\delta b^\alpha +ab^\delta .$$

If $`\alpha =1`$, this is just a derivation. The *left skew polynomial ring* in $`x`$ over $`k`$ associated with $`\alpha `$ and $`\delta `$, denoted by $`R=k[x;\alpha ,\delta ]`$ is the ring whose elements are expressions of the form $`a_0+a_1x+\mathrm{}+a_mx^m`$ with $`a_ik`$. Addition is defined in the usual way. Multiplication is defined by the commutation rule

$$xa=a^\alpha x+a^\delta $$

The left euclidean algorithm holds in $`R`$, relative to the usual degree map $`\mathrm{deg}:R\{0\}`$. Hence, $`R`$ is a left principal ideal domain. When $`\alpha `$ is an automorphism of the field $`k`$ then $`R`$ is also a right skew polynomial ring and hence also right euclidean.

Since $`R`$ is a left principal ideal domain, it is left Ore and it has a unique skew field of fractions $`Q`$. It consists of expressions of the form $`r/s`$ with $`s0`$ and $`r/s=r^{}/s^{}`$ if and only if there exist non-zero $`u,u^{}`$ in $`R`$ with $`ur=u^{}r^{}`$ and $`us=u^{}s^{}`$. The degree map $`\mathrm{deg}:Q\{\mathrm{}\}:r/s\mathrm{deg}(r)\mathrm{deg}(s)`$ is well-defined and satisfies

$$\mathrm{deg}(tu)=\mathrm{deg}(t)+\mathrm{deg}(u).$$

It factors over $`QQ^{\mathrm{ab}}=Q^\times /[Q^\times ,Q^\times ]\{0\}`$.

### 1.2. Matrices over skew polynomial rings

$`\mathrm{M}(n,S)`$ is the ring of $`n\times n`$ matrices over the ring $`S`$. The subring of diagonal matrices is denoted by $`\mathrm{D}(n,S)=S^n`$. We write $`\mathrm{GL}(n,S)`$ for the group of invertible elements in $`\mathrm{M}(n,S)`$ and $`\mathrm{E}(n,S)`$ for the subgroup generated by the elementary matrices (corresponding to the elementary row and column operations).

Consider the ring $`\mathrm{M}(n,Q)`$ and its subring $`\mathrm{M}(n,R)`$. On the former, the Dieudonné determinant (\[Dieudonné 1943\], \[Draxl 1983\]) defines a multiplicative function

$$det:\mathrm{M}(n,Q)Q^{\mathrm{ab}}$$

and an exact sequence of groups

$$1\mathrm{E}(n,Q)\mathrm{GL}(n,Q)(Q^{\mathrm{ab}})^\times 1$$

Furthermore, $`\mathrm{E}(n,Q)`$ equals the commutator subgroup of $`\mathrm{GL}(n,Q)`$.111 Over *every* skew field, $`\mathrm{E}`$ is the kernel of $`det`$. It equals the commutator subgroup of $`\mathrm{GL}`$ unless $`n=2`$ and the skew field is the finite field of two elements.  As the function $`det`$ is rational in the entries of the matrix, we cannot hope for a restriction to $`\mathrm{M}(n,R)`$ with the same properties as its commutative, polynomial, counterpart. However, consider the map

$$\mathrm{deg}det:\mathrm{M}(n,Q)\{\mathrm{}\}.$$

It is surjective and satisfies $`\mathrm{deg}det(AB)=\mathrm{deg}det(A)+\mathrm{deg}det(B)`$. We make a little observation on its restriction to $`\mathrm{M}(n,R)`$.

###### Theorem 1.1.

The restriction of the map $`\mathrm{deg}det`$ to $`\mathrm{M}(n,R)`$ induces an exact sequence of unitary semigroups

$$1\mathrm{GL}(n,R)\mathrm{M}(n,R)\{\mathrm{}\}0.$$

Moreover, $`\mathrm{deg}det`$ is unique in the sense that every semigroup homomorphism $`f:\mathrm{M}(n,R)\{\mathrm{}\}`$ that coincides with $`\mathrm{deg}det`$ on $`\mathrm{D}(n,R)`$ equals $`\mathrm{deg}det`$.

###### Proof.

We first prove the uniqueness claim and then use it to deduce the first part of the theorem.

Step 1. Assume $`f:\mathrm{M}(n,R)\{\mathrm{}\}`$ extends to $`\mathrm{M}(n,Q)`$. As $`\mathrm{deg}`$ has a unique extension from $`R`$ to $`Q`$, we find that $`f=\mathrm{deg}det`$ on $`\mathrm{D}(n,Q)`$. Since $`\mathrm{M}(n,Q)=\mathrm{D}(n,Q)\mathrm{M}(n,R)`$, there can at most be one extension of $`f`$. It is a straightforward computation to show that the extension given by $`f(DA)=f(D)+f(A)`$ with $`D\mathrm{D}(n,Q)`$ and $`A\mathrm{M}(n,R)`$ is a well-defined semigroup homomorphism. Observe that this unique lift $`f:\mathrm{M}(n,Q)\{\mathrm{}\}`$ has to factor over $`det:\mathrm{M}(n,Q)Q^{\mathrm{ab}}`$. Because $`\mathrm{D}(n,Q)`$ maps surjectively to $`Q^{\mathrm{ab}}`$ and $`f`$ coincides with $`\mathrm{deg}det`$ on $`\mathrm{D}(n,Q)`$, we conclude that $`f=\mathrm{deg}det`$.

Step 2. Given a matrix $`A\mathrm{M}(n,R)`$, consider the quotient of left $`R`$-modules $`R^n/R^nA`$. It is a vector space over $`k`$. Now define

$$f:\mathrm{M}(n,R)\{\mathrm{}\}:Adim_kR^n/R^nA.$$

Because $`f(AB)=f(A)+f(B)`$ and because $`f(D)=\mathrm{deg}det(D)`$ for diagonal matrices $`D`$, we conclude that $`f=\mathrm{deg}det`$ on all of $`\mathrm{M}(n,R)`$. But $`f`$ takes values in $`\{\mathrm{}\}`$ and $`\mathrm{ker}f=\mathrm{GL}(n,R)`$. This finishes the proof. ∎

## 2. Applications

By interpreting the skew polynomial ring, we can apply the main result to two special cases. The first has a trivial derivation, the second a trivial field endomorphism.

### 2.1. Endomorphisms of $`𝔾_a^n`$ in characteristic $`p>0`$

Let $`k`$ be a field of characteristic $`p>0`$. Denote by $`𝔾_a`$ the additive (algebraic) group over $`k`$. Its ring of endomorphisms is known to be the skew polynomial ring $`R=k[\tau ;aa^p,0]`$. Here $`ak`$ acts on $`𝔾_a`$ by multiplication with $`a`$ and $`\tau `$ acts as the $`p`$-th power frobenius. More generally, we have a canonical isomorphism

$$\mathrm{End}(𝔾_a^n)=\mathrm{M}(n,R).$$

Given a $`\varphi \mathrm{End}(𝔾_a^n)`$, its kernel is a closed subgroup scheme with an $`𝔽_p`$-linear structure. We can now determine its size.

###### Corollary 2.1.

If $`\mathrm{deg}det\varphi <\mathrm{}`$ then $`\mathrm{ker}\varphi `$ is a closed subgroup scheme of $`𝔾_a^n`$ which is finite of rank $`p^{\mathrm{deg}det\varphi }`$ over $`\mathrm{Spec}(k)`$.

###### Proof.

Consider the function $`f:\mathrm{End}(𝔾_a^n)p^{}\{\mathrm{}\}`$ that associates with $`\varphi `$ the rank of $`\mathrm{ker}\varphi `$ whenever this kernel is finite and $`\mathrm{}`$ when it is not. One readily checks that $`f`$ is multiplicative and that $`f`$ coincides with $`p^{\mathrm{deg}det}`$ for diagonal $`\varphi `$. The result now follows from theorem 1.1. ∎

###### Remark 2.2 (Anderson abelian $`t`$-modules).

In the theory of Anderson $`t`$-motives (\[Anderson 1986\]) one considers 2 types of objects. They roughly look as follows. The first object is an *abelian $`t`$-module of dimension $`n`$* and is an action of $`𝔽_p[t]`$ on $`𝔾_a^n/k`$. The second object, called a *$`t`$-motive of dimension $`n`$ and rank $`r`$* is a module over $`R_{𝔽_p}𝔽_p[t]`$, which has rank $`n`$ over $`R=k[\tau ;aa^p]`$ and rank $`r`$ over $`k𝔽_p[t]`$. The motives are in some sense dual to the modules and one proves that these objects actually form anti-equivalent categories. After this has been proven, one defines the *rank* of an abelian $`t`$-module to be the rank of its associated $`t`$-motive.

However, no straightforward description of the rank of an abelian $`t`$-module, other than the rank of its associated motive, seemed to be known for $`n>1`$. When $`n=1`$ we are dealing with Drinfel’d modules and a very simple description in terms of the degree of the endomorphisms acting on $`𝔾_a`$ is known. Corollary 2.1 shows that $`\mathrm{deg}det`$ is the sought generalization of this degree function and gives the following desctiption. The rank of the abelian $`t`$-module given by

$$\varphi :𝔽_p[t]\mathrm{End}(𝔾_a^n/k)=\mathrm{M}(n,R),$$

is the constant $`r`$ which satisfies

$$(f𝔽_p[t])(\mathrm{deg}det\varphi (f)=r\mathrm{deg}f).$$

### 2.2. Systems of linear ordinary differential equations

Details on the algebraic theory of differential equations can be found in the book \[van der Put - Singer 2003\].

Let $`k`$ be a differential field of characteristic $`0`$. This means $`k`$ is equipped with an additive map (called derivation) $`kk:aa^{}`$ satisfying $`(ab)^{}=a^{}b+ab^{}`$. Let $`Ck`$ be the field of constants, that is the kernel of the derivation. Assume that the derivation is non-trivial, i.e. $`Ck`$. Examples are $`k=(x)`$ and $`k=((x))`$ with the usual derivation. Now consider the skew polynomial ring $`R=k[;1,^{}]`$ with center $`C`$. It acts $`k`$-linearly on differential field extensions of $`k`$ by $`a=a^{}`$.

A homogeneous matrix differential equation of the form

$$A_0y+A_1y^{}+\mathrm{}+A_dy^{(d)}=0$$

where $`y`$ denotes a vector in $`k^n`$ and the $`A_i`$ are matrices in $`\mathrm{M}(n,k)`$ can be rewritten as

$$Ay=0$$

with $`A=A_i^i\mathrm{M}(n,R)`$. Conversely, every $`A`$ corresponds to such a differential equation. Note that we do not demand $`A_d`$ to be invertible.

As in the proof of theorem 1.1, we associate with $`A`$ the $`R`$-module

$$M:=R^n/R^nA=R^sM_{\mathrm{tors}}$$

Take $`kl`$ to be the Picard-Vessiot extension of $`M_{\mathrm{tors}}`$, or alternatively, take $`l`$ to be a universal differential field extension of $`k`$. When $`s=0`$, all solutions of the differential equation exist over $`l`$. The *contravariant solution space* $`V`$ of $`M`$ is defined to be the $`C`$-vector space

$$V:=\mathrm{Hom}_R(M,l).$$

It is finite-dimensional if and only if $`s=0`$, and in that case it is dual to the $`C`$-space of solutions in $`l^n`$ of the given differential equation. On its dimension, we conclude:

###### Corollary 2.3.

With the notations as above, we have

$$dim_CV=dim_kM=\mathrm{deg}detA.$$

###### Remark 2.4.

Completely analogous results hold for difference and $`q`$-difference equations.


text:
# 1 Introduction

## 1 Introduction

A coin toss with bias $`\theta `$ is a $`\{1,1\}`$-valued random variable with expected value $`\theta `$, and a fair coin is a coin toss with bias zero.

Harris and Keane \[HK97\] introduced a model for sequences of coin tosses with a particular kind of dependence. Let $`S=\{S_n\}_{n=0}^{\mathrm{}}`$ be simple random walk on $``$. Suppose that whenever $`S_n=0`$, an independent coin with bias $`\theta 0`$ is tossed, while at all other times an independent fair coin is tossed. Suppose that we are given $`X=\{X_n\}_{n=0}^{\mathrm{}}`$, the record of coin tosses obtained, but the path of the walker, $`S`$, is hidden from us. Can $`X`$ be distinguished from a sequence of i.i.d. fair coin tosses?
If it can be distinguished, can the parameter $`\theta `$ be recovered, again only from $`X`$?

Harris and Keane proved the following:

###### Theorem (\[HK97, Theorem 2\]).

There exist a sequence of functions $`\mathrm{\Theta }_n:\{1,1\}^n`$, not depending on $`\theta `$, so that $`lim_n\mathrm{}\mathrm{\Theta }_n(X_1,\mathrm{},X_n)=\theta `$ almost surely.

In fact, the model in \[HK97\] is more general, allowing the walk to be any null-recurrent Markov chain. Let $`\mu _\theta `$ be the distribution of $`X`$ on $`\{1,1\}^{}`$. Recall that two Borel measures are mutually singular if there is a Borel set which is null for one measure such that its complement is null for the other measure; in this case the measures are distinguished by almost any observation. Whether or not $`\mu _\theta `$ and $`\mu _0`$ are mutually singular depends on the graph, and as was shown in \[LPP01\], sometimes on the bias $`\theta `$. \[HK97\] provides a partial criterion for determining singularity based on the graph, while the full story – in particular the role of $`\theta `$ for certain graphs – is completed in \[LPP01\].

In this paper, this model is generalized in a different direction. Label each $`z`$ with $`\theta (z)[0,1]`$. Now allow a random walker to move on $``$, and suppose that on her $`n`$th move she is at position $`S_n`$ and she tosses a coin with bias $`\theta (S_n)`$, generating the random variable $`X_n`$. Again, the path of the walker, $`\{S_n\}_{n=0}^{\mathrm{}}`$ is not observed, and the output is only the outcomes of the coin tosses, that is, $`\{X_n\}_{n=0}^{\mathrm{}}`$. The main result of this paper says that the biases $`\{\theta (z):z\}`$ can be recovered, up to a shift and reflection of $``$, in the case when the number of vertices with $`\theta (z)0`$ is finite:

###### Theorem 1.1.

Suppose that attached to each site $`z`$ is a coin with bias $`\theta (z)`$, and only finitely many of these coins have non-zero bias. Allow a simple random walker to generate observations by tossing, at each move, the coin attached to its current position. Then it is possible to determine the biases $`\{\theta (z)\}_z`$, up to a shift and reflection of $``$, using only a single observation of the infinite sequence of these coin tosses and no information about the path of the random walker.

Another related model was introduced by Benjamini and Kesten \[BK96\] (and independently, by Den Hollander and Keane). Instead of attaching a coin with bias $`\theta (z)`$ to each $`z^d`$, a fixed color is assigned to each vertex. The random walker reports only the sequence of colors visited, while just as in our generalization of the Harris-Keane model, the path itself is hidden. Further investigations of the model introduced in \[BK96\] can be found in \[How96a, How96b, Lin99, LM02, LM03, Ma99, MR03a, MR03b\] and a survey of results (up to 1998) can be found in \[Kes98\].

This paper is organized as follows. Theorem 1.1 holds more generally, where the observed random variables are not restricted to be coin tosses. Some definitions and the statement of the more general Theorem 2.3 can be found in Section 2. The main requirements of the proof of this theorem are a strong law of large numbers, and some algebraic results, found in Section 3. Because the special case of coin tosses is more readily understood, a separate proof of Theorem 1.1 is supplied, after which Theorem 2.3 is proven, both in Section 4. Finally, some unsolved problems are mentioned in Section 5.

## 2 Definitions and Statement of Result

Let $`q`$ be a probability mass function on $``$, and $`q^n`$ its $`n`$-fold convolution. Assume that

$$\underset{z}{}zq(z)=0\text{and}\underset{z}{}z^2q(z)<\mathrm{}.$$
(1)
Also, we will assume that $`q`$ is symmetric:

$$q(z)=q(z)\text{ for all }z.$$
(2)
In addition, to simplify the exposition we will suppose that

$$\mathrm{g}.\mathrm{c}.\mathrm{d}.\{n:q^n(0)>0\}=1.$$
(3)
###### Remark.

Condition (3) rules out, for example, $`q=\frac{1}{2}\delta _1+\frac{1}{2}\delta _{+1}`$, the mass function corresponding to the increments of simple random walk on $``$. However, the results in this paper (in particular, Theorem 2.3) can be obtained for periodic random walks by considering the process observed at times $`\{rn+k:n\}`$, where $`r`$ is the period (the left-hand side of (3)).

The random walk with increments distributed according to $`q`$ will be denoted $`S=\{S_n\}_{n=0}^{\mathrm{}}`$:

$$[S_{n+1}S_n=zS_0,\mathrm{},S_n]=q(z).$$

We use the notation $`P^n(z,w)\stackrel{def}{=}[S_n=wS_0=z]`$ and $`u_n\stackrel{def}{=}P^n(0,0)`$.

###### Definition 2.1.

A stochastic scenery is a map $`\eta :𝒫()`$, where $`𝒫()`$ is the set of all probability measures on $``$.

We assume that there is a known reference distribution $`\alpha 𝒫()`$ which appears everywhere but finitely many vertices: that is,

$$|\eta ^1(𝒫\{\alpha \})|<\mathrm{}.$$
(4)
###### Definition 2.2.

The sequence of observations induced by $`S`$ and $`\eta `$ is the stochastic process $`X=\{X_n\}_{n=0}^{\mathrm{}}`$, whose law conditioned on $`S`$ has independent marginal distributions given by $`[X_nS]=\eta (S_n)`$.

###### Theorem 2.3.

For a random walk $`S`$ with symmetric increment distribution $`q`$ satisfying (1) and (3), and stochastic scenery $`\eta `$ obeying (4), let $`X=\{X_n\}_{n=0}^{\mathrm{}}`$ be the observations induced by $`S`$ and $`\eta `$. Then using only the observations $`\{X_n\}_{n=0}^{\mathrm{}}`$, we can determine a scenery $`\widehat{\eta }`$ so that

$$\widehat{\eta }=\eta T\text{a.s.},$$

where $`T:`$ is either a shift or a shift composed with a reflection, and may depend on $`\eta `$.

###### Remark.

As noted by a referee, if we are given an infinite sequence of observations then we do not need to be given the reference distribution $`\alpha `$, as it can be a.s. reconstructed from the observations.

## 3 A few ingredients

In this section, we first state Proposition 3.2, which shows how the observations $`\{X_n\}`$ can be used to determine a family of parameters $`\{p_𝒕\}`$. We show in Proposition 3.7 that we can express a new family of parameters $`\{Q_𝒅^k\}`$ as functions of $`\{p_𝒕\}`$. These new parameters determines the scenery $`\eta `$, and hence the scenery can be recovered from the observations $`\{X_n\}`$. (This is the substance of the proofs of Theorem 1.1 and Theorem 2.3 in Section 4.) We conclude the present section with a proof of Proposition 3.2.

###### Definition 3.1.

1. For a vector $`𝒕^k`$ (where $`k`$), and a bounded and measurable $`\phi :`$, define

$$p_𝒕(\phi )\stackrel{def}{=}\underset{z}{}𝔼[\phi (X_0)\phi (X_{t_1})\phi (X_{t_1+t_2})\mathrm{}\phi (X_{t_1+\mathrm{}+t_k})S_0=z].$$
2. For $`r`$, let $`𝒑^k(\phi )`$ be the vector with components

$$\{p_𝒕(\phi ):𝒕\{1,\mathrm{},r\}^k\}.$$

For measurable functions $`\phi `$, we will use the supremum norm $`\phi _{\mathrm{}}`$. When we know that all the measures $`\eta (z)`$ are supported on a common set $`E`$, we will take this norm to be the essential supremum over $`E`$. For example, when we are dealing with coin tosses only, $`\phi _{\mathrm{}}1`$ means that $`\phi `$ is bounded by $`1`$ on $`\{1,1\}`$, a condition satisfied by $`\phi (x)=x`$.

###### Proposition 3.2.

Fix a measurable function $`\phi `$ with $`\phi _{\mathrm{}}1`$ and $`_{}\phi 𝑑\alpha =0`$, and a vector $`𝐭^s`$. Then there exists a sequence $`\{g_N\}`$ of measurable functions, $`g_N:^N,`$ not depending on the stochastic scenery $`\eta `$, with

$$\underset{N\mathrm{}}{lim}g_N(X_1,\mathrm{},X_N)=p_𝒕(\phi )\text{almost surely}.$$

The information in the collection $`\{p_𝒕\}`$ must be transformed into a more useful form for us to recover the stochastic scenery $`\eta `$. We provide now several results enabling this transformation.

###### Lemma 3.3.

For a given transition semigroup $`P^t`$, and $`m,r`$, define the matrix $`𝐌`$ as

$$𝑴\stackrel{def}{=}\left[\begin{array}{cccc}P^1(0,0)\hfill & P^1(0,1)\hfill & \mathrm{}\hfill & P^1(0,m)\hfill \\ P^2(0,0)\hfill & P^2(0,1)\hfill & \mathrm{}\hfill & P^2(0,m)\hfill \\ \mathrm{}\hfill & \mathrm{}\hfill & \mathrm{}\hfill & \mathrm{}\hfill \\ P^r(0,0)\hfill & P^r(0,1)\hfill & \mathrm{}\hfill & P^r(0,m)\hfill \end{array}\right].$$
(5)
Let $`S`$ be an aperiodic and symmetric random walk on $``$, whose increments have probability mass function $`q`$: that is, $`[S_{t+1}=zS_t=w]=q(zw)`$.

1. If $`P^t`$ is the transition semigroup for $`S`$, then $`𝑴`$ has rank $`(m+1)`$ for some $`r`$.
2. If $`S`$ is the simple random walk on $``$, and $`P^t(0,z)=[S_{2t}=2z]`$, then any $`(m+1)\times (m+1)`$ square submatrix of $`𝑴`$ is non-singular.

###### Proof.

If $`\psi `$ is the characteristic function of $`q`$, so that $`\psi ^t`$ is the characteristic function of the $`t`$th convolution power of $`q`$, then by Fourier inversion

$$\begin{array}{cc}\hfill \frac{1}{2\pi }_\pi ^\pi \mathrm{cos}(uj)\psi ^t(u)𝑑u& =2[S_t=j].\hfill \end{array}$$
(6)
Suppose that for each $`r`$, the $`m+1`$ columns of $`𝑴`$ are linearly dependent, that is, there exist $`\{a_j(r)\}_{j=0}^m`$ (not all zero) so that

$$\underset{j=0}{\overset{m}{}}a_j(r)P^t(0,j)=0\text{ for all }tr.$$

By rescaling, it can be assumed that $`_{j=0}^ma_j(r)^2=1`$. Thus there exist subsequential limits $`\{a_j\}_{j=0}^m`$ (not all zero) so that

$$\underset{j=0}{\overset{m}{}}a_jP^t(0,j)=0\text{ for all }t.$$
(7)
Hence, the matrix $`𝑴`$ in (5) fails to have rank $`(m+1)`$ for any $`r`$ if and only if there exist $`\{a_j\}_{j=0}^m`$ satisfying (7). By (6), this is the same as

$$_\pi ^\pi g(u)\psi ^t(u)𝑑u=0\text{ for all }t,$$
(8)
where $`g(u)=_{j=0}^ma_j\mathrm{cos}(uj)`$. We now show that (8) cannot hold:

Observe that $`g`$ is an even function that is non-zero in a neighborhood of $`0`$, except possibly at $`0`$. It can be assumed without loss of generality (by multiplying the coefficients $`a_j`$ by $`1`$) that $`g`$ is non-negative near $`0`$. Also $`\psi `$ is even, has value $`1`$ at the origin, and is positive in a neighborhood $`[\delta ,\delta ]`$ of $`0`$.

Choose $`\delta _1<\delta `$ so that

$$B\stackrel{def}{=}\underset{|u|\delta _1}{\mathrm{min}}\psi (u)>\underset{\delta <|u|\pi }{\mathrm{max}}\psi (u)\stackrel{def}{=}A$$

This is possible because, as $`\psi `$ is a characteristic function of an aperiodic distribution, $`A<1`$. Choose $`\delta _1`$ even smaller to ensure $`\mathrm{min}_{\frac{\delta _1}{2}|u|\delta _1}g(u)=ϵ>0`$. Hence

$`{\displaystyle _\pi ^\pi }g(u)\psi ^t(u)𝑑u`$ $`={\displaystyle _\delta ^\delta }g(u)\psi ^t(u)𝑑u+{\displaystyle _{[\pi ,\pi ][\delta ,\delta ]}}g(u)\psi ^t(u)𝑑u`$
$`{\displaystyle _{\delta _1/2}^{\delta _1}}g(u)\psi ^t(u)𝑑u+{\displaystyle _{[\pi ,\pi ][\delta ,\delta ]}}g(u)\psi ^t(u)𝑑u`$
$`{\displaystyle \frac{\delta _1}{2}}ϵB^tg_{\mathrm{}}2\pi A^t.`$ (9)
For $`t`$ large enough, the right-hand side of (9) is positive, contradicting (8). Thus the matrix (5) has rank $`(m+1)`$ when $`r`$ is sufficiently large, proving (i).

We now discuss the special case of simple random walk. Suppose there exist $`a_0,\mathrm{},a_m`$ and $`t_0,t_1,\mathrm{},t_m2`$ so that for $`t=t_0,\mathrm{},t_m`$,

$$\underset{k=0}{\overset{m}{}}a_k[S_{2t}=2k]=0.$$

Then

$$\underset{k=0}{\overset{m}{}}a_k\frac{(2t)!}{(tk)!(t+k)!}=0.$$
(10)
Multiplying both sides of (10) by $`\frac{(t+m)!t!}{(2t)!}`$ yields

$$0=\underset{k=0}{\overset{m}{}}a_k(t+m)\mathrm{}(t+k+1)t\mathrm{}(tk+1).$$
(11)
If $`f_k(x)\stackrel{def}{=}(x+m)\mathrm{}(x+k+1)x\mathrm{}(xk+1)`$, then (11) shows that

$$f(x)\stackrel{def}{=}\underset{k=0}{\overset{m}{}}a_kf_k(x)=0\text{ for }x=t_0,\mathrm{},t_m.$$
(12)
Since $`f`$ is a polynomial of degree $`m`$, and by (12) $`f`$ has $`m+1`$ zeros, it follows that $`f0`$. But $`f(m)=0`$ implies $`a_m=0`$.

Multiplying both side of (10) by $`\frac{(t+m1)!t!}{(2t)!}`$ and arguing as above shows that $`a_{m1}=0`$. Repeating this procedure shows that $`a_k=0`$ for all $`k`$, establishing (ii). ∎

###### Remark 1.

We have suppressed the dependence of the $`r\times (m+1)`$ matrix $`𝑴`$ on both $`m`$ and $`r`$. For each $`m`$, fix an $`r_m`$ so that $`𝑴`$ has rank $`(m+1)`$. In the sequel, the matrix $`𝑴`$ will depend only on $`m`$, having dimension $`r_m\times (m+1)`$. We will write $`r`$ for $`r_m`$.

We now introduce some notation:

###### Definition 3.4.

For any function $`\phi :`$, define

$$\overline{\phi }(z)\stackrel{def}{=}_{}\phi 𝑑\eta (z),\text{and}\phi _0\stackrel{def}{=}\phi _{}\phi 𝑑\alpha .$$
(13)
(Recall that $`\eta (z)𝒫()`$.)

The parameters $`\{𝑸^k(\phi )\}`$ which will be used in the reconstruction of the scenery are now defined:

###### Definition 3.5.

For $`\phi `$ a bounded measurable function and $`k`$, define the vector $`𝑸^k(\phi )^{[m]^k}`$, indexed by $`𝒅[m]^k`$, by

$$Q_𝒅^k(\phi )\stackrel{def}{=}\underset{\begin{array}{c}(z_1,\mathrm{},z_{k+1})\\ |z_jz_{j1}|=d_j\end{array}}{}\overline{\phi }(z_1)\overline{\phi }(z_2)\mathrm{}\overline{\phi }(z_{k+1}).$$
(14)
(Here $`[m]\stackrel{def}{=}\{0,1\mathrm{},m\}`$.)

Assumption (4) of Theorem 2.3 requires that the stochastic scenery $`\eta `$ differs from a reference distribution $`\alpha `$ at only finitely many vertices. With this in mind, we make the following definitions:

###### Definition 3.6.

Let

$$a\stackrel{def}{=}inf\{j:\eta (j)\alpha \},b\stackrel{def}{=}sup\{j:\eta (j)\alpha \},\text{and}\mathrm{}\stackrel{def}{=}ba.$$
(15)
By assumption (4), $`\mathrm{}<ab<\mathrm{}`$.

Finally, we state the main algebraic result used in the proof of Theorem 2.3:

###### Proposition 3.7.

If $`m\mathrm{}`$ and $`\phi 𝑑\alpha =0`$, then $`𝐐^k(\phi )^{[m]^k}`$ is a linear transformation of $`𝐩^k(\phi )^{r^k}`$ (defined in Definition 3.1.)

###### Proof.

Let us begin with the case of $`k=1`$. Let $`𝑴`$ be the matrix in (5), and $`𝑴^{}`$ its left inverse, shown to exist in Lemma 3.3.

We have

$`p_t(\phi )`$ $`={\displaystyle \underset{z}{}}𝔼[\phi (X_t)\phi (X_0)S_0=z]`$
$`={\displaystyle \underset{z}{}}{\displaystyle \underset{w}{}}𝔼[\phi (X_t)\phi (X_0)S_0=z,S_t=w][S_t=wS_0=z]`$
$`={\displaystyle \underset{d}{}}P^t(0,d){\displaystyle \underset{\begin{array}{c}(z,w)\\ zw=d\end{array}}{}}\overline{\phi }(z)\overline{\phi }(w).`$ (16)
Because $`q`$ is symmetric, we have $`P^t(0,d)=P^t(0,d)`$, and hence from (16) we conclude that

$$p_t(\phi )=\underset{d=0}{\overset{\mathrm{}}{}}P^t(0,d)\underset{\begin{array}{c}(z,w)\\ |zw|=d\end{array}}{}\overline{\phi }(z)\overline{\phi }(w).$$

If $`dm`$, then $`d\mathrm{}`$ and the factor $`_{|zw|=d}\overline{\phi }(z)\overline{\phi }(w)`$ vanishes, so we have

$$p_t(\phi )=\underset{d=0}{\overset{m}{}}M_{t,d}Q_d^1(\phi ).$$
(17)
Using Definition 3.1, we rewrite the collection of $`r`$ equations (17) as

$$𝒑^1(\phi )=𝑴𝑸^1(\phi ).$$
(18)
Multiplying both sides of (18) on the left by $`𝑴^{}`$ yields $`𝑸^1(\phi )=𝑴^{}𝒑^1(\phi )`$.

Now consider the case $`k=2`$. We have

$`p_{(t_1,t_2)}(\phi )`$ $`={\displaystyle \underset{z,w,v}{}}𝔼[\phi (X_{t_1+t_2})\phi (X_{t_1})\phi (X_0)S_0=z,S_{t_1}=w,S_{t_2}=v]`$
$`\times P^{t_1}(0,wz)P^{t_2}(0,vw)`$
$`={\displaystyle \underset{z,w,v}{}}\overline{\phi }(z)\overline{\phi }(w)\overline{\phi }(v)P^{t_1}(0,wz)P^{t_2}(0,vw)`$
$`={\displaystyle \underset{d_1=\mathrm{}}{\overset{\mathrm{}}{}}}{\displaystyle \underset{d_2=\mathrm{}}{\overset{\mathrm{}}{}}}P^{t_1}(0,d_1)P^{t_2}(0,d_2){\displaystyle \underset{\begin{array}{c}(z,w,v)\\ wz=d_1,vw=d_2\end{array}}{}}\overline{\phi }(z)\overline{\phi }(w)\overline{\phi }(v)`$
$`={\displaystyle \underset{d_1=0}{\overset{\mathrm{}}{}}}{\displaystyle \underset{d_2=0}{\overset{\mathrm{}}{}}}P^{t_1}(0,d_1)P^{t_2}(0,d_2){\displaystyle \underset{\begin{array}{c}(z,w,v)\\ |wz|=d_1,|vw|=d_2\end{array}}{}}\overline{\phi }(z)\overline{\phi }(w)\overline{\phi }(v).`$
Again, since $`_{|zw|=d_1,|wv|=d_2}\overline{\phi }(z)\overline{\phi }(w)\overline{\phi }(v)`$ vanishes for $`d_1d_2>m\mathrm{}`$, we have

$$p_{(t_1,t_2)}(\phi )=\underset{d_1=0}{\overset{m}{}}\underset{d_2=0}{\overset{m}{}}P^{t_1}(0,d_1)P^{t_2}(0,d_2)\underset{\begin{array}{c}(z,w,v)\\ |zw|=d_1,\\ |wv|=d_2\end{array}}{}\overline{\phi }(z)\overline{\phi }(w)\overline{\phi }(v).$$
(19)
Recall that the tensor product of the matrix $`𝑴`$ in (5) with itself is given by

$$𝑴𝑴=\left[\begin{array}{ccc}M_{1,0}𝑴\hfill & \mathrm{}& M_{1,m}𝑴\hfill \\ \mathrm{}\hfill & \mathrm{}& \mathrm{}\hfill \\ M_{r,0}𝑴\hfill & \mathrm{}& M_{r,m}𝑴\hfill \end{array}\right].$$

There are $`r^2`$ rows, indexed by $`𝒕\{(t_1,t_2):\mathrm{\hspace{0.33em}1}t_1,t_2r\}`$, and $`(m+1)^2`$ columns indexed by $`𝒅[m]^2=\{(d_1,d_2):d_i=0,1,\mathrm{},m\}`$. Each row is of the form

$$\left(P^{t_1}(0,d_1)P^{t_2}(0,d_2)\right)_{d_1,d_2=0}^m.$$

Thus we can rewrite the equations (19) for $`𝒕[r]^2`$ compactly as

$$𝒑^2(\phi )=\left(𝑴𝑴\right)𝑸^2(\phi ).$$

Because each $`𝑴`$ has rank $`(m+1)`$, the matrix $`𝑴𝑴`$ has rank $`(m+1)^2`$ (see \[HJ91, Theorem 4.2.15\]). Thus there is a left inverse $`(𝑴𝑴)^{}`$ to $`𝑴𝑴`$ and we can write

$$𝑸^2(\phi )=(𝑴𝑴)^{}𝒑^2(\phi ).$$

In general, $`𝑴^k`$ has rank $`(m+1)^k`$, and hence has a left inverse, enabling us to write

$$𝑸^k(\phi )=\left(𝑴^k\right)^{}𝒑^k(\phi ).$$
(20)
###### Remark 2.

The vectors $`𝒑^k(\phi )`$ depend on the constant $`r`$ (see Definition 3.1), which we have taken to be the constant $`r_m`$ defined in Remark 1. Thus these vectors depend on $`m`$, although we have again suppressed this dependence in the notation.

###### Lemma 3.8.

Let $`\mathrm{}`$ be the constant given in Definition 3.6. Then there exists a sequence of random variables $`\{\mathrm{}_n\}_{n=0}^{\mathrm{}}`$, not depending on $`\eta `$, with $`\mathrm{}_n`$ measurable with respect to $`\sigma (X_1,\mathrm{},X_n)`$, and so that $`\mathrm{}_n=\mathrm{}`$ eventually, a.s.

Recall that a class $`\mathrm{\Phi }`$ of measurable functions on $``$ is said to be measure determining if $`_{}\phi 𝑑\mu =_{}\phi 𝑑\nu `$ for each $`\phi \mathrm{\Phi }`$ implies $`\mu =\nu `$. Let $`\mathrm{\Phi }`$ be a countable measure determining class of functions on $``$ with $`\phi _{\mathrm{}}1`$. We will enumerate $`\mathrm{\Phi }`$ as $`(\phi _1,\phi _2,\mathrm{})`$. Also define $`\mathrm{\Phi }_1\stackrel{def}{=}\{\frac{f+cg}{f+cg_{\mathrm{}}}:f,g\mathrm{\Phi },c\}`$, and enumerate its elements as $`(h^1,h^2,\mathrm{})`$.

###### Lemma 3.9.

Let $`\mu `$ and $`\nu `$ be two probability measures, neither equal to $`\alpha `$. Recall that $`\psi _0=\psi \psi 𝑑\alpha `$. If $`\mu \nu `$, there exists $`\psi \mathrm{\Phi }_1`$ with

$$\psi _0𝑑\mu 0,\psi _0𝑑\nu 0,\text{and}\psi _0𝑑\mu \psi _0𝑑\nu .$$
(21)
###### Proof.

Because $`\mu \nu `$ and $`\mathrm{\Phi }`$ is measure determining, there is an $`f\mathrm{\Phi }`$ so that $`f𝑑\mu f𝑑\nu `$. By subtracting $`f𝑑\alpha `$, we have $`f_0𝑑\mu f_0𝑑\nu `$. Then one of $`f_0𝑑\mu `$ and $`f_0𝑑\nu `$ is nonzero; without loss of generality assume $`f_0𝑑\mu 0`$. Similarly, there is a $`g\mathrm{\Phi }`$ so that $`g𝑑\nu g𝑑\alpha `$, that is, $`g_0𝑑\nu 0`$.

Hence, for small enough $`c`$, we have

$$f_0𝑑\mu +cg_0𝑑\mu 0,\text{ and }f_0𝑑\nu +cg_0𝑑\nu 0.$$
(22)
By taking $`c`$ even smaller, since $`f_0𝑑\mu f_0𝑑\nu `$, we have

$$f_0𝑑\mu +cg_0𝑑\mu f_0𝑑\nu +cg_0𝑑\nu .$$
(23)
Thus, if $`\psi =\frac{f+cg}{f+cg_{\mathrm{}}}`$, so that $`\psi _0=\frac{f_0+cg_0}{f+cg_{\mathrm{}}}`$, we have from (22) and (23) that $`\psi `$ obeys (21). ∎

We can now proceed with the proof of Lemma 3.8:

###### Proof of Lemma 3.8.

As before, let $`𝑴^{}`$ be the left inverse to the matrix $`𝑴`$ in (5).

Let $`\mathrm{}^h\stackrel{def}{=}sup\{|zw|:\overline{h_0}(z)\overline{h_0}(w)0\}`$. Recall that $`(h^1,h^2,\mathrm{})`$ is an enumeration of $`\mathrm{\Phi }_1`$, and write $`\mathrm{}^j`$ for $`\mathrm{}^{h^j}`$. Lemma 3.9 guarantees that $`sup_{jr}\mathrm{}^j=\mathrm{}`$ for $`r`$ sufficiently large. Define

$$T(m,h)\stackrel{def}{=}\pi _{m+1}(𝑴^{}𝒑^1(h_0)),$$

where $`\pi _{m+1}`$ is the projection onto the $`m+1`$st coordinate.

Notice that

$$T(m,h)=\{\begin{array}{cc}_{|zw|=\mathrm{}^h}\overline{h_0}(z)\overline{h_0}(w)0\hfill & \text{if }m=\mathrm{}^h\hfill \\ 0\hfill & \text{if }m>\mathrm{}^h.\hfill \end{array}$$
(24)
By Proposition 3.2, there exists for each $`m`$ and $`j`$ a sequence of random variables $`\{T_r(m,j)\}_{r=1}^{\mathrm{}}`$ so that almost surely,

$$\underset{r\mathrm{}}{lim}T_r(m,j)=T(m,h^j).$$

Let $`\{s_n\}`$ be any sequence with $`lim_n\mathrm{}s_n=\mathrm{}`$. An examination of the proof of Proposition 3.2 shows that there are bounds on the variances of $`T_r(m,j)`$ uniform for $`ms_n`$ and $`js_n`$. In particular, there is a sequence $`f_r`$ with $`lim_r\mathrm{}f_r=0`$ so that

$$\underset{\begin{array}{c}1js_n\\ \mathrm{}^j<ms_n\end{array}}{sup}𝔼\left[T_r(m,j)^2\right]f_r.$$

We have

$`\left[{\displaystyle \underset{j=1}{\overset{s_n}{}}}{\displaystyle \underset{m=\mathrm{}^j+1}{\overset{s_n}{}}}\left\{T_r(m,j)>{\displaystyle \frac{1}{n}}\right\}\right]`$ $`s_n^2n^2\underset{\begin{array}{c}1js_n\\ \mathrm{}^j<ms_n\end{array}}{sup}𝔼\left[T_r(m,j)^2\right]`$
$`s_n^2n^2f_r.`$
Let $`\{B_n\}`$ be a sequence so that $`s_n^2n^2f_{B_n}`$ is summable. By Borel-Cantelli, almost surely

$$T_{B_n}(m,j)\frac{1}{n}\text{for }\mathrm{}^j<ms_n\text{ and }1js_n,\text{ eventually}.$$

Similarly, since $`lim_r\mathrm{}T_r(\mathrm{}^j,j)=T(\mathrm{}^j,j)0`$, we can take a subsequence of $`\{B_n\}`$, which we will continue to denote by $`\{B_n\}`$, so that almost surely

$$T_{B_n}(\mathrm{}^j,j)>\frac{1}{n}\text{for }1js_n,\text{ eventually}.$$

To summarize, the following holds almost surely: For $`n`$ sufficiently large, for all $`j=1,\mathrm{},s_n`$,

$$T_{B_n}(\mathrm{}^j,j)>n^1,\text{ while }T_{B_n}(m,j)n^1\text{ for }m=\mathrm{}^j+1,\mathrm{},s_n.$$

Consequently,

$$sup\{ms_n:T_{B_n}(m,j)>\frac{1}{n}\}=\mathrm{}^j\text{for }1js_n,$$

for $`n`$ sufficiently large. Finally,

$$\underset{js_n}{sup}sup\{ms_n:T_{B_n}(m,j)>\frac{1}{n}\}=\underset{js_n}{sup}\mathrm{}^j=\mathrm{}$$

for $`n`$ sufficiently large. \[Since $`sup_{jr}\mathrm{}^j=\mathrm{}`$ for all but finitely many $`r`$.\]

We still need a proof of Proposition 3.2; it is similar to the proof of \[LPP01, Theorem 6.1\]. Recall that $`u_n=P^n(0,0)`$. The only facts we need about $`P^n`$ are

$$\underset{n=0}{\overset{\mathrm{}}{}}u_n^2=\mathrm{},$$
(25)
and
$$\underset{n\mathrm{}}{lim}\frac{P^{nk}(z,w)}{P^{nj}(u,v)}=1\text{ for all }u,v,z,w\text{ and }j,k.$$
(26)
That the transition probabilities satisfy (25) and (26) is easily seen from a local central limit theorem, for example \[Woe00, Theorem 13.10\].

###### Proof of Proposition 3.2.

For

$$w(m,n)\stackrel{def}{=}\underset{k=m+1}{\overset{n}{}}u_k^2\text{and}Z_k\stackrel{def}{=}\phi (X_k)\phi (X_{k+t_1})\mathrm{}\phi (X_{k+t_1+\mathrm{}+t_s}),$$

define the linear estimator

$$L_{m,n}\stackrel{def}{=}\frac{1}{w(m,n)}\underset{k=m+1}{\overset{n}{}}u_kZ_k.$$
(27)
Notice that $`𝔼[L_{m,n}]=\frac{1}{w(m,n)}_{k=m+1}^nu_k^2p_{𝒕,k}(\phi )`$, where we define

$$p_{𝒕,k}\stackrel{def}{=}\underset{z}{}𝔼[Z_kS_k=z]\frac{P^k(0,z)}{u_k}.$$

Since $`lim_k\mathrm{}\frac{u_k}{P^k(0,z)}=1`$ for all $`z`$, it follows that $`lim_k\mathrm{}p_{𝒕,k}(\phi )=p_𝒕(\phi )`$ and

$$\underset{m\mathrm{}}{lim}𝔼[L_{m,n}]=p_𝒕(\phi ).$$
(28)
The strategy of the proof is to find sequences $`\{m_i\}`$ and $`\{n_i\}`$ so that

$$\underset{N\mathrm{}}{lim}\frac{1}{N}\underset{i=1}{\overset{N}{}}L_{m_i,n_i}=p_𝒕\left(\phi \right)\text{ almost surely}.$$
(29)
We prove (29) by showing that $`\mathrm{Cov}(Z_j,Z_k)`$ is small for $`|jk|`$ large, and consequently $`\mathrm{Cov}(L_{m_i,n_i},L_{m_\tau ,n_\tau })`$ is small for $`|i\tau |`$ large.

For $`𝒛^{s+1}`$ and $`j`$, define the event

$$H_𝒕(j,𝒛)\stackrel{def}{=}\{S_j=z_0,S_{j+t_1}=z_1,\mathrm{},S_{j+t_1+\mathrm{}+t_s}=z_s\}.$$
(30)
Then by conditioning on positions of $`S`$,

$$𝔼[Z_jZ_k]=\underset{𝒛,𝒘^{s+1}}{}𝔼[Z_jZ_kH_𝒕(j,𝒛)H_𝒕(k,𝒘)][H_𝒕(j,𝒛)H_𝒕(k,𝒘)]$$

Suppose that $`k>j+t_1+\mathrm{}+t_s`$. Notice that

$$𝔼[Z_jZ_kH_𝒕(j,𝒛)H_𝒕(k,𝒘)]=\underset{i=0}{\overset{s}{}}\overline{\phi }(z_i)\underset{j=0}{\overset{s}{}}\overline{\phi }(w_j),$$
(31)
and

$$\begin{array}{cc}\hfill [H_𝒕(j,𝒛)H_𝒕(k,𝒘)]& =P^j(0,z_0)[H_𝒕(j,𝒛)S_j=z_0]\hfill \\ & \times P^{k(j+t_1+\mathrm{}+t_s)}(z_s,w_0)[H_𝒕(k,𝒘)S_k=w_0].\hfill \end{array}$$
(32)
Combining (31) and (32) shows that $`𝔼[Z_jZ_k]`$ is equal to

$$\begin{array}{c}\underset{𝒛,𝒘^{s+1}}{}\left(\underset{i=0}{\overset{s}{}}\overline{\phi }(z_i)\underset{j=0}{\overset{s}{}}\overline{\phi }(w_j)\right)P^j(0,z_0)[H_𝒕(j,𝒛)S_j=z_0]\hfill \\ \hfill \times P^{k(j+t_1+\mathrm{}+t_s)}(z_s,w_0)[H_𝒕(k,𝒘)S_k=w_0].\end{array}$$
(33)
By similar reasoning, $`𝔼[Z_j]𝔼[Z_k]`$ is equal to

$$\begin{array}{c}\underset{𝒛,𝒘^{s+1}}{}\left(\underset{i=0}{\overset{s}{}}\overline{\phi }(z_i)\underset{j=0}{\overset{s}{}}\overline{\phi }(w_j)\right)P^j(0,z_0)[H_𝒕(j,𝒛)S_j=z_0]\hfill \\ \hfill \times P^k(0,w_0)[H_𝒕(k,𝒘)S_k=w_0].\end{array}$$

Because of the definitions of $`a`$ and $`b`$ in (15), if $`D|a||b|`$, then for any $`z`$ with $`|z|>D`$, we have $`\overline{\phi }(z)=0`$.

Thus if $`D|a||b|`$,

$$\begin{array}{cc}\hfill |\mathrm{Cov}(Z_j,Z_k)|& =\left|𝔼[Z_jZ_k]𝔼[Z_j]𝔼[Z_k]\right|\hfill \\ & \underset{\begin{array}{c}Dz_0D\\ Dz_sD\\ Dw_0D\end{array}}{}P^j(0,z_0)\left|P^{k(j+t_1+\mathrm{}+t_s)}(z_s,w_0)P^k(0,w_0)\right|,\hfill \end{array}$$
(34)
since $`\phi _{\mathrm{}}1`$.

For sequences $`\{m_i\}_{i=1}^{\mathrm{}}`$ and $`\{n_i\}_{i=1}^{\mathrm{}}`$ with $`m_i<n_i`$, define

$$L_i\stackrel{def}{=}L_{m_i,n_i}=\frac{1}{w(m_i,n_i)}\underset{j=m_i+1}{\overset{n_i}{}}u_jZ_j.$$
(35)
For any sequence $`\{ϵ_i\}`$, and integer $`D`$, we will inductively define sequences $`\{m_i\}`$ and $`\{n_i\}`$ so that for $`\tau >i`$,

$$\left|\mathrm{Cov}(L_i,L_\tau )\right|<Cϵ_i,$$
(36)
provided $`D|a||b|`$. For now, assume that $`D`$ is indeed chosen so that $`D|a||b|`$. To begin, let $`m_1=n_1=1`$. Now assume that the pair $`(m_i,n_i)`$ has already been defined. Pick $`m_{i+1}`$ large enough so that

$$\begin{array}{c}\text{if }jn_i\text{ and }k>m_{i+1},\text{then}\hfill \\ \hfill \left|P^{k(j+t_1+\mathrm{}+t_s)}(z,w)P^k(0,w)\right|C_1(D)ϵ_iu_k\text{ for all }Dz,wD.\end{array}$$
(37)
This is possible by (26).

Next, pick $`n_{i+1}`$ so that

$$w(m_{i+1},n_{i+1})w(m_{i+1}),$$
(38)
where $`w(m)\stackrel{def}{=}w(0,m)`$. Combining (34) and (37) shows that

$$|\mathrm{Cov}(Z_j,Z_k)|(2D)^3C_1(D)ϵ_iu_ju_k=C_2(D)ϵ_iu_ju_k$$
(39)
for $`j<n_i`$ and $`k>m_{i+1}`$.

From the definition (35) and the bound (39) we have

$$\begin{array}{cc}\hfill \left|\mathrm{Cov}(L_i,L_\tau )\right|& =\left|\frac{1}{w(m_i,n_i)}\frac{1}{w(m_\tau ,n_\tau )}\underset{j=m_i+1}{\overset{n_i}{}}\underset{k=m_\tau +1}{\overset{n_\tau }{}}u_ju_k\mathrm{Cov}(Z_j,Z_k)\right|\hfill \\ & \frac{1}{w(m_i,n_i)}\frac{1}{w(m_\tau ,n_\tau )}C_2(D)ϵ_i\underset{j=m_i+1}{\overset{n_i}{}}u_j^2\underset{k=m_\tau +1}{\overset{n_\tau }{}}u_k^2\hfill \\ & =C_2(D)ϵ_i.\hfill \end{array}$$

Next, we show that

$$\underset{i1}{sup}𝔼[L_i^2]<M<\mathrm{}.$$
(40)
Notice that

$$𝔼[L_i^2]\frac{1}{w(m_i,n_i)^2}\left\{2\underset{\begin{array}{c}m_i<jkn_i\\ |jk|t_1+\mathrm{}+t_s\end{array}}{}u_ju_k𝔼[Z_jZ_k]+2\underset{\begin{array}{c}m_i<j,kn_i\\ j+t_1+\mathrm{}+t_s<k\end{array}}{}u_ju_k𝔼[Z_jZ_k]\right\}$$
(41)
By (26), for each fixed $`k`$, we have $`lim_j\mathrm{}\frac{u_j}{u_{j+k}}=1`$, and hence $`u_{j+k}C_3u_j`$ for $`k=0,1,\mathrm{},t_1+\mathrm{}+t_s`$. Consequently, since $`\phi _{\mathrm{}}1`$ and hence $`Z_jZ_k1`$,

$$\underset{\begin{array}{c}m_i<jkn_i\\ |jk|t_1+\mathrm{}+t_s\end{array}}{}u_ju_k𝔼[Z_jZ_k](t_1+\mathrm{}+t_s)C_3\underset{j=m_i+1}{\overset{n_i}{}}u_j^2=C_4w(m_i,n_i).$$
(42)
Since $`𝔼[Z_jZ_k]`$ is equal to (33), we have

$$𝔼[Z_jZ_k]\underset{z_0=D}{\overset{D}{}}P^j(0,z_0)\underset{z_s=D}{\overset{D}{}}\underset{w_0=D}{\overset{D}{}}P^{k(j+t_1+\mathrm{}+t_s)}(z_s,w_0)C_5(D)u_ju_{kj},$$

again by (26). Thus,

$$2\underset{\begin{array}{c}m_i<j,kn_i\\ j+t_1+\mathrm{}+t_s<k\end{array}}{}u_ju_k𝔼[Z_jZ_k]C_6(D)\underset{j=m_i+1}{\overset{n_i}{}}u_j^2\underset{k=j+1}{\overset{n_i}{}}u_ku_{kj}.$$
(43)
Now applying the Cauchy-Schwarz inequality yields

$$\underset{k=j+1}{\overset{n_i}{}}u_ku_{kj}\sqrt{w(j,n_i)w(1,n_ij)}w(n_i).$$
(44)
Plugging (44) into (43) yields

$$2\underset{\begin{array}{c}m_i<j,kn_i\\ j+t_1+\mathrm{}+t_s<k\end{array}}{}u_ju_k𝔼[Z_jZ_k]C_6(D)w(n_i)w(m_i,n_i).$$
(45)
Then, using (45) and (42) in (41) yields

$$𝔼[L_i^2]\frac{C_4}{w(m_i,n_i)}+C_6(D)\frac{w(n_i)}{w(m_i,n_i)}.$$

Now, since by (38) $`w(m_i,n_i)w(m_i)`$, it follows that $`w(n_i)2w(m_i,n_i)`$. Hence,

$$𝔼[L_i^2]\frac{C_4}{w(m_i,n_i)}+2C_6(D)M,$$

where $`M`$ doesn’t depend on $`i`$.

If we choose $`ϵ_i=i^3`$, then a strong law for weakly correlated and centered random variables (see \[Loè78, Theorem 37.7.A\]) applied to the sequence $`\{L_i𝔼[L_i]\}_{i1}`$ implies that $`\frac{1}{N}_{i=1}^N\left(L_i𝔼[L_i]\right)0`$.

Thus, from (28), we have $`lim_i\mathrm{}𝔼[L_i]=p_𝒕(\phi )`$ and $`\frac{1}{N}_{i=1}^NL_ip_𝒕(\phi )`$.

To summarize, for each $`D`$ we get a sequence of functions $`\left\{g_N^D\right\}_{N=1}^{\mathrm{}}`$ so that

$$\text{if }D|a||b|,\text{ then }g_N^D(X_1,\mathrm{},X_N)\stackrel{N\mathrm{}}{}p_𝒕(\phi )\text{ a.s.}$$
(46)
By a diagonalization argument, there is a sequence of integers $`\{r_n\}`$ so that for each $`D`$, the limit $`A(D)\stackrel{def}{=}lim_ng_{r_n}^D(X_1,\mathrm{},X_{r_n})`$ exists, and moreover for each $`D`$,

$$|g_{r_n}^D(X_1,\mathrm{},X_{r_n})A(D)|<n^1\text{ for }nD.$$

From (46) it follows that $`A(D)=p_𝒕(\phi )`$ for $`D|a||b|`$, and consequently a.s.

$$g_{r_D}^D(X_1,\mathrm{},X_{r_D})\stackrel{D\mathrm{}}{}p_𝒕(\phi ).$$

## 4 Proofs of Theorem 1.1 and Theorem 2.3

Here is an outline of the proof of Theorem 2.3: In the last section, it was shown in Proposition 3.2 that the parameters $`\{p_𝒕\}`$ can be recovered from the data $`\{X_1,X_2,\mathrm{}\}`$. We transformed these parameters in Proposition 3.7 into the family $`\{Q_𝒅\}`$. Now we must show how to use this information to determine the laws $`\{\eta (z)\}`$.

Before we prove Theorem 2.3 in its full generality, we offer the proof of Theorem 1.1, the case where the observable random variables are coin tosses. The exposition is much clearer in this special case. The proof is given in its full generality later in this section.

Theorem 1.1. Let $`S`$ be a symmetric and aperiodic random walk, and label each $`z`$ with a coin having bias $`\theta (z)`$. If only finitely many vertices have $`\theta (z)0`$, then there exist a sequence $`\{\theta _n\}_{n=0}^{\mathrm{}}`$ with $`\theta _n`$ measurable with respect to $`\sigma (X_1,\mathrm{},X_n)`$, and a shift and reflection $`T`$ (depending on $`\eta `$) so that

$$\underset{n\mathrm{}}{lim}\theta _n(z)=\theta T(z)\text{ for all }z,\text{ a.s.}$$

Let us first introduce some notation.

###### Definition 4.1.

Let $`(x_1,x_2,\mathrm{},x_n)`$ be a finite, ordered sequence. Define $`[x_1,x_2,\mathrm{},x_n]`$ as

$$[x_1,x_2,\mathrm{},x_n]\stackrel{def}{=}\{(x_1,x_2,\mathrm{},x_n),(x_n,x_{n1},\mathrm{},x_1)\}.$$
(47)
###### Proposition 4.2.

Let $`\theta :[0,1]`$ have compact support. Then, given $`\mathrm{}=ba`$ as defined in (15),

$$[\theta (a),\theta (a+1),\mathrm{},\theta (b1),\theta (b)]$$
(48)
can be uniquely determined from $`\{𝐩^k(I)\}`$, where $`I`$ is the identity map.

###### Proof.

We will write $`Q_𝒅^k`$ for $`Q_𝒅^k(I)`$, where $`I`$ is the identity map.

By Proposition 3.7 it is enough to construct (48) using only $`\{𝑸^k\}`$.

Our method will be to first determine the biases at $`a`$ and $`b`$, and then work inwards.

In the case where $`k=1`$ and $`𝒅=(\mathrm{})`$, we have

$$\frac{1}{2}Q_{\mathrm{}}^1=\frac{1}{2}\underset{\begin{array}{c}(z_1,z_2)\\ |z_2z_1|=\mathrm{}\end{array}}{}\theta (z_1)\theta (z_2)=\theta (a)\theta (b),$$

as the only pairs $`(z_1,z_2)`$ with $`|z_2z_1|=\mathrm{}`$ and with $`\theta (z_1)\theta (z_2)0`$ are $`(a,b)`$ and $`(b,a)`$.

Notice that

$$Q_{(\mathrm{},\mathrm{})}^2=\underset{\begin{array}{c}(z_1,z_2,z_3)\\ |z_2z_1|=\mathrm{},\\ |z_3z_2|=\mathrm{}\end{array}}{}\theta (z_1)\theta (z_2)\theta (z_3)=\theta (a)\theta (b)\left\{\theta (a)+\theta (b)\right\},$$

and so $`\theta (a)+\theta (b)=2Q_{(\mathrm{},\mathrm{})}^2/Q_{\mathrm{}}^1`$. We can conclude that

$`\{\theta (a),\theta (b)\}`$ $`=\left\{{\displaystyle \frac{(\theta (a)+\theta (b))\pm \sqrt{(\theta (a)+\theta (b))^24\theta (a)\theta (b)}}{2}}\right\}`$
$`=\left\{Q_{(\mathrm{},\mathrm{})}^2/Q_{\mathrm{}}^1\pm \sqrt{\left(Q_{(\mathrm{},\mathrm{})}^2/Q_{\mathrm{}}^1\right)^2Q_{\mathrm{}}^1/2}\right\}.`$
Now we move on to the unordered pair $`\{\theta (a+1),\theta (b1)\}`$. Notice that

$$Q_{(\mathrm{},1)}^2=\underset{\begin{array}{c}(z_1,z_2,z_3)\\ |z_2z_1|=\mathrm{},\\ |z_3z_2|=1\end{array}}{}\theta (z_1)\theta (z_2)\theta (z_3)=\theta (a)\theta (b)\left\{\theta (a+1)+\theta (b1)\right\},$$

and

$`Q_{(\mathrm{},1,1,\mathrm{},1)}^5`$ $`={\displaystyle \underset{\begin{array}{c}(z_1,z_2,z_3,z_4,z_5)\\ |z_2z_1|=\mathrm{},|z_3z_2|=1,\\ |z_4z_3|=1,|z_5z_4|=\mathrm{}\\ |z_6z_5|=1\end{array}}{}}\theta (z_1)\theta (z_2)\theta (z_3)\theta (z_4)\theta (z_5)\theta (z_6)`$
$`=2\left\{\theta (a)\theta (b)\right\}^2\theta (a+1)\theta (b1).`$
Hence,

$$\theta (a+1)+\theta (b1)=2Q_{(\mathrm{},1)}^2/Q_{\mathrm{}}^1\text{ and }\theta (a+1)\theta (b1)=2Q_{(\mathrm{},1,1,\mathrm{},1)}^5/\left(Q_{\mathrm{}}^1\right)^2,$$

and so the unordered pair $`\{\theta (a+1),\theta (b1)\}`$ can be written as a function of $`(𝑸^1,\mathrm{},𝑸^5)`$.

The cross-product $`\theta (a)\theta (a+1)+\theta (b)\theta (b+1)`$ allows us to write $`[\theta (a),\theta (a+1),\theta (b1),\theta (b)]`$ as a function of the unordered pairs $`\{\theta (a),\theta (b)\}`$ and $`\{\theta (a+1),\theta (b1)\}`$. We have

$`Q_{(\mathrm{},\mathrm{},1)}^3`$ $`={\displaystyle \underset{\begin{array}{c}(z_1,z_2,z_3,z_4)\\ |z_2z_1|=\mathrm{},|z_3z_2|=\mathrm{},\\ |z_4z_3|=1\end{array}}{}}\theta (z_1)\theta (z_2)\theta (z_3)\theta (z_4)`$
$`=\theta (a)\theta (b)\left\{\theta (a)\theta (a+1)+\theta (b)\theta (b11)\right\},`$
and so

$$\theta (a)\theta (a+1)+\theta (b)\theta (b1)=2Q_{(\mathrm{},\mathrm{},1)}^3/Q_{\mathrm{}}^1.$$

We conclude that $`[\theta (a),\theta (a+1),\theta (b1),\theta (b)]`$ can be written as a function of the $`\{𝑸^k\}`$.

Continuing in this way, we work down to the center to obtain (48), using only $`\{𝑸^k\}`$. ∎

###### Proof of Theorem 1.1.

If $`\mathrm{}`$ is given, then by Proposition 4.2, it is clear that the theorem holds. That is, for each $`\mathrm{}`$, we can construct a scenery $`\theta _n^{\mathrm{}}`$ depending only on $`\sigma (X_1,\mathrm{},X_n)`$ measurable random variables, and so that $`\theta _n^{\mathrm{}}\theta T`$. Then by Lemma 3.8, the sequence $`\theta _n^\mathrm{}_n`$ will satisfy the requirements of the Theorem. ∎

We now provide a proof of our result in its full generality. Recall the notation given in Definition 3.4: As $`\eta (z)`$ is a probability measure on $``$ for each $`z`$,

$$\overline{\phi }(z)=_{}\phi 𝑑\eta (z),\text{and}\phi _0=\phi _{}\phi 𝑑\alpha .$$

###### Proof of Theorem 2.3.

We will show how to use the collection $`𝒬\stackrel{def}{=}\{𝑸^k(\phi )\}_{\phi \mathrm{\Phi }_1,k}`$ and $`\mathrm{}`$ to construct a stochastic scenery which is a shift and/or a reflection of $`\eta `$. The conclusion of the Theorem will then follow from applications of Proposition 3.2, Proposition 3.7, and Lemma 3.8 similarly to the proof of Theorem 1.1.

Fix a bounded and measurable $`\phi `$. We have that

$$\begin{array}{cc}\hfill Q_{\mathrm{}}^1(\phi _0)& =2\overline{\phi _0}(a)\overline{\phi _0}(b),\hfill \\ \hfill Q_{(\mathrm{},\mathrm{})}^2(\phi _0)& =\overline{\phi _0}(a)\overline{\phi _0}(b)\left\{\overline{\phi _0}(a)+\overline{\phi _0}(b)\right\}.\hfill \end{array}$$
(49)
Assume first that $`\overline{\phi _0}(a)\overline{\phi _0}(b)0`$. In this case, we can solve in (49) to obtain

$$\overline{\phi _0}(a)\overline{\phi _0}(b)=Q_{\mathrm{}}^1(\phi _0)/2\text{ and }\overline{\phi _0}(a)+\overline{\phi _0}(b)=2Q_{(\mathrm{},\mathrm{})}^2(\phi _0)/Q_{\mathrm{}}^1(\phi _0).$$
(50)
We use the identities in (50) to get

$$\{\overline{\phi _0}(a),\overline{\phi _0}(b)\}=\left\{\frac{Q_{(\mathrm{},\mathrm{})}^2(\phi _0)}{Q_{\mathrm{}}^1(\phi _0)}\pm \sqrt{\left(\frac{Q_{(\mathrm{},\mathrm{})}^2(\phi _0)}{Q_{\mathrm{}}^1(\phi _0)}\right)^2Q_{\mathrm{}}^1(\phi _0)/2}\right\}$$
(51)
We proceed inductively: assume we have determined, for $`k\mathrm{}/2`$,

$$\{(\overline{\phi _0}(a),\mathrm{},\overline{\phi _0}(a+k1)),(\overline{\phi _0}(b),\mathrm{},\overline{\phi _0}(bk+1))\}.$$
(52)
We have

$$\begin{array}{cc}\hfill Q_{(\mathrm{},k,k,\mathrm{})}^4(\phi _0)& =\left(\overline{\phi _0}(a)\overline{\phi _0}(b)\right)^2\left\{\overline{\phi _0}(a+k)+\overline{\phi _0}(bk)\right\},\hfill \\ \hfill Q_{(\mathrm{},k,k,\mathrm{},k)}^5(\phi _0)& =2\left(\overline{\phi _0}(a)\overline{\phi _0}(b)\right)^2\overline{\phi _0}(a+k)\overline{\phi _0}(bk).\hfill \end{array}$$
(53)
By assumption, $`\overline{\phi _0}(a)\overline{\phi _0}(b)0`$, so we can solve in (53) (using (50)) to get

$$\overline{\phi _0}(a+k)\overline{\phi _0}(bk)=\frac{2Q_{(\mathrm{},k,k,\mathrm{},k)}^5}{\left(Q_{\mathrm{}}^1(\phi _0)\right)^2}\text{and}\overline{\phi _0}(a+k)+\overline{\phi _0}(bk)=\frac{4Q_{(\mathrm{},k,k,\mathrm{})}^4(\phi _0)}{\left(Q_{\mathrm{}}^1(\phi _0)\right)^2}.$$

Thus, similarly to (51), we can determine

$$\{\overline{\phi _0}(a+k),\overline{\phi _0}(bk)\}$$
(54)
as a function of elements of $`𝒬`$.

Now define $`m\stackrel{def}{=}sup\{jk1:\overline{\phi _0}(a+j)\overline{\phi _0}(bj)\}`$. If there is no such $`j`$, there is no problem in finding

$$\{(\overline{\phi _0}(a),\mathrm{},\overline{\phi _0}(a+k)),(\overline{\phi _0}(b),\mathrm{},\overline{\phi _0}(bk))\}$$
(55)
from (52) and (54), so without loss of generality, assume such a $`j`$ exists.

Now notice that

$$Q_{(\mathrm{},m,m,\mathrm{},k,k,\mathrm{})}^7=\left(\overline{\phi _0}(a)\overline{\phi _0}(b)\right)^3\left\{\overline{\phi _0}(a+m)\overline{\phi _0}(bk)+\overline{\phi _0}(bm)\overline{\phi _0}(a+k)\right\},$$

and hence
$$\overline{\phi _0}(a+m)\overline{\phi _0}(bk)+\overline{\phi _0}(bm)\overline{\phi _0}(a+k)=\frac{8Q_{(\mathrm{},m,m,\mathrm{},k,k,\mathrm{})}^7}{\left(Q_{\mathrm{}}^1(\phi _0)\right)^3}.$$
(56)
From the two unordered pairs (which we already know)

$$\{\overline{\phi _0}(a+m),\overline{\phi _0}(bm)\}\text{ and }\{\overline{\phi _0}(a+k),\overline{\phi _0}(bk)\}$$

we can get two possible pairings:

$$\begin{array}{c}F_{good}\stackrel{def}{=}\{(\overline{\phi _0}(a+m),\overline{\phi _0}(a+k)),(\overline{\phi _0}(bm),\overline{\phi _0}(bk))\}\\ \text{and}\\ F_{bad}\stackrel{def}{=}\{(\overline{\phi _0}(a+m),\overline{\phi _0}(bk)),(\overline{\phi _0}(bm),\overline{\phi _0}(a+k))\}.\end{array}$$
(57)
From these two pairings we can compute the values

$$\begin{array}{c}f_{good}\stackrel{def}{=}\overline{\phi _0}(a+m)\overline{\phi _0}(a+k)+\overline{\phi _0}(bm)\overline{\phi _0}(bk)\\ \text{ and }\\ f_{bad}\stackrel{def}{=}\overline{\phi _0}(a+m)\overline{\phi _0}(bk)+\overline{\phi _0}(bm)\overline{\phi _0}(a+k)\end{array}.$$
(58)
Since we have written $`f_{bad}`$ in (56) as a function of elements of $`𝒬`$, we can use these elements to discard the pairing $`F_{bad}`$ in (57) from which it comes. If $`f_{bad}=f_{good}`$, we cannot determine the proper pairing. But this happens if and only if

$$\overline{\phi _0}(a+k)\left(\overline{\phi _0}(a+m)\overline{\phi _0}(bm)\right)=\overline{\phi _0}(bk)\left(\overline{\phi _0}(a+m)\overline{\phi _0}(bm)\right).$$
(59)
Since $`m`$ was defined so that $`\overline{\phi _0}(a+m)\overline{\phi _0}(bm)0`$, we conclude that (59) is valid if and only if $`\overline{\phi _0}(a+k)=\overline{\phi _0}(bk)`$. But in this case, it is clear that (55) can be found from (52) and (54).

Otherwise, we can pick out $`F_{good}`$ from (57), and hence we can determine (55).

Thus, by induction, we can determine

$$\{(\overline{\phi }(a),\mathrm{},\overline{\phi }(b)),(\overline{\phi }(b),\mathrm{},\overline{\phi }(a))\}.$$
(60)
To summarize, we have just shown for any bounded measurable function $`\phi `$ obeying the condition $`\overline{\phi _0}(a)\overline{\phi _0}(b)0`$ we can determine

$$[\overline{\phi }(a),\mathrm{},\overline{\phi }(b)].$$
(61)
Now suppose that $`\overline{\phi _0}(a)\overline{\phi _0}(b)=0`$. Recall that the elements of $`\mathrm{\Phi }_1`$ are enumerated as $`(h_1,\mathrm{},h_n,\mathrm{})`$. If we define $`n^{}`$ as the smallest $`n`$ so that $`\{\overline{h_n}(a)_{}h_n𝑑\alpha ,\overline{h_n}(b)_{}h_n𝑑\alpha \}`$ has distinct non-zero elements, then Lemma 3.9 guarantees that $`n^{}<\mathrm{}`$. Let $`\psi \stackrel{def}{=}h_n^{}`$.

There is a $`c`$ small enough so that

$$\overline{\phi _0+c\psi _0}(a)0\text{and}\overline{\phi _0+c\psi _0}(b)0.$$

We can determine $`[\overline{c\psi _0}(a),\mathrm{},\overline{c\psi _0}(b)]`$, and $`[\overline{\phi _0+c\psi _0}(a),\mathrm{},\overline{\phi _0+c\psi _0}(b)]`$.

Thus we can determine the two quantities

$$\begin{array}{c}[\overline{\phi _0+c\psi _0}(a)\overline{c\psi _0}(a),\mathrm{},\overline{\phi _0+c\psi _0}(b)\overline{c\psi _0}(b)]\\ \text{and}\\ [\overline{\phi _0+c\psi _0}(a)\overline{c\psi _0}(b),\mathrm{},\overline{\phi _0+c\psi _0}(b)\overline{c\psi _0}(a)]\end{array}.$$

But the end points of the second expression are nonzero for $`c`$ small enough, while at least one endpoint in the first express is zero. Thus we can pick out the first expression, which allows us to determine (61).

The careful reader will have noticed that our use of Lemma 3.9 requires that $`\eta (a)\eta (b)`$. If this is not the case, then $`\overline{\phi _0}(a)=\overline{\phi _0}(b)=0`$. We can then apply the entire procedure with $`\mathrm{}2,a+1,b1`$ replacing $`\mathrm{},a`$ and $`b`$ respectively.

Now we have shown that we can determine

$$([\overline{\phi _1}(a),\mathrm{},\overline{\phi _1}(b)],[\overline{\phi _2}(a),\mathrm{},\overline{\phi _2}(b)],\mathrm{}).$$
(62)
Our goal now is to find

$$[\left(\overline{\phi _k}(a)\right)_{k=1}^{\mathrm{}},\left(\overline{\phi _k}(a+1)\right)_{k=1}^{\mathrm{}},\mathrm{},\left(\overline{\phi _k}(b)\right)_{k=1}^{\mathrm{}}],$$

which, since $`\mathrm{\Phi }`$ is measure determining, yields $`[\eta (a),\eta (a+1),\mathrm{},\eta (b)]`$. Again, we use induction. Suppose that we know

$$[(\overline{\phi _1}(a),\mathrm{},\overline{\phi _{k1}}(a)),\mathrm{},(\overline{\phi _1}(b),\mathrm{},\overline{\phi _{k1}}(b))].$$
(63)
From (62), we have in particular

$$[\overline{\phi _k}(a),\mathrm{},\overline{\phi _k}(b)].$$
(64)
There are two possible extensions of (63) using (64):

$$\begin{array}{c}G_{good}\stackrel{def}{=}[(\overline{\phi _1}(a),\mathrm{},\overline{\phi _{k1}}(a),\overline{\phi _k}(a)),\mathrm{},(\overline{\phi _1}(b),\mathrm{},\overline{\phi _{k1}}(b),\overline{\phi _k}(b))]\\ \text{and}\\ G_{bad}\stackrel{def}{=}[(\overline{\phi _1}(a),\mathrm{},\overline{\phi _{k1}}(a),\overline{\phi _k}(b)),\mathrm{},(\overline{\phi _1}(b),\mathrm{},\overline{\phi _{k1}}(b),\overline{\phi _k}(a))]\end{array}$$
(65)
We want to guarantee that we can pick out $`G_{good}`$ from $`\{G_{good},G_{bad}\}`$ given in (65).

Suppose there is some $`j`$ so that

$$(\overline{\phi _1}(a+j),\mathrm{},\overline{\phi _{k1}}(a+j))(\overline{\phi _1}(bj),\mathrm{},\overline{\phi _{k1}}(bj)).$$
(66)
This is without loss of generality, since if there is no such $`j`$, then of course we can extend (63) to obtain

$$[(\overline{\phi _1}(a),\mathrm{},\overline{\phi _k}(a)),\mathrm{},(\overline{\phi _1}(b),\mathrm{},\overline{\phi _k}(b))].$$
(67)
Since the linear functionals on $`^{k1}`$ separate points, there exist $`𝒄^{k1}`$ so that if $`T_c(𝒙)=𝒄,𝒙`$, then

$$T_c\left((\overline{\phi _1}(a+j),\mathrm{},\overline{\phi _{k1}}(a+j))\right)T_c\left((\overline{\phi _1}(bj),\mathrm{},\overline{\phi _{k1}}(bj))\right).$$

Since for any function $`\phi `$ we can recover (60), by linearity of expectation, for the function $`T_c\left((\phi _1,\mathrm{},\phi _{k1})\right)+\phi _k`$ we can determine

$$[T_c(\overline{\phi _1}(a),\mathrm{},\overline{\phi _{k1}}(a))+\overline{\phi _k}(a),\mathrm{},T_c(\overline{\phi _1}(b),\mathrm{},\overline{\phi _{k1}}(b))+\overline{\phi _k}(b))]$$
(68)
But from (65), we can determine

$$\begin{array}{c}[T_c(\overline{\phi _1}(a),\mathrm{},\overline{\phi _{k1}}(a))+\overline{\phi _k}(a),\mathrm{},T_c(\overline{\phi _1}(b),\mathrm{},\overline{\phi _{k1}}(b))+\overline{\phi _k}(b)]\\ \text{and}\\ [T_c(\overline{\phi _1}(a),\mathrm{},\overline{\phi _{k1}}(a))+\overline{\phi _k}(b),\mathrm{},T_c(\overline{\phi _1}(b),\mathrm{},\overline{\phi _{k1}}(b))+\overline{\phi _k}(a)]\end{array}$$
(69)
It thus suffices to show that these two sets cannot be the same. If the sets in (69) are the same, then either $`\overline{\phi _k}(a+j)=\overline{\phi _k}(bj)`$ for all $`j`$, in which case there is no problem in obtaining (67), or

$$T_c(\overline{\phi _1}(a+j),\mathrm{},\overline{\phi _{k1}}(a+j))=T_c(\overline{\phi _1}(bj),\mathrm{},\overline{\phi _{k1}}(bj))\text{ for all }j.$$

But $`T_c`$ was defined to rule out this possibility. Hence we can distinguish the “correct” extension in (65), and thus we can determine (67).

By induction, we can then determine

$$[(\overline{\phi _k}(a))_{k=1}^{\mathrm{}},\mathrm{},(\overline{\phi _k}(b))_{k=1}^{\mathrm{}}].$$
(70)
Because the $`\{\phi _k\}`$ are measure determining, from (70) we can determine

$$[\eta (a),\mathrm{},\eta (b)].$$

Pick one $`\mathrm{}`$-tuple from $`[\eta (a),\mathrm{},\eta (b)]`$, and call it $`(\eta _0(1),\mathrm{},\eta _0(\mathrm{}))`$. Finally, define $`\widehat{\eta }`$ by

$$\widehat{\eta }(z)=\{\begin{array}{cc}\alpha \hfill & \text{if }z<1\text{ or }z>\mathrm{}\hfill \\ \eta _0(z)\hfill & \text{if }1z\mathrm{}\hfill \end{array}.$$

## 5 Unsolved Problems

There remain a couple of questions still requiring resolution:

1. It follows from results in \[Lin99\] that if we allow infinitely many biased coins, then there exist bias configurations $`\{\theta (z):z\}`$ that cannot be recovered up to a reflection and shift. We have restricted attention to finitely many biased coins; however, the methods of this paper do allow recovery of infinitely many biases (up to reflection and shift) if the biased coins are sufficiently sparse. It remains an open question to determine for which infinite sets of integers $`S`$ can one recover the biases of biased coins located in $`S`$ from the tosses observed by a random walker.
2. We have shown in Theorem 2.3 that for symmetric walks with finite variance increments, we can recover finitely many unknown distributions up to a shift and/or a reflection. We have not been able to generalize the algebraic results in Section 3 to walks which are asymmetric, yet still mean zero. In particular, Lemma 3.3 needs to be proven for a matrix with entries $`\{P^i(0,j):\mathrm{\hspace{0.17em}1}ir,mjm\}`$. We expect the following to hold:

###### Conjecture 1.

In the setting of theorem 2.3, suppose that the symmetry assumption on the walk $`S`$ is replaced by the assumption that the walk $`S`$ has mean-zero, non-symmetric increments of finite variance. Then $`\eta `$ can be recovered up to a shift only.
3. In Theorem 2.3, is it possible to replace the symmetric random walk on $``$ satisfying (1), by a general null-recurrent Markov chain that satisfies $`_nu_n^2=\mathrm{}`$?
(Here $`u_n`$ is the probability that the chain returns to its starting state after $`n`$ steps.) The goal is to recover $`\eta `$ up to an automorphism of the Markov chain.

Acknowledgements. We are grateful to Rich Bass for useful discussions, and to Alan Hammond and Gabor Pete for helpful comments on the manuscript.