Discussion about math, puzzles, games and fun. Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ π -¹ ² ³ °

You are not logged in.

- Topics: Active | Unanswered

**anonimnystefy****Real Member**- From: Harlan's World
- Registered: 2011-05-23
- Posts: 15,937

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-28 11:26:59)*

Here lies the reader who will never open this book. He is forever dead.

Taking a new step, uttering a new word, is what people fear most. ― Fyodor Dostoyevsky, Crime and Punishment

The knowledge of some things as a function of age is a delta function.

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 97,095

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.**

**If it ain't broke, fix it until it is.**

Offline

**anonimnystefy****Real Member**- From: Harlan's World
- Registered: 2011-05-23
- Posts: 15,937

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?

Here lies the reader who will never open this book. He is forever dead.

Taking a new step, uttering a new word, is what people fear most. ― Fyodor Dostoyevsky, Crime and Punishment

The knowledge of some things as a function of age is a delta function.

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 97,095

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.**

**If it ain't broke, fix it until it is.**

Offline

**anonimnystefy****Real Member**- From: Harlan's World
- Registered: 2011-05-23
- Posts: 15,937

It rhymes.

Ok. Could we get an example for that graph you posted using a Markov Chain?

Here lies the reader who will never open this book. He is forever dead.

Taking a new step, uttering a new word, is what people fear most. ― Fyodor Dostoyevsky, Crime and Punishment

The knowledge of some things as a function of age is a delta function.

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 97,095

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.**

**If it ain't broke, fix it until it is.**

Offline

**anonimnystefy****Real Member**- From: Harlan's World
- Registered: 2011-05-23
- Posts: 15,937

I think this is the one:

Taking a new step, uttering a new word, is what people fear most. ― Fyodor Dostoyevsky, Crime and Punishment

The knowledge of some things as a function of age is a delta function.

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 97,095

When you square that you get the same matrix.

**In mathematics, you don't understand things. You just get used to them.**

**If it ain't broke, fix it until it is.**

Offline

**anonimnystefy****Real Member**- From: Harlan's World
- Registered: 2011-05-23
- Posts: 15,937

Then it is correct.

Taking a new step, uttering a new word, is what people fear most. ― Fyodor Dostoyevsky, Crime and Punishment

The knowledge of some things as a function of age is a delta function.

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 97,095

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.**

**If it ain't broke, fix it until it is.**

Offline

**anonimnystefy****Real Member**- From: Harlan's World
- Registered: 2011-05-23
- Posts: 15,937

No,squaring the matrix gives the probability of getting from the given state to another in two steps.

Taking a new step, uttering a new word, is what people fear most. ― Fyodor Dostoyevsky, Crime and Punishment

The knowledge of some things as a function of age is a delta function.

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 97,095

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.**

**If it ain't broke, fix it until it is.**

Offline

**anonimnystefy****Real Member**- From: Harlan's World
- Registered: 2011-05-23
- Posts: 15,937

Yes,I agree.

What if we multiply by a vector?

Taking a new step, uttering a new word, is what people fear most. ― Fyodor Dostoyevsky, Crime and Punishment

The knowledge of some things as a function of age is a delta function.

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 97,095

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.**

**If it ain't broke, fix it until it is.**

Offline

**anonimnystefy****Real Member**- From: Harlan's World
- Registered: 2011-05-23
- Posts: 15,937

Yes,I know. But it doesn't help. What matrix would you like as your output?

Taking a new step, uttering a new word, is what people fear most. ― Fyodor Dostoyevsky, Crime and Punishment

The knowledge of some things as a function of age is a delta function.

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 97,095

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.**

**If it ain't broke, fix it until it is.**

Offline

**anonimnystefy****Real Member**- From: Harlan's World
- Registered: 2011-05-23
- Posts: 15,937

What is A?

Taking a new step, uttering a new word, is what people fear most. ― Fyodor Dostoyevsky, Crime and Punishment

The knowledge of some things as a function of age is a delta function.

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 97,095

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.**

**If it ain't broke, fix it until it is.**

Offline

**anonimnystefy****Real Member**- From: Harlan's World
- Registered: 2011-05-23
- Posts: 15,937

I don't understand what you want to do with that.

Taking a new step, uttering a new word, is what people fear most. ― Fyodor Dostoyevsky, Crime and Punishment

The knowledge of some things as a function of age is a delta function.

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 97,095

Trees are computed by mutiplying nodes down the branches.

**In mathematics, you don't understand things. You just get used to them.**

**If it ain't broke, fix it until it is.**

Offline

**anonimnystefy****Real Member**- From: Harlan's World
- Registered: 2011-05-23
- Posts: 15,937

Ok,but what does that have to do with matrices?

Taking a new step, uttering a new word, is what people fear most. ― Fyodor Dostoyevsky, Crime and Punishment

The knowledge of some things as a function of age is a delta function.

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 97,095

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.**

**If it ain't broke, fix it until it is.**

Offline

**anonimnystefy****Real Member**- From: Harlan's World
- Registered: 2011-05-23
- Posts: 15,937

I don't think it would work for three steps.

Taking a new step, uttering a new word, is what people fear most. ― Fyodor Dostoyevsky, Crime and Punishment

The knowledge of some things as a function of age is a delta function.

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 97,095

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.**

**If it ain't broke, fix it until it is.**

Offline

**anonimnystefy****Real Member**- From: Harlan's World
- Registered: 2011-05-23
- Posts: 15,937

But there would be 8 branches! We only have a 2x2 matrix!

Taking a new step, uttering a new word, is what people fear most. ― Fyodor Dostoyevsky, Crime and Punishment

The knowledge of some things as a function of age is a delta function.

Offline