MATLAB: Double indexed recurrence relation

double indexrecurrence relationsequence

I need to simulate the following (double indexed!) recurrence relation:
p[1,1]=1
for n=1,2,3,… and k=1,2,…,n+1
p[n+1,k] = p[n,k]*(1-v*k/n) + p[n,k-1]*v*(k-1)/n , with p[n,0]=p[n,n+1]=0
where v is just some constant in the interval (0,1)
For a fixed value of n, say n=20, I need to compute p[n,k] for k=1,2,…,n
Thanks, Dave

Best Answer

  • I may be missing something but I don't understand the difficulty. Just use two loops:
    maxn = 20;
    v = rand;
    p = zeros(maxn);
    p(1,1) = 1;
    for n = 1 : maxn-1
    for k = 1 : maxn
    p(n+1, k) = p(n, k)*(1-v*k/n);
    if k > 1 %to account for p(~, 0) which is not valid index in matlab
    p(n+1, k) = p(n+1, k) + p(n, k-1)*v*(k-1)/n;
    end
    end
    end
    The rows of p are the values of n, the columns the values of k.
    There may be a more efficient way of generating that matrix, without loops. I've not really looked into the details of your recurrence.