HELP NEEDED on a stochastic question! THANKS!

We define the concept "asymptotic equivalence" as follows: we say that two sequences A1, A2,...and B1, B2,.... are asymptotically equivalent and write

An~Bn , if lim(An/Bn) = 1 when n->infinity


Consider a sequence of real numbers A1, A2,... that satises the following recursive equation:

A(n)/n = (c/n^2) + (A(n-1) / n-1) for n>=2

If A1=c, what's the sequence that is "asymptotic equivalence" to A(n) when n->infinity?

ANY HELP WILL BE APPRECIATED =D thank you so much cos i really have no idea on how to go about solving this question!

Quote: shirobia

We define the concept "asymptotic equivalence" as follows: we say that two sequences A1, A2,...and B1, B2,.... are asymptotically equivalent and write

An~Bn , if lim(An/Bn) = 1 when n->infinity


Consider a sequence of real numbers A1, A2,... that satises the following recursive equation:

A(n)/n = (c/n^2) + (A(n-1) / n-1) for n>=2

If A1=c, what's the sequence that is "asymptotic equivalence" to A(n) when n->infinity?

ANY HELP WILL BE APPRECIATED =D thank you so much cos i really have no idea on how to go about solving this question!

I think your equation is approaching a linear function in the variable n implying that B(n)=c + 1.6449339867095*c*(n-1) .

Hi there, thanks for replying. Actually this is a MCQ question with these choices below,

a) An~ n
b) An~ 2n
c) An~ c*n
d) An~ c*n/(pi)
e) An~ (pi)^2c*n/6
f) An~ c^2*n
g) An~ c*((pi)^2)/6
h) An~ c*n/(3)

I tried expressing An in terms of A1 and i have (1/6) appearing in the A1 term. But i'm not sure if this approach is correct.

The function is bounded above by both B(n) = B(n-1) + c*pi^2/6, and C(n) = n*c*pi^2/6.

where pi^2/6 = 1.644934...

I suppose A(n) is asymptotically equivalent to both. Pick one, they both work, although B is a recursive sequence which is probably the answer they are looking for. The first one is tighter. As for the derivation, my calculus is really rusty. I'm much better at analyzing limits than at proving they exist.

EDIT: i pick (e). lucky you, no derivation required?

yup no derivation is required, but i still do not understand why is there a pi^2 appearing?
Anw thanks a lot!

Quote: shirobia

Hi there, thanks for replying. Actually this is a MCQ question with these choices below,

a) An~ n
b) An~ 2n
c) An~ c*n
d) An~ c*n/(pi)
e) An~ (pi)^2c*n/6
f) An~ c^2*n
g) An~ c*((pi)^2)/6
h) An~ c*n/(3)

I tried expressing An in terms of A1 and i have (1/6) appearing in the A1 term. But i'm not sure if this approach is correct.

You can rule out a) and b) since they don't have any dependence on c
You can rule out g) since A(n) does not approach a constant but keep increasing
You can rule out f) since B(n) is not a linear function of c


c) An~ 1:c*n
d) An~ 1/(pi)*c*n
e) An~ (pi)^2/6*c*n
h) An~ 1/3*c*n

The slope of the line that I defined above is
c) 1
d) 0.318309886
e) 1.644934067
f) 0.333333333

So I would go with answer (e)

Let's look at this not-so-elegant approach:

a(1) = c

a(2) = c/2 + 2/1*c
a(2) = c/2 + 2c

a(3) = c/3 + 3/2*(c/2+2c)
a(3) = c/3 + 3/4*c + 3c

a(4) = c/4 + 4/3*(c/3 + 3/4*c + 3c)
a(4) = c/4 + 4/9*c + c + 4c

a(5) = c/5 + 5/4*(c/4 + 4/9*c + c + 4c)
a(5) = c/5 + 5/16*c + 5/9*c + 5/4*c + 5c

a(6) = c/6 + 6/5*( c/5 + 5/16*c + 5/9*c + 5/4*c + 5c)
a(6) = c/6 + 6/25*c + 6/16*c + 6/9*c + 6/4*c + 6c

a(7) = c/7 + 7/6*(c/6 + 6/25*c + 6/16*c + 6/9*c + 6/4*c + 6c)
a(7) = c/7 + 7/36*c + 7/25*c + 7/16*c + 7/9*c + 7/4*c + 7c

factoring out a 7c, we get:
a(7) = 7*c*(1/49 + 1/36 + 1/25 + 1/16 + 1/9 + 1/4 + 1/1)
Clearly, we have a pattern.

So, we can say that a(n) = n*c*(1/1^2 + 1/2^2 + 1/3^2 + 1/4^2 + 1/5^2 + 1/6^2 + 1/7^2 + ... + 1/n^2)

Knowing what this represents is more of a challenge:

Basel_problem on Wikipedia

Quote: CrystalMath

Clearly, we have a pattern.

So, we can say that a(n) = n*c*(1/1^2 + 1/2^2 + 1/3^2 + 1/4^2 + 1/5^2 + 1/6^2 + 1/7^2 + ... + 1/n^2)

Here is a slightly more elegant approach:

Let B(n) = A(n) / n
Substituting in the original sequence specification:
B(1) = c
B(n) = c / n^2 + B(n-1) for all n >= 2

Proof that B(n) = c * (1 + 1/4 + 1/9 + ... + 1/n^2) by induction:
B(1) = c * 1, so it is true for 1
Assume B(n) = c * (1 + 1/4 + 1/9 + ... + 1/n^2)
B(n+1) = c / (n+1)^2 + c * (1 + 1/4 + 1/9 + ... + 1/n^2) = c * (1 + 1/4 + 1/9 + ... + 1/n^2 + 1/(n+1)^2)
Thus, if it is true for n, it is true for n+1 - therefore, since it is true for 1, it is true for all integers > 1

Substitute A(n) / n = B(n):
A(n) / n = c * (1 + 1/4 + 1/9 + ... + 1/n^2)
A(n) = n * c * (1 + 1/4 + 1/9 + ... + 1/n^2)

Anybody who is wondering where pi^2 comes into this should note that 1 + 1/4 + 1/9 + 1/16 + ... approaches pi^2 / 6 as n approaches positive infinity.

Quote: CrystalMath

So, we can say that a(n) = n*c*(1/1^2 + 1/2^2 + 1/3^2 + 1/4^2 + 1/5^2 + 1/6^2 + 1/7^2 + ... + 1/n^2)
Knowing what this represents is more of a challenge:
Basel_problem on Wikipedia

Very nice. I knew it was proportional to nc, but I don't think I would have picked up the closed form of the constant.

That's a tough problem, was it an extra credit? Of course, given the multiple choice you could just plug in numbers and see which is the correct answer.

I must observe that this question is not really about a Stochastic process so I must assume that it is a warm up question early in the class. We can also assume that the OP will be posing very difficult questions in the future.

Quote: pacomartin

I must observe that this question is not really about a Stochastic process so I must assume that it is a warm up question early in the class. We can also assume that the OP will be posing very difficult questions in the future.

Well, the thread title referred to a "stochastic question", not necessarily a stochastic process. Maybe the OP means that the question itself will be randomly changing(?). I often felt that some profs changed the test questions after I had tried to answer them, so maybe that's what was going on. :-)

Quote: pacomartin

Quote: CrystalMath

So, we can say that a(n) = n*c*(1/1^2 + 1/2^2 + 1/3^2 + 1/4^2 + 1/5^2 + 1/6^2 + 1/7^2 + ... + 1/n^2)
Knowing what this represents is more of a challenge:
Basel_problem on Wikipedia

Very nice. I knew it was proportional to nc, but I don't think I would have picked up the closed form of the constant.

That's a tough problem, was it an extra credit? Of course, given the multiple choice you could just plug in numbers and see which is the correct answer.

I must observe that this question is not really about a Stochastic process so I must assume that it is a warm up question early in the class. We can also assume that the OP will be posing very difficult questions in the future.

Yup you are right. This is only the first assignment and we will be touching on Markov chain in the next few lectures. I can foresee that I'll be asking for more help in the near future! The pattern was really tough to observe but the explanation was really good!

Thanks for all the helps given. they were really useful =)

Quote: shirobia

Yup you are right. This is only the first assignment and we will be touching on Markov chain in the next few lectures. I can foresee that I'll be asking for more help in the near future! The pattern was really tough to observe but the explanation was really good!

Thanks for all the helps given. they were really useful =)

I thought it was at the beginning of an advanced class in mathematics. The equation is fairly complex, but the actual relationship is linear. The coefficient was very difficult. This is not a "pattern" that most people would be expected to see. If it stumped the Bernoullis, then you should not be surprised that it is difficult. In reality it is a series that people learn about and recognize.

But it is really a question about recursively defined functions, which is a prelude to Markov chains and then onto stochastics.


There are a number of threads in this forum that talk about Markov chains. One of the better known was in response to the Time Magazine article:


Holy Craps! How a Gambling Grandma Broke the Record
It sounds like a homework problem out of a high school math book: What is the probability of rolling a pair of dice 154 times continuously at a craps table, without throwing a seven? The answer is roughly 1 in 1.56 trillion, and on May 23, Patricia Demauro, a New Jersey grandmother, beat those odds at Atlantic City's Borgata Hotel Casino and Spa. Demauro's 154-roll lucky streak, which lasted four hours and 18 minutes, broke the world records for the longest craps roll and the most successive dice rolls without "sevening out."

The answer of 1 in 1.56 trillion is incorrect and is actually much too large. The writer either did the calculation herself, or she relied on a poor mathematician. This response is the answer to the probability of rolling a dice 154 times without getting a 7. In craps you can get a 7, as long as it is on a "come out" roll. The solution can be posed as a Markov chain, and is essentially a stochastic process.