# Thread: Generating function of aX + m

1. ## Generating function of aX + m

Hello, everyone.

I'm having some doubts with the following problem:

Let X denote the execution time of a job rounded to the nearest second. The charges are based on a linear function Y = mX + n of the execution time for suitably chosen nonnegative integers m and n. Given the PGF (probability generating function) of X, find the PGF and pmf of Y.

I will write (shorty) what I have tried. If someone could confirm my solution or give me some hint I would appreciate that.

I started with
$\displaystyle G_Y(z) = \sum_{i=0}^{\infty} P(Y=i)z^i = \sum_{i=0}^{\infty} P(mX + n=i)z^i$

Hence we have that $\displaystyle X = \frac{i-n}{m}$. By the euclidian algorithm exist k and r<m such that $\displaystyle i-n = km + r$ and since the time is rounded to the nearest second I considered $\displaystyle \frac{i-n}{m} = k$ for $\displaystyle km - \left \lfloor \frac m2 \right \rfloor \leq i - n \leq km + \left\lfloor \frac m2 \right\rfloor - 1$

With this I got $\displaystyle G_Y(z) = \sum_{k=0}^{\infty} \left [P(X=k) \sum_{i=km - \left \lfloor \frac m2 \right \rfloor + n}^{km + \left\lfloor \frac m2 \right\rfloor +n - 1} z^i \right ]$
And then using the sum of the geometric progression and rearranging the terms I got $\displaystyle G_Y(z) = z^n \frac{z^{\left\lfloor \frac m2 \right\rfloor} - z^{-\left\lfloor \frac m2 \right\rfloor}}{z-1}G_X(z^m)$

p.s. sorry for my English.

2. Hello,

Well, maybe what you did is correct, but here's a better way...
$\displaystyle G_Y(z)=E[z^Y]=E[z^{mX+n}]=z^n E[(z^m)^X]=z^n \cdot G_X(z^m)$

3. Originally Posted by Moo
Hello,

Well, maybe what you did is correct, but here's a better way...
$\displaystyle G_Y(z)=E[z^Y]=E[z^{mX+n}]=z^n E[(z^m)^X]=z^n \cdot G_X(z^m)$
Hi, Moo.

I have an intuitive idea (and this doesn't include you have done) about expectation, but in the book that I'm using it is only treated in chapter 4, and I'm in chapter 2.
Also does your solution takes into account the fact that X takes only integers values, and that non integers are rounded?

p.s. Doing exercises late at night is not good. Plugging m=1 and n=0 in my formula clearly shows that there is a problem with my result.

4. Originally Posted by johanS
Hi, Moo.

I have an intuitive idea (and this doesn't include you have done) about expectation, but in the book that I'm using it is only treated in chapter 4, and I'm in chapter 2.
Just so you know, the expectation is a linear mapping (E[aX+b]=aE[X]+b)
Also does your solution takes into account the fact that X takes only integers values, and that non integers are rounded?
The probability generating function only holds if X has integer values. And the properties of the expectation hold whether X is an integer or not.

Okay then it looks like you can't really use the properties of expectation...

Your problem is that if Y=mX+n, with m and n integers, then Y doesn't take all the nonnegative integer values ! So in your sum there will be some (many) i such that $\displaystyle P(Y=i)=0$.
Which makes your final result quite false

Sorry I have to go (Chinese new year's eve ) so I'll explain you quickly.. Think that you make X vary and hence the pgf of Y is something like $\displaystyle \sum_{k=0}^\infty P(X=k)z^{mk+n}$

5. Okay, so to be more precise... :

In general, when dealing with random variables, the first thing to do is to define the set in which it takes its values.
Let $\displaystyle \mathcal J=\{mk+n \mid k\in\mathbb{N}\}$
This is the set of values for Y.
Let's assume that n<m, so that there is no redundancy (it's just more painful if it's not, but still doable)

So the probability generating function of Y will be :

$\displaystyle G_Y(z)=\sum_{j\in \mathcal J} \mathbb{P}(Y=j)z^j$

Since n<m, for any $\displaystyle j\in\mathcal J$, there is a unique k such that $\displaystyle j=mk+n$ (Euclidean division, as you said)

Hence $\displaystyle \mathbb{P}(Y=j)=\mathbb{P}(X=k)$

So does it look logical to you that $\displaystyle G_Y(z)=\sum_{k\in\mathbb N} \mathbb{P}(X=k)z^{mk+n}$ ?

6. Thank you, Moo.

Actually it's even simpler with your tip of defining the set $\displaystyle \mathcal J$ because since $\displaystyle m$ and $\displaystyle n$ are fixed numbers $\displaystyle \forall j\in \mathcal J \, \exists ! k \in \mathbb{N} \quad j = mk + n$ regardless of whether $\displaystyle m < n$ or not.
So the outcome of any $\displaystyle j \in \mathcal J$ requires that the time taken is one and only one $\displaystyle k \in \mathbb{N}$, which implies that the probability of the cost being $\displaystyle j$ is the same as the probability of the time being $\displaystyle k$, i.e. $\displaystyle P(Y = j) = P(X = k)$.
So $\displaystyle G_Y(z) = \sum_{j \in \mathcal J} P(Y = j)z^j = \sum_{k \in \mathbb{N}} P(X=k)z^{mk + n} =$
$\displaystyle = \sum_{k=0}^{\infty} P(X = k)z^{mk + n} = z^n \sum_{k=0}^{\infty} P(X=k)(z^m)^k = z^nG_X(z^m)$

My mistake was to make Y take on all integers value. Again thank you for your help!

7. Hi,