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.