TITLE: How to determine when a rounded sequence "converges" and what the convergence value is
QUESTION [0 upvotes]: I have a process on a server that iteratively computes a value over time. The value follows a fairly simple formula, which would generate a convergent sequence; however, the value of the formula is rounded up. Thus, the sequence after a certain number of indexes actually reaches the limit, and then all future values also equal the limit (this seems to be a little different from the definition of convergence, hence the scare quotes in the title). I need to program a method of determining how long the server will take before reaching the equilibrium value, as well as what that value is. For the length of time, I know the time frame of iterations, I just need to know the number of iterations. 
I can easily compute sequence members until the value repeats, then count the number of members to the get the number of iterations, but I am interested in whether there is an analytic way of computing the value, since it would be much more efficient. I assume there is not (due to the rounding), but perhaps I am not thinking of a property of rounding that can be used to create such an expression.
The details:
$$
x_n = Ceiling(p(x_{n-1})+k)
$$
If $k=1600; p=.95$, 
$$
x_0=0
\\x_1=1600
\\x_2=3120
\\.
\\.
\\.
\\x_{155}=31999
\\x_{156}=32000
\\x_{157}=32000
$$
Thus, the sequence converges after 156 iterations at 32,000. Is there a way to determine these values without computing the sequence?
For non-negative integers, the value at convergence $=k/.05$. For negative integers and non-integer real numbers the formula breaks down. Luckily, currently, $k$ only takes on positive integer values. However, I'd be interested in a more general formula.

REPLY [2 votes]: If $x_n = \lceil p x_{n-1} + k \rceil$, a fixed point $x_n = a$ would have to satisfy $a-1 < p a + k \le a$, thus (if $p < 1$)
$$  \dfrac{k}{1-p} \le a < \dfrac{k+1}{1-p}$$
If there were only one integer in the interval $[k/(1-p), (k+1)/(1-p))$, then that would be the only possible fixed point.  But in your example, $k/(1-p) = 32000$  and $(k+1)/(1-p) = 32020$.  All integers from $32000$ to $32019$ are fixed points.  
Now since  $f(x) = \lceil p x + k \rceil$ is a nondecreasing function, it's not hard to show that 
for any $x_0 < 32000$, we will have $x_n \le 32000$ for all $n$, that $x_n$ is a nondecreasing sequence (so the limit exists because a nondecreasing sequence bounded above has a limit), and that the limit is $32000$.
As for estimates on how many iterations, you might note that 
$p x_{n-1} + k \le x_{n+1} \le p x_{n-1} + k + 1$; the linear iterations $u_{n+1} = p u_n + k$ and $v_{n+1} = p v_n + k+1$ starting at $u_0 = v_0 = 0$ have solutions 
$$u_n = \dfrac{1-p^n}{1-p} k,\ v_n = \dfrac{1-p^n}{1-p} (k+1)$$
and thus $u_n \le x_n \le v_n$.
If $L$ is the limit of $x_n$, then we must have $x_n < L$ when $v_n < L$, but we must have $x_n = L$ when $u_n > L-1$.  Thus we get the following bounds for the first $N$ for which $x_n = L$:
$$ \log_p \left(1 - \frac{L(1-p)}{1+k}\right) \le N \le \log_p \left( 1 - \frac{(L+1)(1-p)}{k} \right) $$
In your example, I get $144 \le N \le 202$.  Admittedly, these are not very tight bounds.  It's likely they could be improved somewhat, but I don't know if it's possible to improve them so much that you get the exact value without computing a significant fraction of the terms $x_1, \ldots, x_N$.
{"set_name": "stack_exchange", "score": 0, "question_id": 1870841}