0
$\begingroup$

How one can solve the following recurrence: \begin{align} X[i,0] &=0 \quad \forall i =1,\ldots, m\\ X[m,n] &= a_n X[m,n-1]+b_n \sum_{i=k_m}^{m-1}X[i,i] +c_n \end{align}

Where $a_i\ge 1 ,~ 0 \le c_i , b_i <1, k_i \ge 1$ are constants for all $i = 1,\ldots, n$.

Improve this question
$\endgroup$
3
  • $\begingroup$ The expression after the dots is surely mistyped. I edited it, but maybe i misunderstood your intentions. $\endgroup$
    – Daniel Soltész
    Commented Nov 10, 2013 at 1:49
  • 3
    $\begingroup$ Where did this arise? $\endgroup$
    – Gerry Myerson
    Commented Nov 10, 2013 at 4:41
  • $\begingroup$ It arises in a problem called "online dynamic TCP acknowledgement". There is an algorithm proposed by Buchbinder that uses a special case of this update rule. Namely, $a_i = a_k, b_i = b_k$ and $c_i=c_k$ for all $i \neq k$. This is a generalization for the weighted dynamic TCP ack problem, where each packet has a weight that can define the delay penalty. $\endgroup$
    – Majid Khonji
    Commented Nov 10, 2013 at 13:52

1 Answer 1

Reset to default
1
$\begingroup$

I assume that $n$ is a nonnegative integer although this should be clearly stated in the question. Even in simplest cases this recurrence is indeterminate, because it does not say anying about the terms $X[m,n]$, $m-n\neq 0,1$.

Suppose that $a_n=1$, $k_n=n-1$, $c_n=0$. The recurrence then reads

$$X[n,n]-X[n-1,n-1]=X[n,n-1]. $$

This implies

$$ X[n,n]= X[0,0]+ X[1,0]+X[2,1]+\cdots + X[n,n-1]. $$

The terms $X[m,n]$, $m-n\neq 0$ can be chosen arbitrarily. I believe there is some typo in the recurrence relation.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you for the clarification. I'll try to fix it now. $\endgroup$
    – Majid Khonji
    Commented Nov 10, 2013 at 15:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .