Results 1 to 7 of 7

Math Help - Generating function of aX + m

  1. #1
    Newbie
    Joined
    Feb 2010
    Posts
    11

    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
     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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    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)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Feb 2010
    Posts
    11
    Quote Originally Posted by Moo View Post
    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.
    Last edited by johanS; February 13th 2010 at 08:25 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Quote Originally Posted by johanS View Post
    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}
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    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} ?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Feb 2010
    Posts
    11
    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!
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    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 ^^
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Finding probability function of moment generating function
    Posted in the Advanced Statistics Forum
    Replies: 6
    Last Post: July 4th 2011, 05:03 PM
  2. generating function
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: February 25th 2011, 05:54 PM
  3. Generating function
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: May 20th 2010, 06:29 PM
  4. generating function
    Posted in the Advanced Statistics Forum
    Replies: 3
    Last Post: February 8th 2010, 08:33 AM
  5. Moment generating function and distribution function?
    Posted in the Advanced Statistics Forum
    Replies: 4
    Last Post: January 25th 2009, 03:02 PM

Search Tags


/mathhelpforum @mathhelpforum