You are an expert at summarizing long articles. Proceed to summarize the following text: 
this article is part of a larger program , which consists in devising and quantitatively analyzing numerical methods to approximate effective coefficients in stochastic homogenization of linear elliptic equations . more precisely we tackle here the case of a discrete elliptic equation with independent and identically distributed coefficients ( see however the end of this introduction for more general statistics ) , and present and fully analyze an approximation procedure based on a monte - carlo method .    a first possibility to approximate effective coefficients is to directly solve the so - called corrector equation . in this approach , a first step towards the derivation of error estimates is a quantification of the qualitative results proved by knnemann @xcite ( and inspired by papanicolaou and varadhan s treatment of the continuous case @xcite ) and kozlov @xcite . in the stochastic case , such an equation is posed on the whole @xmath3 , and we need to localize it on a bounded domain , say the hypercube @xmath4 of side @xmath5 . as shown in a series of papers by otto and the first author @xcite , and the first author @xcite , there are three contributions to the @xmath6-error in probability between the true homogenized coefficients and its approximation . the dominant error in small dimensions takes the form of a variance : it measures the fact that the approximation of the homogenized coefficients by the average of the energy density of the corrector on a box @xmath4 fluctuates . this error decays at the rate of the central limit theorem @xmath7 in any dimension ( with a logarithmic correction for @xmath8 ) . the second error is the so - called systematic error : it is due to the fact that we have modified the corrector equation by adding a zero - order term of strength @xmath9 ( as standard in the analysis of the well - posedness of the corrector equation ) . the scaling of this error depends on the dimension and saturates at dimension @xmath10 . it is of higher order than the random error up to dimension @xmath11 . the last error is due to the use of boundary conditions on the bounded domain @xmath4 . provided there is a buffer region , this error is exponentially small in the distance to the buffer zone measured in units of @xmath12 . this approach has two main drawbacks . first the numerical method only converges at the central limit theorem scaling in terms of @xmath13 up to dimension @xmath11 , which is somehow disappointing from a conceptual point of view ( although this is already fine in practice ) . second , although the size of the buffer zone is roughly independent of the dimension , its cost with respect to the central limit theorem scaling dramatically increases with the dimension ( recall that in dimension @xmath14 , the clt scaling is @xmath7 , so that in high dimension , we may consider smaller @xmath13 for a given precision , whereas the use of boundary conditions requires @xmath15 in any dimension ) . based on ideas of the second author in @xcite , we have taken advantage of the spectral representation of the homogenized coefficients ( originally introduced by papanicolaou and varadhan to prove their qualitative homogenization result ) in order to devise and analyze new approximation formulas for the homogenized coefficients in @xcite . in particular , this has allowed us to get rid of the restriction on dimension , and exhibit refinements of the numerical method of @xcite which converge at the central limit theorem scaling in any dimension ( thus avoiding the first mentioned drawback ) . unfortunately , the second drawback is inherent to the type of method used : if the corrector equation has to be solved on a bounded domain @xmath4 , boundary conditions need to be imposed on the boundary @xmath16 . since their values are actually also part of the problem , a buffer zone seems mandatory  with the notable exception of the periodization method , whose analysis is yet still unclear to us , especially when spatial correlations are introduced in the coefficients . in order to avoid the issue of boundary conditions , we adopt here another point of view on the problem : the random walk in random environment approach . this other point of view on the same homogenization problem has been analyzed in the celebrated paper @xcite by kipnis and varadhan , and then extended by de masi , ferrari , goldstein , and wick @xcite . the strategy of the present paper is to obtain an approximation of the homogenized coefficients by the numerical simulation of this random walk up to some large time . as we did in the case of the approach based on the corrector equation , a first step towards the analysis of this numerical method is to quantify the corresponding qualitative result , namely here kipnis - varadhan s convergence theorem . compared to the deterministic approach based on the approximate corrector equation , the advantage of the present approach is that its convergence rate and computational costs are dimension - independent . as we shall also see , as opposed to the approach based on the corrector equation , the environment only needs to be generated along the trajectory of the random walker , so that much less information has to be stored during the calculation . this may be quite an important feature of the monte carlo method in view of the discussion of ( * ? ? ? * section  4.3 ) . we consider the discrete elliptic operator @xmath17 , where @xmath18 and @xmath19 are the discrete backward divergence and forward gradient , respectively . for all @xmath20 , @xmath21 is the diagonal matrix whose entries are the conductances @xmath22 of the edges @xmath23 starting at @xmath24 , where @xmath25 denotes the canonical basis of @xmath3 . let @xmath26 denote the set of edges of @xmath3 . we call the family of conductances @xmath27 the _ environment_. the environment @xmath28 is random , and we write @xmath29 for its distribution ( with corresponding expectation @xmath30 ) . we make the following assumptions  :    * the measure @xmath29 is invariant under translations , * the conductances are i.  i.  d. , * there exists @xmath31 such that @xmath32 almost surely .    under these conditions , standard homogenization results ensure that there exists some _ deterministic _ symmetric matrix @xmath33 such that the solution operator of the deterministic continuous differential operator @xmath34 describes the large scale behavior of the solution operator of the random discrete differential operator @xmath17 almost surely ( for this statement , ( h2 ) can in fact be replaced by the weaker assumption that the measure @xmath29 is ergodic with respect to the group of translations , see @xcite ) . the operator @xmath35 is the infinitesimal generator of a stochastic process @xmath36 which can be defined as follows . given an environment @xmath28 , it is the markov process whose jump rate from a site @xmath20 to a neighbouring site @xmath37 is given by @xmath38 . we write @xmath39 for the law of this process starting from @xmath20 . it is proved in @xcite that under the averaged measure @xmath40 , the rescaled process @xmath41 converges in law , as @xmath42 tends to @xmath43 , to a brownian motion whose infinitesimal generator is @xmath34 , or in other words , a brownian motion with covariance matrix @xmath44 ( see also @xcite for prior results ) . we will use this fact to construct computable approximations of @xmath33 . as proved in @xcite , this invariance principle holds as soon as ( h1 ) is true , ( h2 ) is replaced by the ergodicity of the measure @xmath29 , and ( h3 ) by the integrability of the conductances . under the assumptions ( h1-h3 ) , @xcite strengthens this result in another direction , showing that for almost every environment , @xmath41 converges in law under @xmath45 to a brownian motion with covariance matrix @xmath44 . this has been itself extended to environments which do not satisfy the uniform ellipticity condition ( h3 ) , see @xcite . let @xmath46 denote the sequence of consecutive sites visited by the random walk @xmath47 ( note that the `` times '' are different in nature for @xmath48 and @xmath49 ) . this sequence is itself a markov chain that satisfies for any two neighbours @xmath50 : @xmath51 = \frac{\omega_{x , y}}{p_\omega(x)},\ ] ] where @xmath52 . we simply write @xmath53 for @xmath54 . let us introduce a `` tilted '' version of the law @xmath29 on the environments , that we write @xmath55 and define by @xmath56 } \ \d { \mathbb{p}}(\omega).\ ] ] the reason why this measure is natural to consider is that it makes the environment seen from the position of the random walk @xmath57 a stationary process ( see ( [ defenvpart ] ) for a definition of this process ) . interpolating between two integers by a straight line , we can think of @xmath57 as a continuous function on @xmath58 . with this in mind , it is also true that there exists a matrix @xmath59 such that , as @xmath42 tends to @xmath43 , the rescaled process @xmath60 converges in law under @xmath61 to a brownian motion with covariance matrix @xmath62 . moreover , @xmath59 and @xmath33 are related by ( see ( * ? ? ? * theorem  4.5 ( ii ) ) )  : @xmath63 \ { a_\mathrm{hom}^\mathrm{disc}}.\ ] ] given that the numerical simulation of @xmath57 saves some operations compared to the simulation of @xmath64 ( there is no waiting time to compute , and the running time is equal to the number of steps ) , we will focus on approximating @xmath59 . more precisely , we fix once and for all some @xmath65 with @xmath66 , and define @xmath67 , \qquad \sigma^2 = 2 \xi \cdot { a_\mathrm{hom}^\mathrm{disc}}\xi.\ ] ] it follows from results of @xcite ( or ( * ? ? ? * theorem  2.1 ) ) that @xmath68 tends to @xmath69 as @xmath1 tends to infinity . our first contribution is to give a quantitative estimate of this convergence . in particular we shall show that , with i.  i.  d. coefficients and up to a logarithmic correction in dimension @xmath70 , the difference between @xmath68 and @xmath69 is of order @xmath71 . we now describe a monte - carlo method to approximate @xmath68 . using the definition of the tilted measure ( [ deftdp ] ) , one can see that @xmath72}{t }   = \frac{{\mathbb{e}}{\mathbf{e}^\omega}_0[p(\omega ) ( \xi \cdot y(t))^2]}{t { \mathbb{e}}[p]}.\ ] ] assuming that we have easier access to the measure @xmath29 than to the tilted @xmath55 , we prefer to base our monte - carlo procedure on the r.  h.  s. of the second identity in ( [ enlevetilt ] ) . let @xmath73 be independent random walks evolving in the environments @xmath74 respectively . we write @xmath75 for their joint distribution , all random walks starting from @xmath43 , where @xmath76 stands for @xmath77 . the family of environments @xmath76 is itself random , and we let @xmath78 be the product distribution with marginal @xmath29 . in other words , under @xmath78 , the environments @xmath79 are independent and distributed according to @xmath29 . our computable approximation of @xmath68 is defined by @xmath80 the following step in the analysis is to quantify the random fluctuations of @xmath81 in terms of @xmath2  the number of random walks considered in the empirical average to approximate @xmath68  and @xmath1 . we shall prove a large deviation result which ensures that the @xmath82-probability that the difference between @xmath81 and @xmath68 exceeds @xmath71 is exponentially small in the ratio @xmath83 . the rest of this article is organized as follows . in section  [ sec : quantkv ] , which can be read independently of the rest of the paper , we consider a general discrete or continuous - time reversible markov process . kipnis - varadhan s theorem ( and its subsequent development due to @xcite ) gives conditions for additive functionals of this process to satisfy an invariance principle . we show that , under additional conditions written in terms of a spectral measure , the statement can be made quantitative . more precisely , kipnis - varadhan s theorem relies on writing the additive functional under consideration as the sum of a martingale plus a remainder . this remainder , after suitable normalization , is shown to converge to @xmath43 in @xmath6 . under our additional assumptions , we give explicit bounds on the rate of decay . in section  [ sec : syserr ] , we make use of this result , in the context of the approximation of homogenized coefficients , to estimate the systematic error @xmath84 . the central achievement of this section is to prove that the relevant spectral measure satisfies the conditions of our quantitative version of kipnis - varadhan s theorem . section  [ sec : randfluc ] is dedicated to the estimate of the random fluctuations . these are controlled through large deviations estimates . relying on these results , we give in section  [ sec : numtest ] a complete error analysis of the monte - carlo method to approximate the homogenized matrix @xmath59 , which we illustrate by numerical tests . let us quickly discuss the sharpness of these results . if @xmath85 was a periodic matrix ( or even a constant matrix ) the systematic error would also be of order @xmath71 ( without logarithmic correction for @xmath8 ) , and the fluctutations would decay exponentially fast in the ratio @xmath83 as well . this shows that our analysis is optimal ( the additional logarithm seems unavoidable for @xmath8 , as discussed in the introduction of @xcite ) . let us also point out that although the results of this paper are proved under assumptions ( h1)-(h3 ) , the assumption ( h2 ) on the statistics of @xmath28 is only used to obtain the variance estimate of ( * ? ? ? * lemma  2.3 ) . in particular , ( h2 ) can be weakened as follows :    * the distribution of @xmath86 may in addition depend on @xmath87 , * independence can be replaced by finite correlation length @xmath88 , that is for all @xmath89 , @xmath90 and @xmath91 are independent if @xmath92 , * independence can be replaced by mixing in the sense of dobrushin and shlosman  we refer the reader to work in progress by otto and the first author for this issue @xcite .    * notation . * so far we have already introduced the probability measures @xmath45 ( distribution of @xmath57 ) , @xmath75 ( distribution of @xmath93 ) , @xmath29 ( i.i.d . distribution for @xmath27 ) , @xmath55 ( tilted measure defined in ( [ deftdp ] ) ) and @xmath78 ( product distribution of @xmath76 with marginal  @xmath29 ) . it will be convenient to define @xmath94 the product distribution of @xmath76 with marginal  @xmath55 . for convenience , we write @xmath95 as a short - hand notation for @xmath40 , @xmath96 for @xmath61 , @xmath97 for @xmath98 , and @xmath99 for @xmath100 . the corresponding expectations are written accordingly , replacing `` p '' by `` e '' with the appropriate typography . finally , we write @xmath101 for the euclidian norm of @xmath102 . kipnis - varadhan s theorem @xcite concerns additive functionals of reversible markov processes . it gives conditions for such additive functionals to satisfy an invariance principle . the proof of the result relies on a decomposition of the additive functional as the sum of a martingale term plus a remainder term , the latter being shown to be negligible . in this section , which can be read independently of the rest of the paper , we give conditions that enable to obtain some quantitative bounds on this remainder term . we consider discrete and continuous times simultaneously . let @xmath103 be a markov process defined on some measurable state space @xmath104 ( here , @xmath105 stands either for @xmath106 or for @xmath107 ) . we denote by @xmath108 the distribution of the process started from @xmath109 , and by @xmath110 the associated expectation . we assume that this markov process is reversible and ergodic with respect to some probability measure  @xmath111 . we write @xmath112 for the law of the process started from the distribution @xmath111 , and @xmath113 for the associated expectation .    to the markov process is naturally associated a semi - group @xmath114 defined , for any @xmath115 , by @xmath116.\ ] ] each @xmath117 is a self - adjoint contraction of @xmath118 . in the continuous - time case , we assume further that the semi - group is strongly continuous , that is to say , that @xmath119 converges to @xmath120 in @xmath118 as @xmath1 tends to @xmath43 , for any @xmath121 . we let @xmath122 be the @xmath118-infinitesimal generator of the semi - group . it is self - adjoint in @xmath118 , and we fix the sign convention so that it is a positive operator ( i.e. , @xmath123 ) .    note that in general , one can see using spectral analysis that there exists a projection @xmath124 such that @xmath119 converges to @xmath125 as @xmath1 tends to @xmath43 , @xmath126 . changing @xmath118 to the image of the projection @xmath124 , and @xmath127 for @xmath124 , one recovers a strongly continuous semigroup of contractions , and one can still carry the analysis below replacing @xmath118 by the image of @xmath124 when necessary .    in discrete time , we set @xmath128 . again , @xmath122 is a positive self - adjoint operator on @xmath118 . note that we slightly depart from the custom of defining the generator as @xmath129 in order to match more closely the continuous time situation . we denote by @xmath130 the scalar product in @xmath118 . for any function @xmath121 we define the _ spectral measure _ of @xmath122 projected on the function @xmath120 as the measure @xmath131 on  @xmath58 that satisfies , for any bounded continuous @xmath132 , the relation @xmath133    the dirichlet form associated to @xmath122 is given by @xmath134 we denote by @xmath135 the completion of the space @xmath136 with respect to this @xmath137 norm , taken modulo functions of zero @xmath137 norm . this turns @xmath138 into a hilbert space , and we let @xmath139 denote its dual . one can identify @xmath139 with the completion of the space @xmath140 with respect to the norm @xmath141 defined by @xmath142 indeed , for all @xmath121 , the linear form @xmath143 has norm @xmath144 , and thus defines an element of @xmath139 ( with norm @xmath144 ) iff @xmath144 is finite . the notion of spectral measure introduced in ( [ defef ] ) for functions of @xmath118 can be extended to elements of @xmath139 . indeed , let @xmath132 be a continuous function such that @xmath145 as @xmath146 . one can check that the map @xmath147 extends to a bounded linear map on @xmath139 . one can then define the spectral measure of @xmath122 projected on the function @xmath120 as the measure @xmath131 such that for any continuous @xmath148 with @xmath145 , ( [ defef ] ) holds . with a slight abuse of notation , for all @xmath149 and @xmath150 , we write @xmath151 for the @xmath152 duality product between @xmath120 and @xmath153 .    for any @xmath149 , we define @xmath154 as @xmath155 according to whether we consider the continuous or the discrete time cases . in the continuous case , the meaning of ( [ defzf ] ) is unclear a priori . yet it is proved in ( * ? ? ? * lemma  2.4 ) that for any @xmath156 the map @xmath157 can be extended by continuity to a bounded linear map on @xmath139 , and moreover , that ( [ defzf ] ) coincides with the usual integral as soon as @xmath158 . the following theorem is due to @xcite , building on previous work of @xcite . [ kv ] ( i ) for all @xmath149 , there exists @xmath159 , @xmath160 such that @xmath161 defined in satisfies the identity @xmath162 , where @xmath163 is a square - integrable martingale with stationary increments under @xmath112 ( and the natural filtration ) , and @xmath164 is such that  : @xmath165 \xrightarrow[t \to + \infty ] { } 0.\ ] ] as a consequence , @xmath166 converges in law under @xmath112 to a gaussian random variable of variance @xmath167 as @xmath1 goes to infinity , and @xmath168 \xrightarrow[t \to + \infty ] { } \sigma^2(f).\ ] ] ( ii ) if , moreover , @xmath158 and , for some @xmath169 , @xmath170 is in @xmath118 , then the process @xmath171 converges in law under @xmath112 to a brownian motion of variance @xmath172 as @xmath42 goes to @xmath43 . * remarks . * the additional conditions appearing in statement ( ii ) are automatically satisfied in discrete time , due to the fact that @xmath173 in this case . in the continuous - time setting and when @xmath158 , the process @xmath174 is almost surely continuous , and @xmath170 is indeed a well - defined random variable .    under some additional information on the spectral measure of @xmath120 , we can estimate the rates of convergence in the limits ( [ e : xitendvers0 ] ) and ( [ e : l2conv ] ) . for any @xmath175 and @xmath176 , we say that the spectral exponents of a function @xmath149 are at least @xmath177 if @xmath178 note that the phrasing is consistent , since if @xmath179 for the lexicographical order , and if the spectral exponents of @xmath120 are at least @xmath177 , then they are at least @xmath180 . in @xcite , it was found more convenient to consider , instead of ( [ specexp ] ) , a condition of the following form  : @xmath181 one can easily check that conditions ( [ specexp ] ) and ( [ specexp2 ] ) are equivalent . indeed , on the one hand , one has the obvious inequality @xmath182 which shows that ( [ specexp2 ] ) implies ( [ specexp ] ) . on the other hand , one may perform a kind of integration by parts , use fubini s theorem  : @xmath183 and obtain the converse implication by examining separately the integration over @xmath184 in @xmath185 and in @xmath186 .    for all @xmath175 and @xmath176 , we set @xmath187 the quantitative version of theorem  [ kv ] is as follows . [ quantkv ] if the spectral exponents of @xmath149 are at least @xmath177 , then the decomposition @xmath162 of theorem  [ kv ] holds with the additional property that @xmath188 \ = o(\psi_{\gamma , q}(t ) ) \qquad ( t \to + \infty).\ ] ] moreover , @xmath189}{t }   = o(\psi_{\gamma , q}(t ) ) \qquad ( t \to + \infty).\ ] ]    in the continuous - time setting , the argument for the first estimate is very similar to the one of ( * ? ? * proposition  8.2 ) , and we do not repeat the details here . it is based on the observation that @xmath190 = 2 \int \frac{1-e^{-\lambda t}}{\lambda^2 t } \ \d e_f(\lambda).\ ] ] one needs to take into account the possible logarithmic terms that appear in ( [ specexp2 ] ) and which are not considered in @xcite . some care is also needed because we do not assume that @xmath121 . yet one can easily replace the bound involving the @xmath118 norm of @xmath120 by its @xmath139 norm . the second part of the statement is given by ( * ? ? ? * proposition  8.3 ) . we now turn to the discrete time setting . in this context , identity ( [ normxi2 ] ) should be replaced by @xmath191 = 2 \int \frac{1-(1-\lambda)^t}{\lambda^2 t } \ \d e_f(\lambda).\ ] ] by definition , @xmath192 , where @xmath129 is the semi - group at time @xmath193 . hence the spectrum of @xmath122 is contained in @xmath194 $ ] . one can then follow the same computations as before to prove the first part of theorem  [ quantkv ] .    somewhat surprisingly , the second part of the statement requires additional attention in the discrete time setting . indeed , in the continuous case , the argument of ( * ? ? ? * proposition  8.3 ) ( which already appears in @xcite ) is that @xmath161 and @xmath195 are orthogonal in @xmath196 , a fact obtained using the invariance under time symmetry . this orthogonality is only approximately valid in the discrete - time setting . indeed , let us recall that @xmath161 is given by ( [ defzf ] ) , while @xmath197 is obtained as the limit in @xmath196 of @xmath198 where @xmath199 . using time symmetry , what we obtain is that @xmath197 is orthogonal to @xmath200 . as a consequence , the cross - product @xmath201 $ ] , which is equal to @xmath43 in the proof of ( * ? ? ? * proposition  8.3 ) , is in the present case equal to @xmath202 $ ] . yet spectral analysis ensures that this term is equal to @xmath203 which is what we need to obtain the second claim of the theorem . we now come back to the analysis of the monte - carlo approximation of the homogenized coefficients within assumptions ( h1)-(h3 ) . the aim of this section is to estimate the difference between @xmath68 and the quantity @xmath69 we wish to approximate ( both being defined in ( [ defsigmat ] ) ) . this difference , that we refer to as the _ systematic error _ after @xcite , is shown to be of order @xmath71 as @xmath1 tends to infinity , up to a logarithmic correction in dimension @xmath70 . [ syserr ] under assumptions ( h1)-(h3 ) , there exists @xmath176 such that , as @xmath1 tends to infinity , @xmath204    theorem  [ syserr ] is a discrete - time version of ( * ? ? ? * corollary  2.6 ) . its proof makes use of an auxiliary process that we now introduce . let @xmath205 be the translation group that acts on the set of environments as follows : for any pair of neigbhours @xmath206 , @xmath207 . the _ environment viewed by the particle _ is the process defined by @xmath208 one can check that @xmath209 is a markov chain , whose generator is given by @xmath210 so that @xmath211 = ( i-{\mathcal{l}})f(\omega)$ ] . moreover , the measure @xmath55 defined in ( [ deftdp ] ) is reversible and ergodic for this process ( * ? ? ? * lemma  4.3 ( i ) ) . as a consequence , the operator @xmath212 is ( positive and ) self - adjoint in @xmath213 . the proof of theorem  [ syserr ] relies on spectral analysis . for any function @xmath214 , let @xmath131 be the spectral measure of @xmath212 projected on the function @xmath120 . this measure is such that , for any positive continuous function @xmath215 , one has @xmath216 = \int \psi(\lambda ) \ \d e_f(\lambda).\ ] ] for any @xmath175 and @xmath176 , we recall that we say that the spectral exponents of a function @xmath120 are at least @xmath177 if holds . let us define the local drift @xmath217 in direction @xmath218 as @xmath219 = \frac{1}{p(\omega ) } \sum_{|z| = 1 } \omega_{0,z } \ \xi \cdot z.\ ] ] as we shall prove at the end of this section , we have the following bounds on the spectral exponents of @xmath217 .    [ p : specexp ] under assumptions ( h1)-(h3 ) , there exists @xmath176 such that the spectral exponents of the function @xmath217 are at least @xmath220    let us see how this result implies theorem  [ syserr ] . in order to do so , we also need the following information , that is a consequence of proposition  [ p : specexp ] . [ corpoly ] let @xmath221\ ] ] be the image of @xmath217 by the semi - group at time @xmath1 associated with the markov chain @xmath209 . there exists @xmath176 such that @xmath222 = \left| \begin{array}{ll } o\big(t^{-2 } \ { \ln}^q(t)\big )   & \text{if } d = 2,\\ o\big(t^{-(d/2 + 1)}\big ) & \text{if } 3 { \leqslant}d { \leqslant}5 , \\ o\big(t^{-4 } \ { \ln}(t)\big )   & \text{if } d = 6,\\ o\big(t^{-4}\big ) & \text{if } d { \geqslant}7 . \end{array } \right.\ ] ]    this result is the discrete - time analog of ( * ? ? ? * corollary  1 ) . it is obtained the same way , noting that @xmath222 = \int ( 1-\lambda)^{2 t } \ \d e_f(\lambda),\ ] ] and that the support of the measure @xmath131 is contained in @xmath194 $ ] . we are now in position to prove theorem  [ syserr ] . the proof has the same structure as for the continuous - time case of ( * ? ? ? * proposition  8.4 ) . note that ( * ? ? ? * theorem  2.1 ) ensures that @xmath223 \,=\,\sigma^2.\ ] ] the starting point is the observation that , under @xmath96 , the process defined by @xmath224 is a square - integrable martingale with stationary increments . on the one hand , following ( [ defzf ] ) , we denote by @xmath225 the sum appearing in the r.  h.  s. of ( [ defnt ] ) . from proposition [ p : specexp ] and theorem  [ quantkv ] , we learn that there exist @xmath226 and @xmath176 such that @xmath227 =   \left| \begin{array}{ll } o \big (   { \ln}^{q}(t ) \big ) & \text{if } d = 2 , \\ o \big ( 1 \big ) & \text{if } d > 2 . \end{array } \right.\ ] ] on the other hand , since @xmath228 is a martingale with stationary increments , @xmath229 = t { \tilde}{{\mathbb{e}}}_0[(n_1)^2].\ ] ] as in the proof of theorem  [ quantkv ] in the discrete time case , we then use that @xmath230 is orthogonal to @xmath231 to turn into @xmath232 = t^{-1}{\tilde}{{\mathbb{e}}}_0[(\xi \cdot y(t))^2 ] + t^{-1}{\tilde}{{\mathbb{e}}}_0[(z_{{\mathfrak}{d}}(t))^2 ] + 2t^{-1 } { \tilde}{{\mathbb{e}}}_0[{\mathfrak}{d}(\omega(t ) ) ( \xi \cdot y(t))].\ ] ] we already control the l.  h.  s. and the second term of the r.  h.  s. of ( [ decompnt ] ) . in order to quantify the convergence of @xmath233 $ ] it remains to control the last term . in particular , provided we show that @xmath234 = \left| \begin{array}{ll } o \big ( { \ln}^{q}(t ) \big ) & \text{if } d = 2 , \\ o \big ( 1 \big ) & \text{if } d > 2 , \end{array } \right.\ ] ] , , , and imply first that @xmath235-{\overline}{\sigma}^2 $ ] , and then the desired quantitative estimate . we now turn to and write @xmath236 & = & \sum_{s=0}^{t-1 } { \tilde}{{\mathbb{e}}}_0[{\mathfrak}{d}(\omega(t ) ) ( \xi \cdot ( y(s+1)-y(s ) ) ] \\ & = & \sum_{s=0}^{t-1 } { \tilde}{{\mathbb{e}}}_0[{\mathfrak}{d}_{t - s-1}(\omega(s+1 ) ) ( \xi \cdot ( y(s+1)-y(s))],\end{aligned}\ ] ] where we have used the markov property at time @xmath237 , together with the definition ( [ defdt ] ) of @xmath238 . using cauchy - schwarz inequality and the stationarity of the process @xmath209 under @xmath239 , this sum is bounded by @xmath240}^{1/2}.\ ] ] esimate ( [ controlrest ] ) then follows from corollary  [ corpoly ] . this concludes the proof of the theorem . we finally turn to the proof of proposition  [ p : specexp ] , which is a discrete - time counterpart of ( * ? ? ? * theorem  5 ) . in ( * theorem  5 ) however , we had proved in addition that the spectral exponents are at least @xmath241 , which is sharper than the exponents of proposition  [ p : specexp ] for @xmath242 . in particular for @xmath242 the bounds of ( * ? ? ? * theorem  5 ) follow from results of @xcite , whose adaptation to the discrete time setting is not straightforward . as shown above , the present statement is sufficient to prove the optimal scaling of the systematic error , and we do not investigate further this issue . the proof of proposition  [ p : specexp ] is rather involved and one may wonder whether this is worth the effort in terms of the application we have in mind  namely theorem  [ syserr ] . in order to obtain the optimal convergence rate in theorem  [ syserr ] we need the spectral exponents to be larger than @xmath243 . proving that the exponents are at least @xmath243 is rather direct using results of @xcite ( see the first three steps of the proof of proposition  [ p : specexp ] ) . yet proving that they are larger than @xmath243 for @xmath244 is as involved as proving proposition  [ p : specexp ] itself . this is the reason why we display the complete proof of proposition  [ p : specexp ]  although the precise values of the spectral exponents are not that important in the context of this paper . the present proof is a direct version of the proof of ( * ? ? ? * theorem  5 ) . in particular , the proof of ( * ? ? ? * theorem  5 ) relies on a nontrivial ( weaker ) estimate of the spectral exponents obtained in @xcite using a covariance estimate . yet if one wants to extend these results to more general statistics of the conductivity function  for instance to mixing coefficients in the sense of dobrushin and shlosman  one has to give up the covariance estimate ( which we are not able to prove any longer , see @xcite ) . with this in mind we only rely on the variance estimate of ( * ? ? ? * lemma  2.3 ) . our strategy is similar to the strategy used for ( continuous ) elliptic equations in @xcite to prove the estimate of the systematic error . in particular we directly focus on the spectral exponents rather than on some other quantity like the systematic error itself . yet we will go slightly further . starting point is the inequality : @xmath245 which follows from the fact that for @xmath246 , @xmath247 ( here and below @xmath248 and @xmath249 stand respectively for @xmath250 and @xmath251 up to multiplicative constants ) . the variable @xmath252 for @xmath253 large plays the role of @xmath254 in . in what follows we make the standard identification between stationary functions @xmath255 of both the space variable @xmath256 and the environment @xmath28 and their translated versions at 0 @xmath257 depending on the environment only . we define @xmath258 as the unique stationary solution to @xmath259 whose existence and uniqueness follow from lax - milgram s theorem in @xmath260 using the identification between the stationary function @xmath258 and its version defined on the environment only ( see a similar argument of @xcite ) . in particular , with the notation @xmath261 , @xmath262 where @xmath263 is the operator defined in , and the spectral theorem ensures that @xmath264 where @xmath265 is the spectral measure of @xmath263 projected on the drift @xmath266 . we also let @xmath267 be the unique stationary solution to @xmath268 whose existence and uniqueness also follows from lax - milgram s theorem in the probability space as well . this time , @xmath269 and the spectral theorem yields @xmath270 from now on , we shall use the shorthand notation @xmath271 and @xmath272}={\left\langle ( u-{\left\langle u \right\rangle})^2 \right\rangle}$ ] for all @xmath273 . in particular the identity above turns into @xmath274},\ ] ] since @xmath275}\int \psi_t p \ \d \mathbb{p}=\frac{t}{\mathbb{e}[p]}\int \phi_t p \ \d \mathbb{p } = 0 $ ] using equations and . the rest of the proof , which is dedicated to the estimate of @xmath276}$ ] , is divided in six steps . starting point is the application of the variance estimate of ( * ? ? ? * lemma  2.3 ) to @xmath267 , which requires to estimate the susceptibility of @xmath267 with respect to the random coefficients . in view of it is not surprising that we will have to estimate not only the susceptibility of @xmath267 but also of @xmath258 and of some green s function with respect to the random coefficients . in the first step , we establish the susceptibility estimate for the green s function . in step  2 we turn to the susceptibility estimate for the approximate corrector @xmath258 . we then show in step  3 that , relying on @xcite , this implies that the spectral exponents are at least @xmath277 following step is to estimate the susceptibility of @xmath267 . in step  5 we show that this , combined with the suboptimal estimates @xmath278 obtained using , allow us to improve the spectral exponents to @xmath279 in the last step , we quickly argue that in turn these spectral exponents yield the optimal and suboptimal estimates @xmath280 which finally bootstrap to the desired estimates of the spectral exponents , and consequently yield the following optimal estimate of @xmath276}$ ] : @xmath281 } \,\lesssim \ ,   \left| \begin{array}{rcl } t^2\ln^qt & \mbox { for } & d=2,\\ t^{3/2}&\mbox { for } & d=3,\\ t & \mbox { for } & d=4,\\ \sqrt{t}&\mbox { for } & d=5,\\ \ln t&\mbox { for } & d=6,\\ 1&\mbox { for } & d>6 . \end{array } \right.\ ] ] we do not need step  6 to prove theorem  [ syserr ] . yet this step is interesting in itself since it may be the starting point of a subtle `` multi - level '' induction to obtain the sharp spectral exponents in any dimension . _ step _ 1 . susceptility of the green s function . for all @xmath282 we define the green s function @xmath283 with singularity at @xmath37 as the unique solution in @xmath284 to the equation @xmath285 using lax - milgram s theorem . we shall prove for all @xmath286 , @xmath256 , @xmath287 , @xmath288 and @xmath289 where @xmath290 satisfies for some constant @xmath291 ( depending on @xmath292 ) @xmath293 for @xmath244 , and @xmath294 for @xmath8 . we define the elliptic operator @xmath295 as @xmath296 so that takes the form @xmath297 formally differentiating this equation with respect to @xmath90 yields @xmath298 using this identity turns into @xmath299 formally erasing the operator @xmath295 on the l.  h.  s.  then yields the desired identity . to turn this into a rigorous argument , we may proceed as in ( * ? ? ? * proof of lemma  2.5 ) , first consider finite differences instead of derivative w.  r.  t.  @xmath90 , use that @xmath295 is bijective on @xmath284 , and then pass to the limit . we leave the details to the reader and directly turn to . from we infer that @xmath300 using then the uniform pointwise estimate @xmath301 ( see ( * ? ? ? * corollary  2.3 ) , whose proof holds as well in the present case with a non - constant zero order term since @xmath302 ) , the uniform pointwise estimate of the green s function from ( * ? ? ? * lemma  3 ) , and considering this identity as an ode for @xmath303 in function of @xmath90 , we obtain . _ step _ 2 . susceptibility of the approximate corrector @xmath258 .    in this step we shall prove that for @xmath304 , @xmath305 and @xmath287 , @xmath306 @xmath307 @xmath308 and for all @xmath309 , @xmath310 as for the green s function , we rewrite the defining equation for @xmath258 as @xmath311 formally differentiating w.  r.  t. @xmath90 yields @xmath312 which using turns into @xmath313 this ( formally ) shows . to turn this into a rigorous argument , we may use the green representation formula @xmath314 where @xmath315 denotes the sum over all @xmath316 , and proceed as in ( * ? ? ? * proof of lemma  2.4 ) . we now turn to . this estimate follows from , , and the following two facts : @xmath317 starting point to prove is the green representation formula in the form of @xmath318 from which we deduce the claim by a dyadic decomposition of space combined with cauchy - schwarz inequality and ( * ? ? ? * lemma  2.9 ) ( a similar calculation is detailed in ( * ? ? ? * proof of lemma  4 ) ) . for , we first note that implies @xmath319 which  seen as an ode w.  r.  t. @xmath90  yields the claim using the uniform bound @xmath301 of ( * ? ? ? * corollary  2.3 ) and . estimate is a direct consequence of , whereas follows from the leibniz rule combined with , , and . _ step _ 3 . proof of . the estimates of the spectral exponents follow from the more general estimates : for all @xmath320 there exists @xmath321 such that @xmath322 combined with the fact that @xmath323 the proof of is an adaptation of ( * ? ? ? * proof of proposition  2.1 ) which already covers the case of a constant coefficient in the zero order term of @xmath295 , that is for @xmath324 instead of @xmath325 ( no randomness in the zero order term ) . the first step to apply the variance estimate of ( * ? ? ? * lemma  2.3 ) is to show that @xmath258 is measurable with respect to cylindrical topology associated with the random variables . this can be proved exactly as in ( * ? ? ? * lemma  2.6 ) . the estimates , , , and of steps  1 and  2 are like in the auxiliary lemmas of @xcite provided we replace the terms @xmath326 in ( * ? ? ? * lemmas  2.4 &  2.5 ) by @xmath327 . a close look at the proof of ( * ? ? ? * proposition  2.1 ) shows that these terms @xmath326 are either estimated by the green s function itself ( in which case the additional term @xmath328 is of higher order ) , or they are controlled on dyadic annuli by the meyers estimate ( * ? ? ? * lemma  2.9 ) . this lemma shows in particular that there exists @xmath329 such that for all @xmath330 , @xmath331 and @xmath332 , @xmath333 by the properties for @xmath244 and for @xmath8 of the function @xmath334 , it is easy to see that for @xmath244 @xmath335 as well , whereas for @xmath8 @xmath336 hence the proof of ( * ? ? ? * proposition  2.1 ) adapts mutadis mutandis to the present case ( with possibly an additional logarithmic correction for @xmath8 ) , and we have . _ step _ 4 . susceptibility of @xmath267 .    in this step we shall prove that for @xmath337 , @xmath305 and @xmath287 , @xmath338 and @xmath339 where @xmath340 starting point is again the green representation formula @xmath341 associated with in the form @xmath342 differentiated w.  r.  t. @xmath90 it turns into @xmath343 combined with , , and the green representation formula itself , this shows . we now turn to and treat each term of the r.  h.  s. of separately . we begin with the third line of , appeal to , then bound the gradient of the approximate corrector @xmath344 by the approximate corrector @xmath345 itself , control the green s function @xmath346 by @xmath334 , and use to estimate the supremum in @xmath90 of the gradient of the green s function @xmath347 . this term is thus controlled by the second term of the r.  h.  s. of . the term in the fourth line of is also estimated by the second term of the r.  h.  s. of using ( and the uniform bounds @xmath348 ) , whereas the last two terms of are bounded by the first term of the r.  h.  s. of using . the subtle terms are the first three ones , for which we have to estimate the suprema of @xmath349 , @xmath350 , and @xmath351 w.  r.  t. @xmath90 . we begin with the following two estimates @xmath352 which  considered as a system of two coupled odes show that there exists some @xmath353 such that for all @xmath354 , @xmath355 to prove we consider as an ode on @xmath356 , bound @xmath357 by @xmath358 , and use that the four last terms of the r.  h.  s. of are bounded by the second term of the r.  h.  s. of , as discussed above . hence turns into @xmath359 using the uniform bounds @xmath360 , and replacing the gradient of the green s function by the green s function itself in the integral  which we then control by @xmath361  , this estimate yields by integrating the ode . we now turn to and infer from that @xmath362 proceeding as from to , this implies , and therefore and . combining the inequality @xmath363 with and yields the last estimate we need : @xmath364    we are finally in position to conclude the proof of : the first three terms of the r.  h.  s.  of are estimated by , , and . replacing then the gradient of the green s function by the green s function itself , and the green s function by @xmath334 , we obtain , as desired . _ step _ 5 . proof of . this is an application of the variance estimate ( * ? ? ? * lemma  2.3 ) on @xmath267 based on . in particular , @xmath365}\,\lesssim\,\sum_{e\in \mathbb{b}}{\left\langle \sup_{\omega_e}\left| \frac{\partial \psi_t(0)}{\partial \omega_e } \right|^2 \right\rangle}.\ ] ] we distinguish the contributions of the two terms of the r.  h.  s. of in this sum and use the notation @xmath366 the contribution of the first term is estimated as follows : @xmath367 by stationarity of @xmath258 , @xmath267 , and @xmath368 . combined with for @xmath369 , and ( which is proved below ) , this turns into @xmath370 estimate is a consequence of the estimate of the spectral exponents and of the spectral representations @xmath371 since @xmath372 , and by definition of the spectral exponents . we now turn to the second term of the r.  h.  s. of ( [ eq : step-4 - 2 ] ) , and note that it coincides with the term treated in ( * ? ? ? * step  3 , proof of lemma  5 ) so that we have @xmath373 hence , , , and yield for @xmath244 using and . note that is not optimal for @xmath8 in view of the estimate of @xmath374 in ( which is sharper ) . this comes from our estimate of @xmath375 where we have replaced a gradient of the green s function by the green s function itself and therefore given up some potential better decay ( at least integrated on dyadic annuli ) . in high dimensions however , there is no loss because @xmath334 is then square - integrable itself . anyway , the optimal spectral exponents for @xmath8 have been already obtained in .    _ step _ 6 . proof of . we quickly show how allows to get the sharper spectral exponents . this is the same argument as in step  5 , except that can now be boostrapped to using and @xmath376 where @xmath377 has been defined in step  4 . proceeding as in the end of step  5 this yields the spectral exponents , and concludes the proof of the proposition . in this section , we show that the computable quantity @xmath81 defined in ( [ defhata ] ) is a good approximation of @xmath68 , in the sense that its random fluctuations are small as soon as @xmath83 is large . we write @xmath378 for @xmath379 . [ randfluc ] there exists @xmath380 such that , for any @xmath381 , @xmath382 and @xmath1 large enough , @xmath383 { \leqslant}\exp\left ( - \frac{n { \varepsilon}^2}{c t^2}\right).\ ] ]    in order to prove this result , we rewrite @xmath81 as @xmath384 where @xmath385},\ ] ] and @xmath386}.\ ] ] both are sums of independent and identically distributed random variables under  @xmath97 , thus enabling us to use standard tools from large deviations theory . we start with the following classical but instructing fact . [ gdhatp ] there exists @xmath387 such that , for any @xmath388 and any small enough @xmath382 : @xmath389 { \leqslant}\exp\left ( - n { \varepsilon}^2/c_0 \right).\ ] ]    let @xmath390 $ ] . it suffices to show that , for some @xmath391 , @xmath392 { \leqslant}\exp(- n { \varepsilon}^2 / c).\ ] ] chebyshev s inequality implies that , for any @xmath393 , @xmath394 & { \leqslant } & e^{-n { \varepsilon}\lambda } { \mathbb{e}}^\otimes\left[\exp(\lambda({\overline}{p}({\omega}^{(1)})+ \cdots + { \overline}{p}({\omega}^{(n)}))\right ] \\ & { \leqslant } & e^{-n { \varepsilon}\lambda } { \mathbb{e}}\left[\exp(\lambda{\overline}{p}({\omega}))\right]^n.\end{aligned}\ ] ] using a series expansion of the exponential , one can check that there exists @xmath391 such that , for any @xmath395 small enough , @xmath396 { \leqslant}c \lambda^2.\ ] ] as a consequence , for any @xmath395 small enough , @xmath397 { \leqslant}\exp\left ( -n ( \lambda { \varepsilon}- c \lambda^2 ) \right),\ ] ] and for @xmath398 , the latter term becomes @xmath399 . the event @xmath400 can be handled the same way , and we thus obtain ( [ oneside ] ) .    what makes the proof of proposition  [ gdhatp ] work is the observation ( [ loglapl ] ) that the log - laplace transform of @xmath401 $ ] is quadratic close to the origin . in order to prove the corresponding result for @xmath402 , we will need to control the log - laplace transform of @xmath403 uniformly in @xmath1 . to that end , we use a sharp upper bound on the transition probabilities of the random walk recalled in the following theorem . we refer the reader to @xcite or ( * ? ? ? * theorem  14.12 ) for a proof . [ gauss ] there exists a constant @xmath404 such that , for any environement @xmath28 with conductances in @xmath405 $ ] , any @xmath406 and @xmath20 , @xmath407 { \leqslant}\frac{c_1}{t^{d/2 } } \exp\left(- \frac{|x|^2}{c_1 t } \right).\ ] ]    from theorem  [ gauss ] we deduce the following result . [ supexp ] let @xmath408 be given by theorem  [ gauss ] . for all @xmath409 , one has @xmath410 < + \infty.\ ] ]    let @xmath411 . by theorem  [ gauss ] , @xmath412 { \leqslant}c_1 { t^{-d/2 } } \sum_{x \in { \mathbb{z}}^d } e^{-\delta |x|^2/t}.\ ] ] if the sum ranges over all @xmath413 , it is easy to bound it by a convergent integral : @xmath414 by symmetry , the estimate carries over to the sum over all @xmath415 . the same argument applies for the sum over all @xmath416 having exactly one component equal to @xmath43 , and so on . the following lemma contains the required uniform control on the log - laplace transform of @xmath403 . [ grandesdev ] there exist @xmath417 and @xmath418 such that , for any @xmath419 and any @xmath406 , @xmath420 { \leqslant}c_2 \lambda^2.\ ] ]    it is sufficient to prove that there exists @xmath421 such that , for any @xmath395 small enough and any @xmath1 , @xmath422 { \leqslant}1+c_3 \lambda^2.\ ] ] we use the series expansion of the exponential to rewrite this expectation as @xmath423.\ ] ] the term corresponding to @xmath424 is equal to @xmath193 , whereas the term for @xmath425 vanishes . the remaining sum , for @xmath426 ranging from @xmath70 to infinity , can be controlled using corollary  [ supexp ] combined with the bound @xmath427,\ ] ] which follows from the definition of @xmath68 and jensen s inequality . we are now in position to prove theorem  [ randfluc ] . starting point is the inequality @xmath428 \\   { \leqslant}{\mathbb{p}}^\otimes_0\left[a_n(t ) - \sigma_t^2   { \geqslant}{\varepsilon}/ t\right ] + { \mathbb{p}}^\otimes_0\left[a_n(t)(\hat{p}_n^{-1 } - 1 ) { \geqslant}{\varepsilon}/ t\right].\end{gathered}\ ] ] we treat both terms of the r.  h.  s. separately . for the first one , the key observation is that ( recalling the definition of @xmath55 given in ( [ deftdp ] ) ) @xmath429 = { \tilde}{{\mathbb{p}}}^\otimes_0\left[\frac{(\xi \cdot y^{(1)}(t))^2 + \cdots + ( \xi \cdot y^{(n)}(t))^2}{n t } - \sigma_t^2   { \geqslant}{\varepsilon}/ t\right].\ ] ] let @xmath430 . as in the proof of proposition  [ gdhatp ] , we bound this term using chebyshev s inequality : @xmath431 \\ & \qquad { \leqslant}{\tilde}{{\mathbb{e}}}^\otimes_0\left [ \exp\left ( \lambda \left(\frac{(\xi \cdot y^{(1)}(t))^2 + \cdots + ( \xi \cdot y^{(n)}(t))^2}{t } - n \sigma_t^2 \right ) \right ) \right ] \ \exp\left ( -\frac{n \lambda { \varepsilon}}{t } \right )   \\ &   \qquad { \leqslant}{{\tilde}{{\mathbb{e}}}_0\left [ \exp\left ( \lambda \left(\frac{(\xi \cdot y(t))^2}{t } - \sigma_t^2 \right ) \right ) \right]}^n \ \exp\left ( -\frac{n \lambda { \varepsilon}}{t } \right ) . \end{split}\ ] ] by lemma  [ grandesdev ] , the r.  h.  s. of ( [ comput1 ] ) is bounded by @xmath432 for all @xmath395 small enough . choosing @xmath433 ( which is small enough for @xmath1 large enough ) , we obtain @xmath434 { \leqslant}\exp\left ( - \frac{n { \varepsilon}^2}{4 c_2 t^2 } \right),\ ] ] as needed . we now turn to the second term of the r.  h.  s. of ( [ decomp2termes ] ) . from inequality ( [ estim1 ] ) , we infer that there exists @xmath435 such that @xmath436 { \leqslant}\exp\left ( - \frac{n { \varepsilon}^2}{4 c_2 t^2 } \right).\ ] ] since @xmath437 is almost surely bounded by a constant , it is enough to evaluate the probability @xmath438,\ ] ] which is controlled by proposition  [ gdhatp ] .    we have thus obtained the required control of the l.  h.  s. of ( [ decomp2termes ] ) . the probability of the symmetric event @xmath439\ ] ] can be handled the same way . in this section , we illustrate on a simple two - dimensional example the sharpness of the estimates of the systematic error and of the random fluctuations obtained in theorems  [ syserr ] and  [ randfluc ] .    in the numerical tests , each conductivity of @xmath26 takes the value @xmath440 or @xmath441 with probability @xmath442 . in this simple case , the homogenized matrix is given by dykhne s formula , namely @xmath443 ( see for instance ( * ? ? ? * appendix  a ) ) . for the simulation of the random walk , we generate  and store  the environment along the trajectory of the walk . in particular , this requires to store up to a constant times @xmath1 data . in terms of computational cost , the expansive part of the computations is the generation of the randomness . in particular , to compute one realization of @xmath444 costs approximately the generation of @xmath445 random variables . a natural advantage of the method is its full scalability : the @xmath446 random walks used to calculate a realization of @xmath444 are completely independent . we first test the estimate of the systematic error : up to a logarithmic correction , the convergence is proved to be linear in time . in view of theorem  [ randfluc ] , typical fluctuations of @xmath447 are of order no greater than @xmath448 , and thus become negligible when compared with the systematic error as soon as the number @xmath449 of realizations satisfies @xmath450 . we display in table  [ tab : syst ] an estimate of the systematic error obtained with @xmath451 realizations . the systematic error is plotted on figure  [ fig : syst ] in function of the time in logarithmic scale . the apparent convergence rate ( linear fitting ) is @xmath452 , which is consistent with theorem  [ syserr ] , which predicts @xmath453 and a logarithmic correction .     for @xmath451 realizations ] we now turn to the random fluctuations of @xmath454 . theorem  [ randfluc ] gives us a large deviation estimate which essentially says that the fluctuations of @xmath447 have a gaussian tail , measured in units of @xmath448 . the figures  [ fig : histo-1]-[fig : histo-4 ] display the histograms of @xmath455 for @xmath456 and @xmath457 ( with 10000 realizations of @xmath444 in each case ) . as expected , they look gaussian .    ]    ]    ]    ] the authors acknowledge the support of inria through the `` action de recherche collaborative '' disco . this work was also supported by ministry of higher education and research , nord - pas de calais regional council and feder through the `` contrat de projets etat region ( cper ) 2007 - 2013 '' . g.c . papanicolaou and s.r.s . boundary value problems with rapidly oscillating random coefficients . in _ random fields , vol . i , ii ( esztergom , 1979 ) _ , volume  27 of _ colloq . jnos bolyai _ , pages 835873 . north - holland , amsterdam , 1981 .
this article is devoted to the analysis of a monte - carlo method to approximate effective coefficients in stochastic homogenization of discrete elliptic equations . 
 we consider the case of independent and identically distributed coefficients , and adopt the point of view of the random walk in a random environment . given some final time @xmath0 , a natural approximation of the homogenized coefficients is given by the empirical average of the final squared positions rescaled by @xmath1 of @xmath2 independent random walks in @xmath2 independent environments . 
 relying on a new quantitative version of kipnis - varadhan s theorem ( which is of independent interest ) , we first give a sharp estimate of the error between the homogenized coefficients and the expectation of the rescaled final position of the random walk in terms of @xmath1 . 
 we then complete the error analysis by quantifying the fluctuations of the empirical average in terms of @xmath2 and @xmath1 , and prove a large - deviation estimate . 
 compared to other numerical strategies , this monte - carlo approach has the advantage to be dimension - independent in terms of convergence rate and computational cost . 
 * keywords : * random walk , random environment , stochastic homogenization , effective coefficients , monte - carlo method , quantitative estimates .    * 
 2010 mathematics subject classification : * 35b27 , 60k37 , 60h25 , 65c05 , 60h35 , 60g50 .