6

I have a set of equations of the form:

$$\begin{align*} x_1&=(ax_0+c) \bmod (m)\\ x_2&=(ax_1+c) \bmod (m)\\ x_3&=(ax_2+c) \bmod (m)\\ &\vdots\\ x_{n}&=(ax_{n-1}+c) \bmod (m) \end{align*}$$

I want to compute the sensitivity indices of each equation with respect to the parameters $a$, $c$, and $m$. That is, compute $\frac{dx_i}{da}$, $\frac{dx_i}{dc}$, and $\frac{dx_i}{dm}$ for each $i=1,\dots,n$. However, the $\bmod (m)$ is throwing me off... I don't think that we can take a derivative of such an equation... In which case, I don't know if there is any other way to compute the sensitivity index of these equations.

Jan
  • 3,418
  • 22
  • 37
Paul
  • 12,045
  • 7
  • 56
  • 129

3 Answers3

4

My explanation is getting long-winded here, but the answer is, attempting to use a continuous definition of sensitivity index is not going to be meaningful for your problem.

It is possible to find the sensitivity of a discontinuous function with respect to a parameter at a specific point of discontinuity, so if the problem could be posed with functions having domains over the reals, the problem would be well-posed; there exists mathematics to deal with these types of problems. (I'm having trouble tracking down a good source, since the canonical one appears to be E. N. Rozenvasser, "General sensitivity equations of discontinuous systems," Automat. Remote Control (1967), 400–404, and every other paper I've seen seems to cite this one.)

The problem is that moduli have integer-valued arguments, and you're trying to obtain the response to differential (i.e., very small) changes in parameters. It's impossible to meaningfully define what happens in the limit as your change in $m$ goes to zero, so this definition of sensitivity is not going to get you anywhere. I don't believe that switching to a discrete differential operator will remedy that problem in a meaningful way. However, you could search the literature and see if anything comes up; I found some work on sensitivity analysis of discrete stochastic dynamical systems that exists, but upon a quick read, I don't think it generalizes to your work readily. (Your mileage may vary.) If you want to do sensitivity analysis on this problem, there are probably approaches better-suited to your problem, such as sampling.

Geoff Oxberry
  • 30,394
  • 9
  • 64
  • 127
  • That's exactly what I was afraid of... The discreteness of the problem prohibits the use of standard sensitivity analysis. Do you happen to have any good references on sensitivity analysis by "sampling"? – Paul Apr 03 '12 at 20:20
  • 1
    I'll look for some, but the basic idea is simple: try many different values of your parameters. You could use design-of-experiments type of approaches to pick the parameter values, you could pick values ad hoc, or you could employ some other approach. Sampling happens to be the easiest, simplest, most robust approach, and it should give you some intuition for your problem. – Geoff Oxberry Apr 03 '12 at 20:51
2

The mod operation leads to a discontinuity in the function. That means of course that you can't take a derivative for values $x_i$ where $ax_i+c$ is a multiple of $m$. At all the other places, the mod-operation does nothing but shift its left operand so the derivative is as if the mod-operation wasn't there.

To see what exactly happens here, simply plot the $x_1$ as a function of $x_0$ for given $a,c$! It's a saw function.

Wolfgang Bangerth
  • 55,373
  • 59
  • 119
  • Since the parameters $a$, $c$, and $m$ must be integer valued, along with $x_{1}, \ldots, x_{n}$, defining even one-sided derivatives is impossible. – Geoff Oxberry Apr 03 '12 at 18:30
  • Perhaps a discrete differential operator would be the right thing to set up here? I agree this whole problem looks a bit ill-posed in a continuous setting. – Aron Ahmadia Apr 03 '12 at 18:45
  • Oh, I had tacitly assumed that all these numbers (with the possible exception of 'm') would be real numbers and that taking the mod 'm' would simply subtract the largest integer multiple of 'm' from the left hand side operator. Of course, if they're all integers, then nothing can be done since there's no limit you can take in defining the derivative! – Wolfgang Bangerth Apr 03 '12 at 20:27
  • @WolfgangBangerth: Thanks for your feedback. I think I will need an alternative formulation of my problem such sensitivity indicies are not needed. I'll write it up later on. – Paul Apr 11 '12 at 18:59
1

You will need to use a trick. In your example, the modulo function merely introduces periodicity on continuous statements. You didn't specify whether your variables were integers or not, and even so you may want to relax your problem to continuous variables. You can transform your function by using an exponential of your equation: $$ e^{\Im 2\pi x_i/m} = e^{\Im 2\pi(ax_{i-1}+c)/m} $$ Obviously, this equation is differentiable and periodic $\mbox{mod } m$. Now your derivatives are $$ \frac{dx_i}{da} e^{\Im 2\pi x_i/m} = \left(a\frac{dx_{i-1}}{da}+x_{i-1}\right)e^{\Im 2\pi(ax_{i-1}+c)/m}\\ \left(\frac{dx_i}{dm}-\frac{x_i}{m}\right) e^{\Im 2\pi x_i/m} = \left(a\frac{dx_{i-1}}{dm}-\frac{ax_{i-1}+c}{m}\right)e^{\Im 2\pi(ax_{i-1}+c)/m}\\ \frac{dx_i}{dc} e^{\Im 2\pi x_i/m} = \left(a\frac{dx_{i-1}}{dc}+1\right)e^{\Im 2\pi(ax_{i-1}+c)/m} $$

Deathbreath
  • 1,042
  • 7
  • 20
  • If you relax the problem to continuous variables, then you don't need the exponential transformation and can use standard methods. The discontinuities introduces by the modulo function is not the most troublesome issue with Paul's problem; rather, the most troublesome part is the interpretation of those sensitivities. How meaningful is it to perturb $m$ by a "small amount" if $m$ is discrete, unless $m$ is considerably (i.e., several orders of magnitude) larger than 1? – Geoff Oxberry Apr 04 '12 at 22:05
  • @GeoffOxberry: It doesn't make much sense to take derivatives with respect to integers. I assume his modulo function is the quotient space corresponding to the equivalence class $a\equiv b \iff a=b+nm$ for some integer $n$; but Paul may clarify. – Deathbreath Apr 05 '12 at 01:06
  • @GeoffOxberry: You're right... it doesn't make much sense in my case since the values are integer in nature. – Paul Apr 11 '12 at 18:57