I am working on a recursive formula associated with discrete mathematics which seems very difficult to compute. The formula is as follows

$F_{i,j}(m)=\sum_{t=j}^{m}\left [ x_{ij}.\sum_{k=1}^{m}\sum_{l=j-1}^{m} F_{k,l}(m-ij) \right ]$

It's given that $F_{i,j}(m)=0$ for $m<0$.

Here $x_{ij}$ is defined as a random number with the property that $0<x_{ij}<j$.

How do I write a recursive algorithm to compute $F_{i,j}(m)$?

  • 2
    $\begingroup$ Ironic, given your username, but could you be more precise? The $x_{ij}$ have what distribution? Are they resampled every time the sum is evaluated or are they fixed? Is the naive implementation too slow? Did you try dynamic programming? $\endgroup$ – David Richerby Mar 27 '15 at 20:48
  • $\begingroup$ $x_{ij}$ is uniformly distributed random number and it is re-sampled every time the sum is evaluated. I am trying to build a recursive algorithm for it so that for a given i,j and m, the function fun(i,j,m) can compute $F_{i,j}(m)$. $\endgroup$ – precision Mar 27 '15 at 21:01
  • $\begingroup$ What is provided as inputs? Are the $x_{ij}$'s provided as part of the input, along with $i,j,m$? $\endgroup$ – D.W. Mar 27 '15 at 21:19
  • $\begingroup$ Inputs are $i,j ,m$. Every time I have to compute $x_{ij}$ for each k,l and m. $\endgroup$ – precision Mar 27 '15 at 21:27
  • $\begingroup$ OK. So $F_{i,j}(m)$ is not a number; it is a random variable. So it's not clear what you want. Do you want to sample a single value from $F_{i,j}(m)$? Do you want to compute the distribution of $F_{i,j}(m)$? If the latter, we'll need to know what the base cases are (so we can evaluate how large $F_{i,j}(m)$ might get, as a function of $i,j,m$ and the $x$'s). $\endgroup$ – D.W. Mar 28 '15 at 4:28

Assuming we are given the $x_{ij}$'s and $i,j,m$, your formula already is a recursive algorithm to compute $F_{i,j}(m)$. If you use dynamic programming (memoization) to avoid re-computing $F_{i',j'}(m')$ more than once for any given tuple $(i',j',m')$, the running time will be $O(m^3)$, since you only evaluate $F_{i',j'}(m')$ for tuples $(i',j',m')$ where $0 \le i',j',m' \le m$.

If the $x_{ij}$'s are not given, your question is not well-defined. If that's what you meant, it's possible you might be asking for us to compute the distribution of $F_{i,j}(m)$, but if so, the question needs to be edited accordingly.

Either way, I suspect that there must be some additional base cases you have not provided. As it currently stands, the solution $F_{i,j}(m)=0$ for all $i,j,m$ satisfies your equation. I suggest you edit your question to specify the missing base cases.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.