0
$\begingroup$

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

Improve this question
$\endgroup$
6
  • 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, 2015 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, 2015 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, 2015 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, 2015 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, 2015 at 4:28

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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