Generating function of aX + m

**johanS** · February 12th 2010, 01:41 PM

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

With this I got $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 $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.

**Moo** · February 13th 2010, 05:42 AM

Hello,

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

**johanS** · February 13th 2010, 06:39 AM

Originally Posted by Moo

Hello,

Well, maybe what you did is correct, but here's a better way...
$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.

**Moo** · February 13th 2010, 08:09 AM

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 $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 $\sum_{k=0}^\infty P(X=k)z^{mk+n}$

**Moo** · February 14th 2010, 12:16 AM

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 $\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 :

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

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

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

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

**johanS** · February 14th 2010, 09:02 AM

Thank you, Moo.

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

**Moo** · February 14th 2010, 09:49 AM

Hi,

I'm glad you understand

And yes, it doesn't matter whether n<m or not. I got confused in the case where n is a multiple of m, but that was just a matter of logic ^^

Thread: Generating function of aX + m

LinkBack

Thread Tools

Display

Generating function of aX + m

Similar Math Help Forum Discussions

Finding probability function of moment generating function

generating function

Generating function

generating function

Moment generating function and distribution function?

Search Tags