I have a mathematical function of two variables that I’m studying. At present, I have this function as a recursion relation: I know the values for certain low values of the independent variables, and I can relate the value of the function for high inputs to its value for lower inputs. This is enough to always evaluate the function, but I could do much more if I could express it directly. Is there any general method for constructing such a representation from the recursion relations?
If it matters, the relations I have are:
a, b nonnegative integers; P(a,b) rational
If a < b, P(a,b) = 0
If b = 0, P(a,b) = 1
If b = 1, P(a,b) = a/(a+1) P(a-2,1) + 1/(a+1)
Otherwise, P(a,b) = a/(a+b) P(a-2,b) + b/(a+b) P(a-1,b-1)
(a virtual cookie to anyone who recognizes what problem this is from)
Ah, yes, I suppose that does fall afoul of my statement that a is nonnegative. To be clear, I only care about the values of P for both positive, but P(-1,1) = 0, since a < b. In other words, P(1,1) = 1/2.
EDIT: I’d really prefer a general method for such problems, anyway, rather than focusing on the specific problem I have before me right now. I was waffling about whether to include the actual problem, and only did so to forestall questions.
I don’t think there’s a general algorithm for doing it, but tricks I tend to use when I have to do it is abusing things like ceilings, floors, and mods.
For instance, a<b => P(a,b)= 0 is the same assertion as floor(a/b)=0. That might not end up being useful, but those functions are usually where I start.
ETA: I mean the assertion is the same for your domain (excluding the negative case).
Actually, now I remember, there is an algorithm for this. It’s been so long I’d forgotten. It’s mostly used for analyzing what the big O of a recursive algorithm is, but it works for this too.
The general idea is plugging in and pattern matching. The minus is that for something like this with so many catches it’ll give you a nasty piecewise function. It does take a bit of creativity sometimes.
Let’s take the case when b=1
What’s
a/(a+1)P(a-2,1)+1/(a+1)?
Well, that’s just
a/(a+1)((a-2)/(a-1)P(a-4,1)+1/(a-1))+1/(a+1)
Essentially, just keep plugging in P(a-2n,1) until you get the point of what the pattern is. Do this for two or three iterations, until you’re sure of the pattern, and then put in a big ol’ […] P(0,1).
In this case, I think you’re going to have to split the b=1 case into b=1 and a%2=0 and b=1 and a%2=1, but the functions should come out almost the same, it’s just the terminating case that’s different.
Then it’s just a matter of condensing the function with summations, Big Pis, etc.
I can tell already that the a>=b>1 case is going to get REALLY gnarly, I’ve never had to do this with two recursive variables, good luck.
The methods out there are for single variable recurrences. I don’t know of any general tricks for multivariate ones. You might be able to do something with generating functions, but there’s no guarantee that you’ll get anything nice.
The main problem in this scenario is the P(a-2,b) in the “otherwise” function. If it was just P(a-1,b-1) it would be easy since it clearly will eventually hit the b=1 case. But yeah, in general the multivariate is going to range from hard to impossible.
Hm, that’s unfortunate. But it’s good to know; that probably means I shouldn’t waste too much time trying to find a closed-form solution, and just make do with what I have.
I noticed a while ago that it makes a big difference whether a+b is even or odd: The values of P are significantly higher for even a+b than for neighboring odd points.
FWIW, in the case where a is even and b=1, the recurrence relation reduces to this equation (it works for the a=6 test case, I can’t assure you it always works, though, it was pretty quick and dirty):
And here’s the whole equation, for evens and odds. Turns out all that happens is you need to ceil a/2 (catch case is a=1, when k goes from 1 to 0, just assume the sum goes away).
Mafia. P(a, b) is the probability that the non-Mafia players win if they kill people at uniform random each turn, starting from a non-Mafia players and b Mafia players.
Wow, either I was way off or there are correct solutions for the P(a,1) case that look incredibly different. I think it might be the latter since mine seems to give the right answer when I test it, but I could have easily messed up somewhere.
ETA: Oh, I think I just got a really wordy alternate form of (a-1)!!/a!!
Huh, I was completely unaware of the existence of this paper. Thanks!
As it happens, my plan is to eventually incorporate more complicated roles, so that doesn’t supercede my work, but it should certainly be useful for understanding the simple case.