Notation help

From what you've posted, I have no idea what the summation is supposed to be over either. I suspect you'd have to post a lot for anyone to be able to help, and since I'm not a probability bod, it's unlikely that helpful person would be me. Up to you...

Reply 2

Kolya

17

notnek

Can someone help me understand the summation? The book does not say what the summation is over and I'm struggling to interpret what it means.

I've never studied this but, as a completely wild guess, they might be summing over

n

?...

Reply 3

OP

I'll post a bit more.

The kth moment of the mean eigenvalue distribution of a random symmetric matrix T(n) is given as

Unparseable latex formula:

\tau_n(T(n)^k)=\frac{1}{n^{\frac{k}{2}+1}} \sum E(\xi_{m_1}_{m_2} \xi_{m_2}_{m_3} \cdots \xi_{m_k}_{m_1})

*The summation is over all

1\leq m_1,m_2,...,m_k \leq n

.

After my last post, I found * on another page. Even after finding it, I'm still not sure what the summation means...

Reply 4

notnek

Even after finding it, I'm still not sure what the summation means...

It's the same as:

Unparseable latex formula:

\displaystyle \sum_{m_1 = 1}^n \sum_{m_2 = 1}^n \cdots \sum_{m_k = 1}^n E(\xi_{m_1}_{m_2} \xi_{m_2}_{m_3} \cdots \xi_{m_k}_{m_1})

if that helps. But it's better to think of it in the way the book describes; that is, you're summing over all sets of values

m_1, m_2, ..., m_k

such that

1 \leq m_1 \leq n, 1 \leq m_2 \leq n, \cdots 1 \leq m_k \leq n

.

Reply 5

OP

That makes sense now. I should have figured it out myself and I kicked myself when I read your post.

There's one more thing to do with combinatorics which I'm not sure about. It follows on from this equation.

'The terms

Unparseable latex formula:

E(\xi_{m_1}_{m_2} \xi_{m_2}_{m_3} \cdots \xi_{m_k}_{m_1})

can be grouped according to the cardinality of the set

\{m_1,m_2,...,m_k\}

.

The number of terms such that

\#\{m_1,m_2,...,m_k\}=l

is less than:

\displaystyle {n\choose l}l^k

'

I'm sure I'll kick myself again once I understand it.

Reply 6

notnek

That makes sense now. I should have figured it out myself and I kicked myself when I read your post.

There's one more thing to do with combinatorics which I'm not sure about. It follows on from this equation.

'The terms

Unparseable latex formula:

E(\xi_{m_1}_{m_2} \xi_{m_2}_{m_3} \cdots \xi_{m_k}_{m_1})

can be grouped according to the cardinality of the set

\{m_1,m_2,...,m_k\}

.

The number of terms such that

\#\{m_1,m_2,...,m_k\}=l

is less than:

\displaystyle {n\choose l}l^k

'

I'm sure I'll kick myself again once I understand it.

If

\#\{m_1,m_2,...,m_k\}=l

, then m_1, ..., m_k only take l values out of 1,..., n.

Try to enumerate those ways, thinking about where the two terms

\binom{n}{l}

and l^k might come from.

full spoiler

Note that for cases l = 0 or l = 1, the number of terms is in fact exactly

\binom{n}{l} l^k

.

Reply 7

OP

Thank you for your reply. I don't see how

\#\{m_1,m_2,...,m_k\}

can be anything other than k since the index of m goes from 1 to k in that set.

I can kind of understand the rest of your post but it's the above which I'm struggling to get my head around.

Reply 8

notnek

Thank you for your reply. I don't see how

\#\{m_1,m_2,...,m_k\}

can be anything other than k since the index of m goes from 1 to k in that set.e.g. k = 5, m_1 = m_2 = m_3 = 1, m_4 = m_5 = 4.

Then

\{m_1,m_2,...,m_k\} = \{1,4\}

(since in every case m_j is either 1 or 4) and so

\#\{m_1,m_2,...,m_k\} = 2

.

Reply 9

OP

I don't know why I didn't see that. Thank you.

DFranklin

If l > 1, this includes cases where we have less than l distinct values, for example, the cases where m_1 = m_2 = ... = m_k. So the inequality must actually be strict.

I've nearly got it but I can't seem to understand this^.
If m_1=m_2=..m_k, how can l be greater than 1?

Reply 10

notnek

I don't know why I didn't see that. Thank you.

I've nearly got it but I can't seem to understand this^.
If m_1=m_2=..m_k, how can l be greater than 1?

It can't. That's the point.

We counted the number of ways we could assign l values to each of m_1, m_2, ..., m_k, but we didn't make sure we assigned l distinct values. So all we can say is that the size of our set is

\leq \binom{n}{l} l^k

, because we've also counted cases where we didn't get l distinct values.

Now this is *almost* what the question asks us to show, but the question actually wants a strict inequality. So the "m_1=m_2=..m_k" case is to show that if l > 1, then we've *definitely* counted cases we shouldn't (where we don't get l distinct values), and so we can't have equality.

Reply 11

OP

This should be my last problem in this thread but I did say that before! Quote from the book:

'Due to the Holder inequality

\displaystyle |E(\xi_{m_1 m_2}(n)\cdots \xi_{m_k m_1}(n))|\leq E(|\xi_{m_1 m_2}(n)|^k)^{\frac{1}{k}}\cdots E(|\xi_{m_k m_1}(n)|^k)^{\frac{1}{k}}

'

But the Holder inequality applies when there are two different outer reciprocated powers on the RHS: p and q where

\frac{1}{p}+\frac{1}{q}=1

. This is not what is written in the book.

Reply 12

Have a look at http://en.wikipedia.org/wiki/H%C3%B6lder%27s_inequality#Generalization_of_H.C3.B6lder.27s_inequality

I think this applies here with r = 1, p_1 = p_2 = ... = p_k = k.

Reply 13

OP

That works, thanks.

Am I right in saying that the norm on the wiki page is an integral but E(X) can be used since it is just an integral.

Reply 14

notnek

That works, thanks.

Am I right in saying that the norm on the wiki page is an integral but E(X) can be used since it is just an integral.

If you look further up they also state Holder's equality for expectations.

I think basically what you said is right, but I'm not sure if there are any fiddly details. I don't remember much measure theory.

Reply 15

OP

Everything I've asked so far has been part of a proof in a book. Unfortunately, I'm still struggling with it and TSR (mainly DFranklin :smile:

) is a great help when my tutor is not available.

This is a link to the part I need help with. It should begin, 'E(...)=0' and ends with 'by removing ... from m_1...m_k'.

I can understand that if the sentence which ends with the highlighted part is true then

E(\xi_{m_i m_{i+1}})

can be factored out since the term is independent. Then the result comes from the assumption that the expectation of the random variables are 0.

I'm having trouble understanding how to do the induction. I think I understand most of what is written but I'm not sure how one can develop a proof by induction from it. I can see what the hypothesis is but I'm not sure where to go from there. This may be too much to ask but can someone help me understand how to do it?

EDIT:

\xi_{i j}=\xi_{j i}

is needed for this. The link has just been edited.

Reply 16

notnek

This may be too much to ask but can someone help me understand how to do it?Probably, I fear, at least unless someone else can help.

To be honest, I suspect I can't help, but if you want to try anyhow and see if we can get somewhere together:

Looking at what you've linked to, I find they keep talking about "non-crossing pair partitions", which I've never heard of. Can you explain what this phrase means?

Edit: Hold on - I think I've looked at the wrong bit of the book. Let me see...

2nd Edit: So, to be clear, you're having trouble with the induction that shows there's a factor

Unparseable latex formula:

\xi_{m_i, m_{i+1}

that isn't repeated?

If so, which case are you having trouble with? (The only bit I thought wasn't obvious is what happens in the case

m_{p-1} = m_{p+1}

, so I suspect that's what you're stuck on, but I'm not totally sure).

Reply 17

notnek

..

Just pinging you to say that I think I understand this now (at least up to "removing ... from m_1, ..., m_k"!).

Reply 18

OP

Your 2nd edit is correct.

I thought I understood it all until I remembered that it was a proof by induction. I don't see where the induction hypothesis p(k) has been assumed and then shown true for p(k+1).
I just thought the paragraph was to help with the induction.

Reply 19