Generating Function for Probability of Equal Sums in Multinomial Distributions?

[JierenChen]

I don't understand the generating function used to find the probability that the sum of the numbers of occurring events is a certain quantity. Specifically, I'm having trouble with this problem:

"Find the probability of purchasing a ticket with a number whose sums of the first three and last three digits are equal if it has six digits and may be any number from 000000 to 999999"

 

[Wong]

What do you not understand? You do not know how to solve the question? Or you do not know something about multinomial distribution?

I may have some ideas about how to solve the question, but are not usre that will work (or that is correct). First you got six digits on a ticket. The six digits are *independently identically distributed* with a discrete uniform distibution from 0 to 9. Call the digits $$z_{i}$$, i from 1 to 6. The probability generating function (pgf)of $$z_{i}$$ is $$\frac{1-t^{10}}{9(1-t)}$$. Now the pgf of $$z_{1}+z_{2}+z_{3} = \frac{(1-t^{10})^3}{27(1-t)^3}$$ (because $$z_{1}, z_{2}, z_{3}$$ are independent). Now find the pgf of $$-z_{4}-z_{5}-z_{6}$$. How may one find it? The pgf of $$-z_{i}$$ is $$\frac{1-\frac{1}{t^{10}}}{9(1-\frac{1}{t})}$$ and so the pgf of $$-z_{4}-z_{5}-z_{6}$$ is the third power of $$\frac{1-\frac{1}{t^{10}}}{9(1-\frac{1}{t})}$$.

Now the problem is to find the probability of the sum of the first three digits being equal the sum of the last three. This is equivalent to $$Pr(z_{1}+z_{2}+z_{3}-z_{4}-z_{5}-z_{6}=0)$$. The pgf of the random variable $$z_{1}+z_{2}+z_{3}-z_{4}-z_{5}-z_{6}$$ is just the product of that of $$z_{1}+z_{2}+z_{3}$$ and that of $$-z_{4}-z_{5}-z_{6}$$ (as they are all independent). Now you may just "read off" the probability from the pgf.

Not sure the solution is correct. But still I hope that may help.

 

[metacristi]

"Find the probability of purchasing a ticket with a number whose sums of the first three and last three digits are equal if it has six digits and may be any number from 000000 to 999999"

I found an interesting solution,somewhat 'mechanical' (based on 'empirical observations') but without losing any generality,which involves also some basic knowledge of numerical sequences.Here it is.

If the digits of the ticket number are z1 z2 z3 z4 z5 z6 then we can have:

z1+z2+z3=n= 0 OR 1 OR 2 OR 3...OR 27 (1) and

z4+z5+z6=n= 0 OR 1 OR 2 OR 3...OR 27 respectively (2)

(the condition is that z1+z2+z3=z4+z5+z6)

If z1+z2+z3=n=0 then we have a single possibility to arrange the digits in z1 z2 z3,namely 000.

If z1+z2+z3=n=1 ---> 001,010,100 ---> 3 ways

If z1+z2+z3=n=2 ---> 011,101,110,002,020,200 ---> 6 ways

If z1+z2+z3=n=3 ---> 111,021,012,120,102,210,201,003,030,300 ---> 10 ways

If z1+z2+z3=n=4 ---> 004,040,400,013,031,103,130,301,310,112,121,211,122,202,220 ---> 15 ways

The interesting fact is that for z1+z2+z3=n=0,1...,13 the number of ways in which we can write z1 z2 z3 is given by a linear sequence.

Indeed (as must be observed from above,easily to verify numerically,though cumbersome):

n=0 ---> a[n]=1=the possible ways to arrange the digits in z1 z2 z3

n=1 ---> a[1]=3

n=2 ---> a[2]=6

n=3 ---> a[3]=10

n=4 ---> a[4]=15
.
.
.
n=13 ---> a[13]=105

The closed term for a[n] is:

a[n]=(1/2)*n²+(3/2)n+1

The situation is symmetric for n=14,...27 by observing that for n=14 we are exactly in the situation of n=13,n=15 --> n=12,...n=27 ---> n=0.

Exactly the same considerations can be applied to z4 z5 z6.


Now for n=0 for example we have:

z1 z2 z3 ---> 1 way of arranging the digits

z4 z5 z6 ---> 1 way of arranging the digits

Thus the number of ways in which we can write z1 z2 z3 z4 z5 z6 with the condition that z1+z2+z3=z4+z5+z6=0 is N[0]=1*1=1 way

For n=1 we have:

z1 z2 z3 ---> 3 ways of arranging the digits

z4 z5 z6 ---> 3 ways of arranging the digits

The number of ways in which we can write z1 z2 z3 z4 z5 z6 with the condition that z1+z2+z3=z4+z5+z6=1 is N[1]=3*3=9 ways.

Analogously for n=2 ---> N[2]=6*6=36 and so on till n=13.

By observing that for n=14,...,27 we have symmetry we can compute the required probability P as:

P=∑ _{from k=0 to k=13} 2*{[(1/2)*k²+(3/2)k+1]²}/1000000

 

[JierenChen]

Thanks all for your replies. I'm starting to understand the problem but I'm still not exactly sure what generating functions are supposed to do.

coudl anyone help me?

 

[Wong]

Chen, so your problem is that you do not understand what are the uses of a generating function?

 

[JierenChen]

Actually now I understand. I'm just now sure exactly how to get to the generating function.