Message Boards Message Boards

GROUPS:

An issue with DiscreteConvolve ?

Posted 10 months ago
1266 Views
|
11 Replies
|
2 Total Likes
|

Hi,

I think, I found a bug in DiscreteConvolve[] implementation. See this code:

F[x_] :=  UnitStep[x] * UnitStep[10 - x] * 1/10
G[x_] := DiscreteConvolve[F[n],F[n], n, x]
M[x_] := DiscreteConvolve[G[n],F[n], n, x]
DiscretePlot[{F[x], G[x], M[x]}, {x, 0, 30}]

Both F[x] and G[x] are 0 outside of very small range. As I understand this should mean that their convolution (F * G)[x] should be 0 with exception of small range. But Wolfram thinks differently (see attached screenshot)

Story: trying to calculate probability mass function (PMF) of sum of three independent variables (lets say total value of three dices). Using DiscreteConvolve[DiscreteConvolve[P1[x], P1[x]], P1[x]] produced results that doesn't make any sense. In fact, changing first UnitStep[x] to UnitStep[x-1] makes M zero everywhere.

Did I miss something here?

Regards, Michael.

Attachment

Attachments:
11 Replies

Hi First, your code is highly inefficient, since you do not really compute the discrete convolution until you call the graphics, and then for each value of the horizontal axis you repeat the convolutions. This happens since you used := (SetDelayed) in place of = (a simple Set). So,

F[x_] = UnitStep[x]*UnitStep[10 - x]*1/10;
DiscretePlot[F[n], {n, -5, 15}]
G[x_] = DiscreteConvolve[F[n], F[n], n, x];
DiscretePlot[G[n], {n, -5, 22}, PlotRange -> All]
M[x_] = DiscreteConvolve[G[n], F[n], n, x];
DiscretePlot[{F[x], G[x], M[x]}, {x, 0, 30}]

F is defined for a support range between 0 and 10 therefore G has a support range of 20. Changing the support range to 1 (in place of 0) shows the expected results HTH yehuda

Posted 10 months ago

It is rather obvious that I am new to Wolfram language and am struggling with it. Efficiency issues aside -- can you explain why this produces wrong result for M[x]:

F[x_] :=  UnitStep[x-1]*UnitStep[6 - x]*1/6;
G[x_] :=  DiscreteConvolve[F[n], F[n], n, x];
M[x_] :=  DiscreteConvolve[G[n], F[n], n, x];
DiscretePlot[{F[x], G[x], M[x]}, {x, 0, 20}]

... and this:

F[x_] = UnitStep[x-1]*UnitStep[6 - x]*1/6;
G[x_] = DiscreteConvolve[F[n], F[n], n, x];
M[x_] = DiscreteConvolve[G[n], F[n], n, x];
DiscretePlot[{F[x], G[x], M[x]}, {x, 0, 20}]

is fine?

Also, I'd also appreciate any advice on improving performance of second snippet.

Thank you for help.

Well, The problem is two-fold First, the "SetDelayed" for defining G is inefficient, but this is not that important Second, the definition for G, using "SetDelayed" generates the wrong results (but MMA does exactly what you have instructed it to do). Considere the second option. Practically, DiscretePlot is a loop, running the x values from 0 to some value in steps of 1. For each such value (say x=1) you get (here x equals 1)

DiscreteConvolve[G[n],F[n]],n,1]

And then G[n] and F[n] need to be calculated, running a DiscreteConvolve for G[n] (here is the problem, look at the definition of G) inside the DiscreteConvolve you setup for M Just try

Table[  DiscreteConvolve[G[n],F[n]],n,i],{i,0,5}]

and try to figure out what happens If you use Set (= rather than := ) the result of the DiscreteConvolve returns a "function" (well, this is a Piecewise expression) and this function is used for the definition of M

This is one of the cases where the SetDelayed should be considered carefully

yehuda

In your definition of M[x_] you call G[n], which translates to

DiscreteConvolve[F[n], F[n], n, n]

which is trouble, because the summation index is the same as the parameter. Look at the difference between G[m] and

G[n] // PiecewiseExpand

The problem goes away with immediate definition = instead of your delayed definition :=

Unfortunately DiscretePlot does no check on the variables it is fed.

See what happens if you use a different variable, for instance k, instead of n in the definition of M, leaving everything else the same:

Clear[F, G, M];
F[x_] := UnitStep[x]*UnitStep[10 - x]*1/10
G[x_] := DiscreteConvolve[F[n], F[n], n, x]
M[x_] := DiscreteConvolve[G[k], F[k], k, x]
DiscretePlot[{F[x], G[x], M[x]}, {x, 0, 30}]
Posted 10 months ago

Yes, I noticed that... This incident actually confused me a lot. All material in Introductory book suggests using SetDelayed for creating my own functions. But my experience shows that it is quite dangerous. Should I always use "Set" instead?

A bit of rant -- I still remember some math from my University days, I am an expert C++ developer (more than 20 years of experience), know Haskell a bit and bunch of other languages. I spent about a week playing with Wolfram Laboratory and digging in Wolfram help. I find it very confusing. Understanding of it's programming model keeps eluding me -- most of code I write ends up producing errors, times out or gives results totally different from my expectations.

Is there any introductions for developers that skips all water and goes straight to programming model of "interpreter" that runs on Shift-Enter?

Posted 10 months ago

There is this book: Fast Introduction for Programmers:

http://www.wolfram.com/language/fast-introduction-for-programmers/en

but I am not sure if this is what you want.

Posted 10 months ago

(After checking first few pages) I think this is exactly what I need. Thank you very much!

Welcome to Wolfram Community! Please make sure you know the rules: https://wolfr.am/READ-1ST

Please do not put word BUG in titles. Such things need confirmation.

Posted 10 months ago

Thank you, everyone. I did not realize that DelayedSet gets literally substituted (like a define in C). Back to reading about basics...

My bad about those rules: this UI is quite different from what I got used to (on typical forum) and confused me quite a bit -- I don't remember running across them.

Michael,

SetDelayed is still most often used for "function"-like definitions. The advantage of SetDelayed is that it delays evaluation of the right side until the arguments are presented (at evaluation time). This is useful in most cases because it fits the "usual" model of define the function and, like a C program, substitutes those arguments at "run time".

You got burned not because you used SetDelayed, but as Gianluca pointed out, you used the variable n twice -- for two different things. This is equivalent in C to using a Macro for the inner definition -- the macro is blindly substituted and if its variable conflicts with the function you will have a bug. In C if n were a global variable and you used variable n in both an inner function and some outer function when you expected it to be local you would also have had a bug.

Your problem arose because the variable n does NOT appear in the pattern -- it is embedded in the right hand side. If n were part of the pattern it would behaved more like a C function and less like a C macro.

As Yehuda pointed out, the most important place that you really have to reconsider delayed vs immediate evaluation is for efficiency (especially for plotting complicated things). It makes no sense to recompute entire expressions over and over again so the times that I think about evaluation order/delay is in situations of repetitive computations.

As a workflow, I usually start with SetDelayed definitions as they are most "C" like in that I can later feed them arguments.

I hope this helps.

Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract