You are not logged in.
#1 2012-04-29 08:28:52
- anonimnystefy
- Real Member
Offline
Generating Functions
This will be a thread for discussing GFs,their applications and uses,cool identities that can be proven using them and pretty much anything concerning them.Any questions about them are welcome and desirable.
Here is a starter topic:"Using GFs to represent binary trees.How can this be done?"
Last edited by anonimnystefy (2012-04-29 09:26:59)
The limit operator is just an excuse for doing something you know you can't.
“It's the subject that nobody knows anything about that we can all talk about!” ― Richard Feynman
“A secret's worth depends on the people from whom it must be kept.” ― Carlos Ruiz Zafón
#2 2012-04-29 12:05:38
- bobbym
- Administrator
Online
Re: Generating Functions
This is a small tree but it is perfect for an example.
The resulting nodes of the tree are compactly represented by the generating function.
In mathematics, you don't understand things. You just get used to them.
Probability is the most important concept in modern science, especially as nobody has the slightest notion what it means.
90% of mathematicians do not understand 90% of currently published mathematics.
#3 2012-04-29 12:09:00
- anonimnystefy
- Real Member
Offline
Re: Generating Functions
I assume the T and H are tales and heads. 
I know this will sound too much,but,what would the graph and the GF look like for a coin that has the probability of heads change according to some known formula?
The limit operator is just an excuse for doing something you know you can't.
“It's the subject that nobody knows anything about that we can all talk about!” ― Richard Feynman
“A secret's worth depends on the people from whom it must be kept.” ― Carlos Ruiz Zafón
#4 2012-04-29 12:12:32
- bobbym
- Administrator
Online
Re: Generating Functions
Sometimes that is possible with a GF but only by a trick or two. It might be a little more like a Markov chain but that can be tricky too.
In mathematics, you don't understand things. You just get used to them.
Probability is the most important concept in modern science, especially as nobody has the slightest notion what it means.
90% of mathematicians do not understand 90% of currently published mathematics.
#5 2012-04-29 12:15:35
- anonimnystefy
- Real Member
Offline
Re: Generating Functions
It rhymes.
Ok. Could we get an example for that graph you posted using a Markov Chain?
The limit operator is just an excuse for doing something you know you can't.
“It's the subject that nobody knows anything about that we can all talk about!” ― Richard Feynman
“A secret's worth depends on the people from whom it must be kept.” ― Carlos Ruiz Zafón
#6 2012-04-29 16:56:27
- bobbym
- Administrator
Online
Re: Generating Functions
Hi;
Sorry about that, I do not remember how. Checked my notes and found I did not write it down.
In mathematics, you don't understand things. You just get used to them.
Probability is the most important concept in modern science, especially as nobody has the slightest notion what it means.
90% of mathematicians do not understand 90% of currently published mathematics.
#7 2012-04-29 20:52:57
- anonimnystefy
- Real Member
Offline
Re: Generating Functions
I think this is the one:
The limit operator is just an excuse for doing something you know you can't.
“It's the subject that nobody knows anything about that we can all talk about!” ― Richard Feynman
“A secret's worth depends on the people from whom it must be kept.” ― Carlos Ruiz Zafón
#8 2012-04-29 20:55:12
- bobbym
- Administrator
Online
Re: Generating Functions
When you square that you get the same matrix.
In mathematics, you don't understand things. You just get used to them.
Probability is the most important concept in modern science, especially as nobody has the slightest notion what it means.
90% of mathematicians do not understand 90% of currently published mathematics.
#9 2012-04-29 21:08:54
- anonimnystefy
- Real Member
Offline
Re: Generating Functions
Then it is correct.
The limit operator is just an excuse for doing something you know you can't.
“It's the subject that nobody knows anything about that we can all talk about!” ― Richard Feynman
“A secret's worth depends on the people from whom it must be kept.” ― Carlos Ruiz Zafón
#10 2012-04-29 21:12:33
- bobbym
- Administrator
Online
Re: Generating Functions
Apparently, I was trying to get it to do the calculation on the right.
In mathematics, you don't understand things. You just get used to them.
Probability is the most important concept in modern science, especially as nobody has the slightest notion what it means.
90% of mathematicians do not understand 90% of currently published mathematics.
#11 2012-04-29 21:20:45
- anonimnystefy
- Real Member
Offline
Re: Generating Functions
No,squaring the matrix gives the probability of getting from the given state to another in two steps.
The limit operator is just an excuse for doing something you know you can't.
“It's the subject that nobody knows anything about that we can all talk about!” ― Richard Feynman
“A secret's worth depends on the people from whom it must be kept.” ― Carlos Ruiz Zafón
#12 2012-04-29 21:27:18
- bobbym
- Administrator
Online
Re: Generating Functions
That is what I am saying. The answer on the right needs something more than a matrix multiplication. But it is the tree answer. So my original statement that the tree can be represented entirely by a markov chain and matrix operations is not accurate.
In mathematics, you don't understand things. You just get used to them.
Probability is the most important concept in modern science, especially as nobody has the slightest notion what it means.
90% of mathematicians do not understand 90% of currently published mathematics.
#13 2012-04-29 21:32:26
- anonimnystefy
- Real Member
Offline
Re: Generating Functions
Yes,I agree.
What if we multiply by a vector?
The limit operator is just an excuse for doing something you know you can't.
“It's the subject that nobody knows anything about that we can all talk about!” ― Richard Feynman
“A secret's worth depends on the people from whom it must be kept.” ― Carlos Ruiz Zafón
#14 2012-04-29 21:37:38
- bobbym
- Administrator
Online
Re: Generating Functions
Sometimes there is an initial state vector. What vector do you want to use?
In mathematics, you don't understand things. You just get used to them.
Probability is the most important concept in modern science, especially as nobody has the slightest notion what it means.
90% of mathematicians do not understand 90% of currently published mathematics.
#15 2012-04-29 21:38:58
- anonimnystefy
- Real Member
Offline
Re: Generating Functions
Yes,I know. But it doesn't help. What matrix would you like as your output?
The limit operator is just an excuse for doing something you know you can't.
“It's the subject that nobody knows anything about that we can all talk about!” ― Richard Feynman
“A secret's worth depends on the people from whom it must be kept.” ― Carlos Ruiz Zafón
#16 2012-04-29 21:41:06
- bobbym
- Administrator
Online
Re: Generating Functions
You could do a scalar multiplication by A^(1) x A^(2)
In mathematics, you don't understand things. You just get used to them.
Probability is the most important concept in modern science, especially as nobody has the slightest notion what it means.
90% of mathematicians do not understand 90% of currently published mathematics.
#17 2012-04-29 21:42:11
- anonimnystefy
- Real Member
Offline
Re: Generating Functions
What is A?
The limit operator is just an excuse for doing something you know you can't.
“It's the subject that nobody knows anything about that we can all talk about!” ― Richard Feynman
“A secret's worth depends on the people from whom it must be kept.” ― Carlos Ruiz Zafón
#18 2012-04-29 21:44:25
- bobbym
- Administrator
Online
Re: Generating Functions
A is your matrix. A^(1) being the first level of the tree, A^(2) being the second level.
In mathematics, you don't understand things. You just get used to them.
Probability is the most important concept in modern science, especially as nobody has the slightest notion what it means.
90% of mathematicians do not understand 90% of currently published mathematics.
#19 2012-04-29 21:46:17
- anonimnystefy
- Real Member
Offline
Re: Generating Functions
I don't understand what you want to do with that.
The limit operator is just an excuse for doing something you know you can't.
“It's the subject that nobody knows anything about that we can all talk about!” ― Richard Feynman
“A secret's worth depends on the people from whom it must be kept.” ― Carlos Ruiz Zafón
#20 2012-04-29 21:49:22
- bobbym
- Administrator
Online
Re: Generating Functions
Trees are computed by mutiplying nodes down the branches.
In mathematics, you don't understand things. You just get used to them.
Probability is the most important concept in modern science, especially as nobody has the slightest notion what it means.
90% of mathematicians do not understand 90% of currently published mathematics.
#21 2012-04-29 21:51:24
- anonimnystefy
- Real Member
Offline
Re: Generating Functions
Ok,but what does that have to do with matrices?
The limit operator is just an excuse for doing something you know you can't.
“It's the subject that nobody knows anything about that we can all talk about!” ― Richard Feynman
“A secret's worth depends on the people from whom it must be kept.” ― Carlos Ruiz Zafón
#22 2012-04-29 21:52:58
- bobbym
- Administrator
Online
Re: Generating Functions
Instead of the usual multiplication of 2 matrices, we could use an element by element multiplication of 2 matrices.
In mathematics, you don't understand things. You just get used to them.
Probability is the most important concept in modern science, especially as nobody has the slightest notion what it means.
90% of mathematicians do not understand 90% of currently published mathematics.
#23 2012-04-29 21:57:22
- anonimnystefy
- Real Member
Offline
Re: Generating Functions
I don't think it would work for three steps.
The limit operator is just an excuse for doing something you know you can't.
“It's the subject that nobody knows anything about that we can all talk about!” ― Richard Feynman
“A secret's worth depends on the people from whom it must be kept.” ― Carlos Ruiz Zafón
#24 2012-04-29 22:00:46
- bobbym
- Administrator
Online
Re: Generating Functions
Sure it would. Element by element would give 1 / 8 for each branch.
In mathematics, you don't understand things. You just get used to them.
Probability is the most important concept in modern science, especially as nobody has the slightest notion what it means.
90% of mathematicians do not understand 90% of currently published mathematics.
#25 2012-04-29 22:04:03
- anonimnystefy
- Real Member
Offline
Re: Generating Functions
But there would be 8 branches! We only have a 2x2 matrix!
The limit operator is just an excuse for doing something you know you can't.
“It's the subject that nobody knows anything about that we can all talk about!” ― Richard Feynman
“A secret's worth depends on the people from whom it must be kept.” ― Carlos Ruiz Zafón