Random walk

  • Thread starter dirk_mec1
  • Start date
  • #1
761
13

Homework Statement


http://img171.imageshack.us/img171/4711/52047019pc2.png [Broken]

Homework Statement





Homework Equations


Random walk equations: Xi is i.i.d. and [tex]S_n = X_1+...+X_n[/tex] and S0=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.
 
Last edited by a moderator:

Answers and Replies

  • #2
172
2
For starters, there may be a slight error in the question. I think the result to be proven should be [tex] 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{\}} [/tex].

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

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

Now, to prove this, we show that given a permutation [tex] (x_{1},x_{2},...,x_{n}) [/tex] satisfying [tex] \sum_{j\displaystyle{=}1}^n jx_{j} \leq a [/tex], we can use this permutation to find another permutation [tex] (y_{1},y_{2},...,y_{n}) [/tex] having the property [tex] \sum_{j\displaystyle{=}1}^n jy_{j} \geq \frac{n(n+1)^2}{2}-a [/tex], 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.
 
Last edited:
  • #3
761
13
Yes, you're right about the mistake, my instructor told us that but I forgot to tell you.


So by permutations they mean:

[tex] \left( \begin{array}{c}n \\ x \end{array} \right) [/tex]

where x can be 1,...,n and the answer for one x corresponds to a Xi, right?


But then [tex] \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)[/tex]

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?
 
  • #4
172
2
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.
 
  • #5
761
13
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) [tex] \sum_{j=1}^n j X_j = 1 \cdot (1, 2, 3, ..., n-1, n) + 2\cdot (2, 3, 4, ...., n, 1)+... [/tex]

I presume the sum means 'per element of the permutation' but how can such a thing be bounded by a? Is that componentwise bounded?
 
  • #6
172
2
Take for example the permutation [tex] (x_{1},x_{2},...,x_{n}) = (1, 2, ..., n) [/tex]. We have [tex] \sum_{j=1}^n j x_j = 1^2 + 2^2 + ... + n^2 [/tex].

Thus, the question is asking us to show that the probability of a permutation [tex] (x_{1},x_{2},...,x_{n}) [/tex] having the property [tex] \sum_{j\displaystyle{=}1}^n jx_{j} \leq a [/tex] is the same as the probability of a permutation having the property [tex] \sum_{j\displaystyle{=}1}^n jx_{j} \geq \frac{n(n+1)^2}{2}-a [/tex].
 
Last edited:
  • #7
761
13
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:

[tex] 1^2 +2^2+...+n^2 = \frac{n(n+1)(2n+1)}{ 6} [/tex]

Is this the direction where I should be going?
 
  • #8
172
2
I believe changing the order of the terms is going to have an effect on the sum at least. Suppose [tex] (x_{1},x_{2},...,x_{n}) = (1, 2, ..., n)[/tex] and [tex] (y_{1},y_{2},...,y_{n}) = (n, ..., 1)[/tex]. In general, [tex] \sum_{j\displaystyle{=}1}^n jx_{j}[/tex] is not equal to [tex] \sum_{j\displaystyle{=}1}^n jy_{j} [/tex].

Here's a possible approach to the question:

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

Part 2: [tex] |B| \leq |A| [/tex]
The idea of this part is the same as before; we show that for every permutation [tex] (y_{1},y_{2},...,y_{n}) [/tex] in B, we can change the order of the terms in a certain way to create a permutation [tex] (x_{1},x_{2},...,x_{n}) [/tex] 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.
 
Last edited:

Related Threads on Random walk

  • Last Post
Replies
8
Views
2K
  • Last Post
Replies
5
Views
1K
  • Last Post
Replies
5
Views
300
  • Last Post
Replies
1
Views
3K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
18
Views
2K
  • Last Post
Replies
3
Views
3K
  • Last Post
Replies
1
Views
454
Top