Recursion to compute convolution
显示 更早的评论
Hello,
consider the sum of i.i.d. random variables 
with 
:
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 个评论
Image Analyst
2020-11-15
If you want convolution, simply use the built-inconv() function. Don't do it manually - the hard way.
Alex Schmdit
2020-11-15
Image Analyst
2020-11-15
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.
Alex Schmdit
2020-11-15
编辑：Alex Schmdit
2020-11-15
I am not sure we are talking about the same thing. If I want to compute the probability of a random variable and know its distribution, I can easy compute it. The distribution of sum of random variable is computed using convolution. For example take 
. Therefore: 
. Therefore: The second factor would be 
. How do I use conv() here?
. How do I use conv() here?采纳的回答
Bruno Luong
2020-11-15
编辑：Bruno Luong
2020-11-15
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 个评论
Alex Schmdit
2020-11-15
Bruno Luong
2020-11-15
编辑：Bruno Luong
2020-11-15
Wrong in both.
You should get (I think)
>> Psum(7,10,2)
ans =
0.1250
Alex Schmdit
2020-11-15
Alex Schmdit
2020-11-15
Bruno Luong
2020-11-15
编辑：Bruno Luong
2020-11-15
XXX=P1(k)
You are now good!
Alex Schmdit
2020-11-15
Bruno Luong
2020-11-15
To make a P = P + ... in the for-loop returns the right sum at the end.
Alex Schmdit
2020-11-15
Bruno Luong
2020-11-15
编辑：Bruno Luong
2020-11-15
For n = 1, the code must return P(S1 = k) that is P(X = k). You don't sum on j (or you sum on single j=k if you insist)
Alex Schmdit
2020-11-15
Alex Schmdit
2020-11-15
Bruno Luong
2020-11-15
编辑：Bruno Luong
2020-11-15
Do you call with n<=0? or not integer?
Alex Schmdit
2020-11-15
Bruno Luong
2020-11-15
编辑：Bruno Luong
2020-11-15
function P = Psum(n, k, alpha)
if k < n
error('not valid parameter k');
end
P1 = @(j) 1/j^alpha - 1/(j+1)^alpha;
if n == 0
% just do it, I have no desire to explain it
P = double(k == 0);
else
P = 0;
for j=1:k-n+1
P = P + Psum(n-1, k-j, alpha)*P1(j);
end
end
end
Alex Schmdit
2020-11-15
Alex Schmdit
2020-11-15
Bruno Luong
2020-11-16
编辑：Bruno Luong
2020-11-16
I give here a non-recursive solution using CONV suggested by Paul
%
function P = Psum_nonrecurse(n, k, alpha)
% n scalar, k can be vector
if (n < 1) || any(k < n)
error('not valid parameter');
end
P1 = @(j) 1./j.^alpha - 1./(j+1).^alpha;
M = P1(1:max(k)-n+1);
P = M;
for i=1:n-1
P = conv(P, M);
end
P = P(k-n+1);
end
Alex Schmdit
2020-11-16
Bruno Luong
2020-11-16
编辑：Bruno Luong
2020-11-16
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.
Alex Schmdit
2020-11-17
更多回答（2 个）
Image Analyst
2020-11-15
If dist is your distribution, then the distribution of the sum would be
distSum = conv(dist, dist, 'full');
No recursion needed.
3 个评论
Alex Schmdit
2020-11-15
Image Analyst
2020-11-15
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
2020-11-15
Looks like you've accepted Bruno's answer, so I guess you got it all solved now.
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 个评论
类别
在 帮助中心 和 File Exchange 中查找有关 F Distribution 的更多信息
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!
Translated by 
