Recursion to compute convolution
15 views (last 30 days)
Show older comments
Hello,
consider the sum of i.i.d. random variables with :
Is it possible to implement this recursively?
If it is, can anybody tell me how I can do that or give at least a hint?
4 Comments
Image Analyst
on 15 Nov 2020
I don't know what that formula is, especially the index for P which is S(n-1)==(k - j), but I'm just going by what you say - that you want convolution. There is a built in function for that, that takes several arguments. First one is the main signal. Second argument is the filter weights of the scanning/sliding filter window. Third argument is whether you want the full convolution, only the valid elements, or an output that is the same size as the input signal. Look up the documentation and online tutorials about what convolution is. Find one that has diagrams that show the window as it slides along -- I'm sure there are lots of convolution tutorials out there.
Accepted Answer
Bruno Luong
on 15 Nov 2020
Edited: Bruno Luong
on 15 Nov 2020
Here is a hint, you must replace XXX and YYY with something (after all it's your homework)
function P = Psum(n, k, alpha)
if k < n
error('not valid parameter');
end
P1 = @(j) 1/j^alpha - 1/(j+1)^alpha;
if n == 1
P = XXX;
else
P = 0;
for j=1:k-n+1
P = P + YYY *P1(j);
end
end
end
20 Comments
Bruno Luong
on 16 Nov 2020
Edited: Bruno Luong
on 16 Nov 2020
When you have two independent integer-discrete random variables X and Y, with repectively PDF A and B, the pdf of random variable X+Y is the convolution of A and B:
conv(A,B)
With that in mind, the for-loop computes then sequentially the pdf of
S(i+1) = S(i) + X(i+1).
If you only need to calculate P(S(n)=k) for a scalar k, this methods computes a lot of things and throw away a big part, as oppose to the recursive method. However if you need for a bunch of k, use CONV is a better approach. This function can be called with a vector k (but same n), not the recursive method that can only deal with scalar k.
More Answers (2)
Image Analyst
on 15 Nov 2020
If dist is your distribution, then the distribution of the sum would be
distSum = conv(dist, dist, 'full');
No recursion needed.
3 Comments
Image Analyst
on 15 Nov 2020
That is your probability distribution function for your random variable. Just one, not the distribution of the sum of the two but just one alone. For example for a uniform distribution it would be all ones, like
n = 500; % Whatever.
dist = ones(n, 1) / n;
subplot(2, 1, 1);
plot(dist, 'b-', 'LineWidth', 2);
title('PDF (Histogram) of One Variable', 'FontSize', 15);
ylim([0, 0.0025]);
grid on;
distSum = conv(dist, dist, 'full');
subplot(2, 1, 2);
plot(distSum, 'b-', 'LineWidth', 2);
grid on;
title('PDF (Histogram) of Sum of Two Variables', 'FontSize', 15);
where n is the resolution you want to digitize your continuous PDF at.
Image Analyst
on 15 Nov 2020
Looks like you've accepted Bruno's answer, so I guess you got it all solved now.
Paul
on 15 Nov 2020
Edited: Paul
on 15 Nov 2020
Let the vector M be the distribution of integer valued X. For example, if X takes on values 1-6 uniformly, then
M = ones(1,6)/6;
Now you can compute the distribution of the sum of the random sample of X as:
Mn = M;
for ii = 2:n
Mn = conv(Mn,M);
end
This isn't recursive, so I'm not sure if that's the implementation you want. Also, it may not be efficient depending on the values of numel(M) and n because Mn is growing each time through the loop. But I think it gives you the result you seek. You'll have to be careful the indexing of Mn if X can take on values less than 1.
1 Comment
See Also
Categories
Find more on Creating and Concatenating Matrices in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!