Recursive probability?

[Mewlove]

Hi all,

Would like to know what method, or distribution to use when solving a problem like this:

I start from level 0. There is a probability p chance to drop to level -1 and a (1-p) chance to increase to level 1.
The levels range from level -n to level n. When it reaches level -n or level n, it resets back to 0 on the same cycle.
How do I calculate the percentage of landing on each level (not counting the reset), assuming I continue running this infinitely? Is there any theorem or formula I can use?

Thanks!

 

[Cubist]

I've found a way of getting exact answers to this (not just a numerical solution).

Are you still interested in this question? Have you made any progress yourself? Also I'd be very interested to know what the origin of this question is.

I can give a hint to get you started if you're still stuck. FYI I might not log in very frequently over the next few days, so please be patient.

 

[Mewlove]

Hi! Yes, I am still interested in this question!
Currently am reading up on Markov's chain and about how it can be used with this problem (or not).

There probably isnt an origin to this question. I was thinking of a very simple game battle system similar to a tug of war, where it could go either sides at any point of time, but one side wins if they reach the end (resets back to 0). Running the code for a specific win-lose probability p, seem to always give me the same percentage hit for each level. So I was curious if I could actually calculate this exactly. It's probably more of a "I feel like I need to figure this out" kind of thing...

 

[Cubist]

You have come up with a very interesting problem!

It sounds like you've written some code to examine the probabilities numerically. I did a similar thing with a spreadsheet...



I noticed that the results eventually seem to settle down to a steady value many columns to the right. It takes longer to settle down as p approaches to 0 or 1. ( In fact it never settles down at the extremes of p=0 or 1, because in this scenario you are always certain to be at one known level ! )

At this point I made the assumption that it will always settle down if 0<p<1 and if "t" is sufficiently large. (I have a good idea about how to prove this, but have not done this step myself)


I then wrote some code that would output a set of equations for "n" levels...

- "2*n+1" equations that state the probability of being at level "x" at time "t" is equal to the probability of being at level "x" at time "t+1". In other words, the probabilities have settled down.

- Also one equation that says the sum of the probabilities is 1.

I then fed these equations into a computer algebra system called "maxima", and it was able to solve them as simultaneous equations to find the probabilities in terms of "p". This might seem like cheating but it cut out a lot of work! Obviously the code generates variable names that maxima will accept. Here are the equations for n=4...

algsys( [
  x_0=(1-p)*x_1,
  x_1=p*x_0+(1-p)*x_2,
  x_2=p*x_1+(1-p)*x_3,
  x_3=p*x_2+(1-p)*x_4,
  x_4=p*x_3+(1-p)*x_5+(1-p)*x_0 + p*x_8,
  x_5=p*x_4+(1-p)*x_6,
  x_6=p*x_5+(1-p)*x_7,
  x_7=p*x_6+(1-p)*x_8,
  x_8=p*x_7,
  x_0+x_1+x_2+x_3+x_4+x_5+x_6+x_7+x_8=1 ] ,
  [ x_0,x_1,x_2,x_3,x_4,x_5,x_6,x_7,x_8 ]);

The solutions are of the form x_n=(polynomial in p) / (poly in p). But the solution for level 0 is a set fraction.

I then looked at the solutions generated for n=1 to 9, and was able to spot a nice pattern.

I'll leave you to think about this for a while, you might want to replicate these steps yourself? If not then I can save you some work and post a summary of the first thing that I spotted about the results (which was not the final solution)