Consider a recurrence relation $x_n = f(x_{n-1})$. Suppose $f(x_n)<0$ for some "large enough" $n$. Now consider a "stochastic variant" $x_n = f(x_{n-1})+y_n$ where $y_n$ is a sequence of random variables. Under what conditions will there again exist a "large enough" $n$ such that $x_n < 0$ ? E.g. does some $c$ exist such that this "convergence" holds if e.g. $|y_n| < c$ etc? I am looking for general ideas of attack / references. I am actually interested in the "multidimensional / linear algebra" case for a vector $\mathbf x$ but am ok with theory / solution starting from a single variable.

  • $\begingroup$ I think there's very little that can be said without more information about $f$. What sort of function is it? $\endgroup$ – Qiaochu Yuan Sep 14 '17 at 5:48
  • $\begingroup$ can it be solved with any assumptions/ simplifications on $f$? $f$ can be regarded as analytic/ exponential function from (non)homogenous linear recurrence relation. $\endgroup$ – vzn Sep 14 '17 at 15:17
  • $\begingroup$ idea: can $f$ be seen as (following some increment of) a derivative of some function? then the problem is asking about convergence of "gradient descent" even with random perturbations (quite similar to "simulated annealing"). the apparent relevant theory is from dynamical systems/ stability theory $\endgroup$ – vzn Sep 15 '17 at 21:13
  • $\begingroup$ update, as stated it appears to be the autoregressive model and vector version seems to be a matrix/ linear algebra variant of the problem, havent found it studied specifically yet, would still like to find that, maybe in some engineering context, but right now thinking autoregressive techniques are applicable/ translate... $\endgroup$ – vzn Sep 18 '17 at 4:28
  • $\begingroup$ also called a multivariate AR(1) process, still cant find a general ref though :( $\endgroup$ – vzn Sep 24 '17 at 16:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.