recursion [Math]

Prev: Godels seconded theorem ends in paradox-simple proof
Next: Is this function convex?

From: sadoc on 28 May 2010 13:28

Hi,

Thanks for the comments regarding the presentation. Now, the
recursion is the following

For i>=1,

x[i + 1] = {[a + (i + 1)m]/a}.x[i] - (im/a).x[i - 1] - 1/a.

When i=1,

x[1] = x[0] - 1/a.

Also,

x[infinity] = 1/m

and x[0] is the unknown quantity.

Finally, x[-1] is not necessary and not well defined (as you
suggested, we might take it to be infinite).

Thanks!

Best regards, Daniel

On May 28, 1:14 pm, Ray Vickson <RGVick...(a)shaw.ca> wrote:
> On May 28, 8:20 am, sadoc <danielsa...(a)gmail.com> wrote:
>
> > Hi,
>
> > thanks for the reply. Yes, the recursion I would like to solve is
>
> > x[i + 1] = (((a + (i + 1)m)/a).x[i]) - ((im/a).x[i - 1]) - (1/a)
>
> For your future reference: your equation is still unnecessarily hard
> to read. You should strip off the brackets around separate terms and
> just write
> x[i + 1] = ((a + (i + 1)m)/a).x[i] - (im/a).x[i - 1] - 1/a.
>
> As long as you leave spaces around the separate terms, the '+' and '-'
> signs will serve to delimit the different terms. Also, you might try
> mixing bracket types when submitting equations written in ASCII, so it
> would be even better to write
> x[i + 1] = {[a + (i + 1)m]/a}.x[i] - (im/a).x[i - 1] - 1/a.
> Do you see how much clearer that is?
>
> R.G. Vickson
>
>
>
> > I forgot to add the boundary conditions, though,
>
> > x[1] = x[0]-1/a
>
> This is a problem: if you put i=0 in the recursion (and assume x[-1]
> is not infinite) you get x[1] = x[0]*(a+m)/a - 1/a. In order to have
> x[1] = x[0] - 1/a you need (a+m)/a = 1, hence m = 0. So, either the
> recursion fails for i = 0 or your boundary condition is wrong.
>
> R.G. Vickson
>
>
>
> > x[0] is unknown but
>
> > x[infinity] = 1/m
>
> > William, x[infinity]=1/m is in line with the solution you proposed..
> > However, I would like to cope with the boundary condition x[1]=x[0]-1/
> > a
>
> > Robert, using Maple, I was able to solve the recursion using
>
> > rsolve({x(n)=(1+(n)*m/a)*x(n-1) - ((n-1)* m/a)*(x(n-2)) - 1/a,
> > x(1)=x0-1/a, x(0)=x0}, x(n));
>
> > However, I get a very complicate solution, and I don't know how to
> > cope with the condition x[infinity]=1/m
>
> > The motivation to the problem I'm trying to solve is the following:
>
> > consider a Markov chain with the following generator matrix
>
> > q(i,i+1) = a (i>=0)
> > q(i,i-1) = im (i>=1)
> > q(i,-1) = m (i>=1)
>
> > Question: given that we start in state s, s >=0, what is the mean time
> > to reach state -1?
>
> > I think that this is related to birth-death processes with killing...
>
> > Thanks again!
>
> > Best regards, Daniel
>
> > On May 28, 5:20 am, William Elliot <ma...(a)rdrop.remove.com> wrote:
>
> > > On Fri, 28 May 2010, sadoc wrote:
> > > > Please, how can I solve the following recursion?
>
> > > > x[ i + 1 ] = ( ( ( a + ( i + 1) m ) / a ) x[ i ] ) - ( ( i
> > > > m / a ) x[ i - 1 ] ) - ( 1 / a )
>
> > > Yicks. Is this what you wrote?
>
> > > x[i + 1] = (((a + (i + 1)m)/a).x[i]) - ((im/a).x[i - 1]) - (1/a)
>
> > > Besides needing to state a /= 0, it needs to be simplified.
>
> > > a.x[i + 1] = (a + (i + 1)m).x[i] - im.x[i - 1] - 1
>
> > > A random thought occurs;
> > > a(x[i + 1] - x[i]) = (i + 1)m.x[i] - im.x[i - 1] - 1
>
> > > a(x[i + 1] - x[i]) = im(x[i] - x[i - 1]) + m.x[i] - 1
>
> > > Let's solve the case m = 0.
>
> > > a(x[i + 1] - x[i]) = -1; x[i + 1] = x[i] - 1/a
>
> > > For all i in N, x[i] = x[0] - i/a is the solution.
>
> > > Regards the case m /= 0,
> > > for all i in N, x[i] = x[0] = 1/m
> > > is a solution.
>
> > > Let's examine the case for all i, x[i + 1] - x[i] = t.
>
> > > at = imt + m.x[i] - 1; m.x[i] = at - imt + 1
>
> > > For all i,
> > > x[i] = at/m + 1/m - it
> > > isn't a solution if t /= 0, because
> > > x[i + 1] - x[i] = -t,
> > > contrary to the assumption
> > > x[i + 1] - x[i] = t.
>
>

From: Ray Vickson on 29 May 2010 18:46

On May 28, 8:20 am, sadoc <danielsa...(a)gmail.com> wrote:
> Hi,
>
> thanks for the reply. Yes, the recursion I would like to solve is
>
> x[i + 1] = (((a + (i + 1)m)/a).x[i]) - ((im/a).x[i - 1]) - (1/a)
>
> I forgot to add the boundary conditions, though,
>
> x[1] = x[0]-1/a
>
> x[0] is unknown but
>
> x[infinity] = 1/m
>
> William, x[infinity]=1/m is in line with the solution you proposed.
> However, I would like to cope with the boundary condition x[1]=x[0]-1/
> a
>
> Robert, using Maple, I was able to solve the recursion using
>
> rsolve({x(n)=(1+(n)*m/a)*x(n-1) - ((n-1)* m/a)*(x(n-2)) - 1/a,
> x(1)=x0-1/a, x(0)=x0}, x(n));
>
> However, I get a very complicate solution, and I don't know how to
> cope with the condition x[infinity]=1/m
>
> The motivation to the problem I'm trying to solve is the following:
>
> consider a Markov chain with the following generator matrix
>
> q(i,i+1) = a (i>=0)
> q(i,i-1) = im (i>=1)
> q(i,-1) = m (i>=1) <------ do you really mean you cannot get directly from
state 0 to state -1? I will assume
so below.

If this is really your problem, I think you have the wrong recursion.
If we let x[i] = expected time to reach the absorbing state -1 from
state i >= 0 then I get:

x[0] = (1/a) + x[1]
x[1] = 1/(a + 2m) + [m/(a + 2m)]*x[0] + [a/(a + 2m)]*x[2]
x[2] = 1/(a + 3m) + [2m/(a + 3m)]*x[1] + [a/(a + 3m)]*x[3],

and in general:

x[i] = 1/(a + (i+1)m) + [im/(a + (i+1)a)]*x[i-1] + [a/(a+(i+1)m)]*x[i
+1]

Maple 9.5 can solve this, but the result is very complicated.

R.G. Vickson

> Question: given that we start in state s, s >=0, what is the mean time
> to reach state -1?
>
> I think that this is related to birth-death processes with killing...
>
> Thanks again!
>
> Best regards, Daniel
>
> On May 28, 5:20 am, William Elliot <ma...(a)rdrop.remove.com> wrote:
>
> > On Fri, 28 May 2010, sadoc wrote:
> > > Please, how can I solve the following recursion?
>
> > > x[ i + 1 ] = ( ( ( a + ( i + 1) m ) / a ) x[ i ] ) - ( ( i
> > > m / a ) x[ i - 1 ] ) - ( 1 / a )
>
> > Yicks. Is this what you wrote?
>
> > x[i + 1] = (((a + (i + 1)m)/a).x[i]) - ((im/a).x[i - 1]) - (1/a)
>
> > Besides needing to state a /= 0, it needs to be simplified.
>
> > a.x[i + 1] = (a + (i + 1)m).x[i] - im.x[i - 1] - 1
>
> > A random thought occurs;
> > a(x[i + 1] - x[i]) = (i + 1)m.x[i] - im.x[i - 1] - 1
>
> > a(x[i + 1] - x[i]) = im(x[i] - x[i - 1]) + m.x[i] - 1
>
> > Let's solve the case m = 0.
>
> > a(x[i + 1] - x[i]) = -1; x[i + 1] = x[i] - 1/a
>
> > For all i in N, x[i] = x[0] - i/a is the solution.
>
> > Regards the case m /= 0,
> > for all i in N, x[i] = x[0] = 1/m
> > is a solution.
>
> > Let's examine the case for all i, x[i + 1] - x[i] = t.
>
> > at = imt + m.x[i] - 1; m.x[i] = at - imt + 1
>
> > For all i,
> > x[i] = at/m + 1/m - it
> > isn't a solution if t /= 0, because
> > x[i + 1] - x[i] = -t,
> > contrary to the assumption
> > x[i + 1] - x[i] = t.
>
>

From: sadoc on 1 Jun 2010 00:32

Dear R.G.Vickson,

Thanks a lot for the answers. I found that the results in

@Article{bdcata,
title={On the first-visit-time problem for birth and death processes
with catastrophes},
author={A. Crescenzo and V. Giorno and A. Nobile and L. Ricciardi},
year={2008},
journal={arXiv}
}

are actually very useful to solve this problem! They yield closed
form expressions to the desired mean time to absorption.

Follows below more comments.

> > consider a Markov chain with the following generator matrix
>
> > q(i,i+1) = a (i>=0)
> > q(i,i-1) = im (i>=1)
> > q(i,-1) = m (i>=1) <------ do you really mean you cannot get directly from
>
> state 0 to state -1? I will assume
> so below.

Yes, we cannot go directly from 0 to -1.

>
> If this is really your problem, I think you have the wrong recursion.
> If we let x[i] = expected time to reach the absorbing state -1 from
> state i >= 0 then I get:
>
> x[0] = (1/a) + x[1]
> x[1] = 1/(a + 2m) + [m/(a + 2m)]*x[0] + [a/(a + 2m)]*x[2]
> x[2] = 1/(a + 3m) + [2m/(a + 3m)]*x[1] + [a/(a + 3m)]*x[3],
>
> and in general:
>
> x[i] = 1/(a + (i+1)m) + [im/(a + (i+1)a)]*x[i-1] + [a/(a+(i+1)m)]*x[i
> +1]

the equation above should be

x[i] = 1/(a + (i+1)m) + [im/(a + (i+1)m)]*x[i-1] + [a/(a+(i+1)m)]*x[i
+1]

Yes,

x[i] = 1/(a + (i+1)m) + [im/(a + (i+1)m)]*x[i-1] + [a/(a+(i+1)m)]*x[i
+1]

therefore,

[a/(a+(i+1)m)]*x[i+1] = x[i] - 1/(a + (i+1)m) - [im/(a + (i
+1)m)]*x[i-1]

x[i+1] = x[i]/[a/(a+(i+1)m)] - [(a+(i+1)m)/a]/(a + (i+1)m) -
- ([im/a]*x[i-1])

x[i+1] = x[i]/[a/(a+(i+1)m)] - 1/a - ([im/a]*x[i-1])

which is the recursion we originally started with

>
> Maple 9.5 can solve this, but the result is very complicated.

yes... thanks a lot!

Best regards, Daniel

>
> R.G. Vickson
>

From: sadoc on 9 Jun 2010 18:44

The solution to the problem is at

A note on birthdeath processes with catastrophes;
by A Di Crescenzo et al. - 2008 -

First | Prev |
Pages: 1 2
Prev: Godels seconded theorem ends in paradox-simple proof
Next: Is this function convex?