|
|
| Author |
Message |
Guest
|
 Posted: Tue May 03, 2005 8:35 pm Post subject:
Annoying recursion
|
|
|
I have been stuck on the following recursion for a while and thought
that I would ask for some help:
Let n be a (large) positive integer and c a constant such that 0 < c <
1. Now consider the following recursion
n_0 = n
n_i = n_{i-1}(1-c^{n_{i-1}/n}) for i>0
I am interested in knowing asymptotically how fast n_i decreases as a
function of n and c. Specifically I am seeking a formula for the
smallest value of i such that n_i = 1.
Note that the recursion can also be rewritten as
n_i = n prod(j=0,i-1)(1 - c^{n_j/n}) for i>0
| Quote: | From this it follows that n_i <= n(1-c)^i and thus n_i <= 1 is true for
i = (log n)/(-log(1-c)) = O(log n). But I am wondering if one can show |
a lower bound on i (or show that this is the best one can do
asymptotically).
Another way to rewrite the recursion is as
n_i = n prod(j=0,i-1)(1 - x_j) for i>0
where x_0 = c and x_j = x_{j-1}^{1-x_{j-1}} for j>0.
Any help would be much appreciated!
Regards
Fredrik Manne
fredrikm *AT* ii.uib.no |
|
| Back to top |
|
 |
Karl Fabian
science forum beginner
Joined: 04 May 2005
Posts: 3
|
| Posted: Wed May 04, 2005 12:05 pm Post subject:
Re: Annoying recursion
|
|
|
| Quote: | I have been stuck on the following recursion for a while and thought
that I would ask for some help:
Let n be a (large) positive integer and c a constant such that 0 < c
1. Now consider the following recursion
n_0 = n
n_i = n_{i-1}(1-c^{n_{i-1}/n}) for i>0
I am interested in knowing asymptotically how fast n_i decreases as a
function of n and c. Specifically I am seeking a formula for the
smallest value of i such that n_i = 1.
Note that the recursion can also be rewritten as
n_i = n prod(j=0,i-1)(1 - c^{n_j/n}) for i>0
From this it follows that n_i <= n(1-c)^i and thus n_i <= 1 is true for
i = (log n)/(-log(1-c)) = O(log n). But I am wondering if one can show
a lower bound on i (or show that this is the best one can do
asymptotically).
Another way to rewrite the recursion is as
n_i = n prod(j=0,i-1)(1 - x_j) for i>0
where x_0 = c and x_j = x_{j-1}^{1-x_{j-1}} for j>0.
Any help would be much appreciated!
Regards
Fredrik Manne
fredrikm *AT* ii.uib.no
|
This is a very crude approximation:
Set
a_i = n_i/n |log c|
then the recursion becomes
a_0 = |log c|
a_{i+1} = a_i (1- exp(-a_i)) (1)
Since 0 < a_i <= a_0
the sequence converges to 0.
From (1) the finite difference quotient is
a_{i+1} - a_i = - a_i exp(-a_i)
Replacing the left side by da/dt one obtains the
similar differential equation
da/dt = - a(t) exp(-a(t)), a(0) = |log c|
with solution
Ei (a(t)) = Ei(|log c|) - t.
For sufficiently small a(t) the exponential integral Ei
is about gamma + log(a(t))
and
a(t) ~ exp(-t) exp(Ei(|log c|) -gamma)
Perhaps this helps to approach your problems.
Karl |
|
| Back to top |
|
|
Google
|
|
| Back to top |
|
|
|
|
The time now is Fri Jan 09, 2009 10:35 pm | All times are GMT
|
|
Mobile Phone | Bankruptcy | Loans | Prepaid Credit Cards | TurboTax
|
|
Copyright © 2004-2005 DeniX Solutions SRL
|
|
Other DeniX Solutions sites:
Electronics forum |
Medicine forum |
Unix/Linux blog |
Unix/Linux documentation |
Unix/Linux forums
|
Powered by phpBB © 2001, 2005 phpBB Group
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
Forum index
»
Science and Technology
»
Math
