4
$\begingroup$

I have the following discrete time dynamical system $$ y(t+1) = y(t) + \frac{1}{1+\exp(z+ u f y(t))} ,\quad y(0)=0,$$ where $z$ is a real number $f$ and $u$ are non-negative reals. I know I have little hope of obtaining a closed form solution for this process. But, actually, for my application, a "better" solution involves finding (making the dependence of $y$ on $f$ explicit by writing $y(t)$ as $y(t,f)$): $$\lim_{n \to \infty} \frac{1}{n}\cdot y\left(nt,\frac{f}{n}\right).$$ Update: Initial simulations suggested that this converged to $$y(t) = \frac{t}{1+\exp(z)}.$$ But that was wrong. In conclusion, the differential equation is indeed a good approximation to the above limit. Sorry about the confusion.

How can I rigorously show this? Also appreciated are references to texts that discuss similar problems.

Thanks

$\endgroup$
17
  • 2
    $\begingroup$ The proposed answer is proportional to $f$ but not $u$ . Is there a typo? $\endgroup$
    – T..
    Commented Jul 21, 2010 at 6:48
  • $\begingroup$ @T: I wonder if that f is the same f the OP multiplied by in the line above. It is possible that $\lim n^{-1} y(nt, n^{-1}f)$ is actually independent of $f$. $\endgroup$ Commented Jul 21, 2010 at 10:28
  • $\begingroup$ @T: No I think this is the right formulation @Willie Wong: It is the same f and yes, my simulations suggest that the quantity you are mentioning is independent of f. $\endgroup$
    – Eric Blair
    Commented Jul 21, 2010 at 12:31
  • $\begingroup$ The question will be clearer if you divide the last two equations by $f$: the problem is to determine if the quantity that Willie wrote down converges to $t / (1 + e^z)$. $\endgroup$
    – T..
    Commented Jul 21, 2010 at 17:57
  • $\begingroup$ OK, I made the change you suggested. $\endgroup$
    – Eric Blair
    Commented Jul 21, 2010 at 19:20

1 Answer 1

3
$\begingroup$

The continuous model of the problem suggests that the limit does depend on $f$ (and $u$). More precisely, it depends on how fast the parameter $f$ is suppressed in the expression whose limit you are taking; behavior of $\lim y(nt, f_n)/n$ will depend on the limit of $nf_n$ as $n \to \infty$. The answer will be a function of the limit of $nuf_n$. Only when this limit is zero does one get the proposed formula.

The associated differential equation is $Y' = 1/(1+Ae^{BY})$ where $A = e^z$ and $B=uf$. Its solution vanishing at 0 is $Y(t) = H^{-1}(t)$ where $H(t) = t + (A/B)(e^{Bt} - 1)$. It does look like this matches the asymptotic behavior of your sequence for $y$ both in the large and small range. For small $t$, the expansion $Y(t) = t/(1+A) + O(t^2)$ corresponds to your formula, but I think the answer is not quite that simple: you have to establish whether the expression whose limit is calculated belongs to the small regime where $Y(t)$ is approximately linear, or the large regime where $Y(t)$ is logarithmic, $Y(t)=O(\log(t))$. The limit uses $n$ iterations so we want to know, as a function of $B \sim 1/n$, whether the transition between regimes happens at a point much larger than $1/B$. However, it's easy to calculate that the ratio $H(t)/t$ moves away from 1 (the difference is larger than some constant independent of $B$) as soon as $Bt$ is of order 1 (i.e., bounded below by a given positive constant) and this would spoil the limit if the differential equation is a good model of the difference equation.

(ADDED: for comparison of $Y$ predictions with $y$ simulations, in the phase transition where $Bt$ is of order 1, $Y(t) \sim t/C$ and $H(t) \sim Ct$, with $C = 1 + A(e^q - 1)/q$, and $q = Bt =uft$. That is, $Y$ stays approximately linear but the coefficient goes to zero, consistent with the idea that it's turning into a logarithmic function. Let $t=nt_0, \quad f=f_0/n$, for some constant $f_0$ and with $u$ and $t_0$ also held constant while $f$ varies with $n$, so that the phase transition parameter is $q=uf_0 t_0$ and the predicted value of the limit, if $Y$ is a good approximation for $y$, is $L_{pred} = \lim Y(nt_0,f_0/n)/n = \lim nt_0/nC = t_0/C = t_0(q/(q + Ae^q - A))$. In the original notation of the question, $L = t/(1+{e^z}F(uft))$ where $F(x)=(e^x-1)/x$. Does this match the simulations?)

To see the small-$y$ behavior directly in the difference equation, it can be expanded in powers of $y$.

$y(t+1) - y(t) = 1/(1+A) - (AB)/(1+A)^2)y + O(y^2)$

Your formula proposes that when $B \sim 1/n$, the effect of the $y^{\geq 1}$ terms is of order smaller than $n$ for $t \in [0,n]$. The sum of the first $t$ values of the $y^1$ term will be of order $t^2$, so one expects these corrections to be suppressed only on a short interval, $t << n^{1/2}$. The calculation with the differential equation suggests that $f_n = f/n$ is too large a parameter ; this calculation with the truncated difference equation can be used to prove that $f_n = f/n^k$ is small enough for any $k > 2$. Adding higher degree terms to the approximate difference equation would, I suppose, only get closer to the picture suggested by the differential equation.

To prove rigorously the predictions from the differential equation you could try to control $y$ by trapping the sequence $y(n)$ between two trajectories of the ODE. If simulations are consistent with a heuristically "wrong" formula it would be very interesting to sort out what the truth is.

$\endgroup$
4
  • $\begingroup$ Thank you T. Unfortunately $nf_n$ has to be a constant and actually B is strictly greater than 0. Since I know very little about differential equations, I would like some clarifications. First, what does the notation $y^1$ mean? Second do you have a reference where something like the technique you suggest in the last paragraph is used/demonstrated/worked out? $\endgroup$
    – Eric Blair
    Commented Jul 21, 2010 at 21:12
  • $\begingroup$ By $y^1$ I just meant the term of degree 1 in $y$, i.e., $(AB/(1+A)^2)y(t)$, which is then summed up for $t = 1,2,\dots,t_0$. If $y(t)$ is approximately linear in this range, the sum will be a quadratic function of $t$, plus a smaller error term. This is not quite right because the series expansion of $y(t+1)-y(t)$ was written down assuming that $y$ is small, but the addition of the $1/(1+A)$ terms will make $y$ large. So to do this properly one could write down an expansion of $y(t) - t/(1+A)$, or $y(t) - Y(t)$, or try to show that the $O(y^2)$ quantity is less than $Cy^2$ for all $y$. $\endgroup$
    – T..
    Commented Jul 21, 2010 at 21:42
  • $\begingroup$ I don't know references but some of the ODE/PDE people here on MO might know specific sources where examples like this can be found. The order-of-magnitude calculations such as the sum of y(t+1)−y(t) being (in this approximation) quadratic, are typical of exercises in real analysis books. Finding asymptotic behavior of difference equations by replacing difference with derivative and analyzing the ODE must appear in a lot of books but I don't know which one. Sorry I can't be more specific, if I find something I will post it. $\endgroup$
    – T..
    Commented Jul 21, 2010 at 21:53
  • $\begingroup$ By the way, I should emphasize that everything above is inconclusive until rigorized. The $Y(t)$ discussion is certainly suggestive that things are more complicated than first assumed. But if the numerical simulations were strong enough it is possible that the discrete and continuous problems don't completely match each other in their asymptotic behavior. Only a full analysis with estimates and explicit bounds can clear this up, I think. $\endgroup$
    – T..
    Commented Jul 22, 2010 at 6:58

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .