1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Random walk

  1. Nov 30, 2008 #1
    1. The problem statement, all variables and given/known data
    [​IMG]
    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.
     
  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
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Random walk
  1. Random walk in a graph (Replies: 18)

  2. Random walk? (Replies: 5)

  3. Random walk on circle (Replies: 1)

  4. Random walk? (Replies: 8)

Loading...