Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Random walk

  1. Nov 30, 2008 #1
    1. The problem statement, all variables and given/known data
    http://img171.imageshack.us/img171/4711/52047019pc2.png [Broken]
    1. The problem statement, all variables and given/known data



    2. Relevant equations
    Random walk equations: Xi is i.i.d. and [tex]S_n = X_1+...+X_n[/tex] and S0=0


    3. 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: May 3, 2017
  2. jcsd
  3. Dec 1, 2008 #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: Dec 1, 2008
  4. Dec 1, 2008 #3
    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?
     
  5. Dec 1, 2008 #4
    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.
     
  6. Dec 1, 2008 #5
    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?
     
  7. Dec 1, 2008 #6
    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: Dec 1, 2008
  8. Dec 1, 2008 #7
    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?
     
  9. Dec 1, 2008 #8
    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: Dec 1, 2008
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook