How Do Permutations Affect Sums in Random Walk Equations?

[dirk_mec1]

Homework Statement

http://img171.imageshack.us/img171/4711/52047019pc2.png

Homework Statement

Homework Equations

Random walk equations: X_i is i.i.d. and S_n = X_1+...+X_n and S₀=0

The Attempt at a Solution

I don't have a idea where to begin. I couldn't start because I don't know how to apply the random walk.

 

[pizzasky]

For starters, there may be a slight error in the question. I think the result to be proven should be P\displaystyle{\{} \sum_{j\displaystyle{=}1}^n jX_{j} \leq a \displaystyle{\}} = P\displaystyle{\{} \sum_{j\displaystyle{=}1}^n jX_{j} \geq \frac{n(n+1)^2}{2}-a \displaystyle{\}}.

Since (X_{1},X_{2},...,X_{n}) is equally likely to be any of the n! permutations of (1,2,...,n), it suffices to prove that the number of permutations

satisfying \sum_{j\displaystyle{=}1}^n jx_{j} \leq a is equal to the number of permutations satisfying \sum_{j\displaystyle{=}1}^n jx_{j} \geq \frac{n(n+1)^2}{2}-a.

Now, to prove this, we show that given a permutation (x_{1},x_{2},...,x_{n}) satisfying \sum_{j\displaystyle{=}1}^n jx_{j} \leq a, we can use this permutation to find another permutation (y_{1},y_{2},...,y_{n}) having the property \sum_{j\displaystyle{=}1}^n jy_{j} \geq \frac{n(n+1)^2}{2}-a, and vice versa.

How can the other permutation be found? Hint: In a permutation, order matters! So, moving the terms around seems a good place to start.

 

[dirk_mec1]

Yes, you're right about the mistake, my instructor told us that but I forgot to tell you.So by permutations they mean:

\left( \begin{array}{c}n \\ x \end{array} \right)

where x can be 1,...,n and the answer for one x corresponds to a X_i, right?But then \sum_{j=1}^n j x_j = \sum_{j=1}^n \left( \begin{array}{c}n \\ x \end{array} \right) = \sum_{j=1}^n \left( \begin{array}{c}n \\ n-x \end{array} \right)

Is this what you mean? But how can I proceed then because if the above expression is smaller than a how can I pop up a n(n+1)^2?

 

[pizzasky]

A permutation is simply an arrangement of the numbers 1, 2, 3, ..., n. So, examples of permutations are (1, 2, 3, ..., n-1, n) ,
(2, 3, 4, ..., n, 1) etc. There are n! such permutations in all, as mentioned in the question.

 

[dirk_mec1]

A permutation is simply an arrangement of the numbers 1, 2, 3, ..., n. So, examples of permutations are (1, 2, 3, ..., n-1, n) ,
(2, 3, 4, ..., n, 1) etc. There are n! such permutations in all, as mentioned in the question.

Right, I understand. But how can I interpretet then (for example) \sum_{j=1}^n j X_j = 1 \cdot (1, 2, 3, ..., n-1, n) + 2\cdot (2, 3, 4, ..., n, 1)+...

I presume the sum means 'per element of the permutation' but how can such a thing be bounded by a? Is that componentwise bounded?

 

[pizzasky]

Take for example the permutation (x_{1},x_{2},...,x_{n}) = (1, 2, ..., n). We have \sum_{j=1}^n j x_j = 1^2 + 2^2 + ... + n^2.

Thus, the question is asking us to show that the probability of a permutation (x_{1},x_{2},...,x_{n}) having the property \sum_{j\displaystyle{=}1}^n jx_{j} \leq a is the same as the probability of a permutation having the property \sum_{j\displaystyle{=}1}^n jx_{j} \geq \frac{n(n+1)^2}{2}-a.

 

[dirk_mec1]

I've thought about your hint and I don't see how changing the order is going to effect anything.

Suppose x= (x1,..xn) =(1,...,n) then if you calculate the sum you'll get a sum of squares:

1^2 +2^2+...+n^2 = \frac{n(n+1)(2n+1)}{ 6}

Is this the direction where I should be going?

 

[pizzasky]

I believe changing the order of the terms is going to have an effect on the sum at least. Suppose (x_{1},x_{2},...,x_{n}) = (1, 2, ..., n) and (y_{1},y_{2},...,y_{n}) = (n, ..., 1). In general, \sum_{j\displaystyle{=}1}^n jx_{j} is not equal to \sum_{j\displaystyle{=}1}^n jy_{j}.

Here's a possible approach to the question:

Let A be the set of permutations (x_{1},x_{2},...,x_{n}) satisfying \sum_{j\displaystyle{=}1}^n jx_{j} \leq a and B be the set of permutations (y_{1},y_{2},...,y_{n}) satisfying \sum_{j\displaystyle{=}1}^n jy_{j} \geq \frac{n(n+1)^2}{2}-a. Let |A| and |B| denote the number of elements in A and B respectively. Our goal is to show that |A| = |B| (refer to the second post). We will prove this statement in 2 parts.


Part 1: |A| \leq |B|
We prove this by showing that for every permutation (x_{1},x_{2},...,x_{n}) in A, we can change the order of the terms in a certain way to create a permutation (y_{1},y_{2},...,y_{n}) that will be in B. This will mean that |B| cannot be smaller than |A|, and thus |A| \leq |B| (since this mapping from set A to set B is injective or one-to-one). Now, consider a permutation (x_{1},x_{2},...,x_{n}) in A. We will try to shuffle the terms around in a certain manner, and show that the new permutation (y_{1},y_{2},...,y_{n}) we get is an element of B. What is one obvious guess for (y_{1},y_{2},...,y_{n})? Try then to show that \sum_{j\displaystyle{=}1}^n jy_{j} \geq \frac{n(n+1)^2}{2}-a, given the fact that \sum_{j\displaystyle{=}1}^n jx_{j} \leq a.

Part 2: |B| \leq |A|
The idea of this part is the same as before; we show that for every permutation (y_{1},y_{2},...,y_{n}) in B, we can change the order of the terms in a certain way to create a permutation (x_{1},x_{2},...,x_{n}) that will be in A. The structure of the proof is similar to Part 1.

Combining our results for both parts, we get |A| = |B| and we are done.