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$
$\endgroup$
6
-
$\begingroup$ I think there's very little that can be said without more information about $f$. What sort of function is it? $\endgroup$– Qiaochu YuanSep 14, 2017 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$– vznSep 14, 2017 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$– vznSep 15, 2017 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$– vznSep 18, 2017 at 4:28
-
$\begingroup$ also called a multivariate AR(1) process, still cant find a general ref though :( $\endgroup$– vznSep 24, 2017 at 16:58
|
Show 1 more comment