Prev: Godels seconded theorem ends in paradox-simple proof
Next: Is this function convex?
From: sadoc on 28 May 2010 03:04
Dear All,

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 )

Thanks!

Best regards, Daniel
From: Robert Israel on 28 May 2010 04:04
sadoc <danielsadoc(a)gmail.com> writes:


> 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 )
>

Using the rsolve command in Maple 14, I get the following:

x(i) =
(1/a*m)^i*GAMMA(i+1)*(-1/a*(1-exp(a/m)*(1-a/m))+1/m*i/((1/a*m)^i)/GAMMA(i+2)*hypergeom([1,
i+1],[i, i+2],a/m))
+ x(0) * (1/a*m)^i*(GAMMA(i+1)*a+GAMMA(i+1)*m-exp(a/m)*GAMMA(i+1,a/m)*m)/a
- x(1) * (1/a*m)^i*(GAMMA(i+1)-exp(a/m)*GAMMA(i+1,a/m))

I don't know if this can be simplified further.
--
Robert Israel israel(a)math.MyUniversitysInitials.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada
From: William Elliot on 28 May 2010 05:20
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 28 May 2010 11:20
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)

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 28 May 2010 13:14
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.
>
>

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