Function design: “stateless” recursive asymptotic to 1

I'm trying to design a function with the following requirements:

• it will be implemented in an electronic device, where it will be called a discrete number of times. However, it will only be given the previous value $$y_{prev}$$. This is "stateless" in the sense that I don't have access to a discrete counter of the number of time the function is called (i.e., $$x$$). In other words, it must be expressed as $$y = f(y_{prev})$$.
• $$y_{prev}$$ is initialized at an arbitrary positive small $$ε$$ (e.g., 0.001) before the function is ever called.
• the function is asymptotic to 1
• the function is increasing monotonic and has decreasing first derivative. In other words, it has a shape similar to a log function like: sample shape

Thanks!

• If we start with some $y_0=\epsilon$, as you write, and define $y_{n+1}=f(y_n)$ for $n\ge 0$, do you expect $\lim_{n\to\infty}y_n=1$ to hold? If yes, note that this is quite different from the condition that the function $f$ is asymptotic to $1$. – Ingix May 18 '19 at 9:39
• Yes @Ingix that's correct, but why wouldn't you call that function "asymptotic to 1"? – Piguasco May 18 '19 at 18:17

To restate, you want to design and implement a function $$f: \mathbb R^+ \to \mathbb R^+$$, then choose a starting value $$y_0=\epsilon$$ and iterate the function $$f$$ over it:

$$y_{n+1}:=f(y_n)\quad \forall n\ge 0.$$

Such a sequence is formally understood to be a function $$y: \mathbb N \to \mathbb R^+$$ via $$y(n)=y_n \;\forall n \ge 0$$.

At the end you state some requirements for "the function":

• the function is asymptotic to 1
• the function is increasing monotonic and has decreasing first derivative. In other words, it has a shape similar to a log function like

Now what made William Elliot give the 'incorrect answer' from your point of view is that William applied the requirements to the function $$f,$$ while you wanted them applied to the function $$y.$$

Once that is clear, one has to slightly change the requirement for the first derivative being decreasing, as sequences don't have derivatives. But an 'equivalent' formulation can be found, considering that

$$\frac{y_{n+1}-y_n}{(n+1)-n} = y_{n+1}-y_n$$

can be considered the equivalent of the derivative:

$$y_{n+2} - y_{n+1} < y_{n+1} - y_n. \tag{1} \label{eq1}$$

Considering this, your desired function $$f$$ can be relatively simple, for example

$$f(y):=\frac{1+y}2$$

works.

We have

$$1-y_{n+1}=1-\frac{1+y_n}2 = \frac{1-y_n}2,$$

which means that the term $$1-y_n$$ will halve in each iteration, so $$\lim_{n\to\infty}y_n=1$$.

If $$0 \le y_0 < 1$$, then per indunction we get easily $$0 \le y_n < 1\; \forall n \ge 0$$. We have for each $$n$$ $$y_{n+1} - y_n=\frac{1+y_n}2 -y_n = \frac{1-y_n}2 > 0,$$ the last inequality following from $$y_n < 1.$$ So $$y_n$$ is increasing.

To verify $$\eqref{eq1}$$, we use what we've just shown

$$y_{n+2} - y_{n+1} = \frac{1-y_{n+1}}2 = \frac12 \frac{1-y_n}2 < \frac{1-y_n}2 = y_{n+1}-y_n.$$

• Thank you, this is exactly what I wanted. Why didn't I think of it? You're right for the "first derivative being decreasing", but you get what I meant :) – Piguasco May 19 '19 at 11:48
• @Piguasco If you want faster/slower convergence, use $f(y)=\frac{1+(k-1)y}k$ for some real $k > 1$. Higher $k$ means slower convergence. – Ingix May 19 '19 at 13:53
• Yes, actually I used something similar: $f(y) = k + (1-k)y_{prev}$ where $0 < k < 1$. Very cheap function to implement on an embedded device. Thanks again. – Piguasco May 20 '19 at 13:40

$$f(x) = 1 - e^{-x}$$

• That's not in the form $y=f(y_{prev})$ I mentioned above. – Piguasco May 18 '19 at 8:39
• @Piguasco If you make the trivial substiution $x-->y$, what condition do you think this function is violating? – Ingix May 18 '19 at 9:35