Archive | April 2014

Random walking trough a lattice

This post is a draft

Problem setup

Consider the following lattice:


Possible path in a lattice

Possible path in a lattice

Suppose you want to move from point A to C, but such that you can only go one step to the right or upwards at a time. For an n x m lattice, there are

(n + m)! / (n! m!)

posible paths. This is so due to the fact that if we denote r as going to the right and u as going upwards, then for every permutation of the symbols r and u with n times r and m times u, there exist exactly one path, and conversely, every path from A to C can be represented with exactly one such permutation.

Let say a path corner is a node in the lattice such that the trajectory changes direction there, either from going right to upwards or viceverse.

Given a path from A to C, what is the probability that it has R corners?

First note that for every corner, there is one upward and one right movement, so that there are at most 2 min(n, m) – 1 corners in a valid path.


An odd trajectory in a lattice

An odd trajectory in a lattice

Fix a path in the lattice, such that its first movement is to the right and the last one is upwards. No matter the path shape, it will always have an odd number of corners. Suppose an odd number R in the range 1,…,(2 min(n, m) – 1) is given, in order to calculate the probability for a path having R and due to the fact that the paths are uniformly distribuited, we must count how many paths are there with exactly such a number of corners.

Consider the previous figure, with the present hypotesis of the first movement being to the right, and labeling the corners in the order shown in the figure, then the upward movements correspond begin in the odd labeled vertixes, moreover, we must accomodate (R – 1) / 2 odd numbered vertixes in n – 1 horizontal cell boundaries, which is accomplished with the combinatoric formula

C_{(n – 1), (R – 1) / 2}

For each one of those horizontal partitions, we must select one possible vertical partition, such that que horizontal step begins with an even numbered label, in the range 2,…, R – 1. There are (R – 1) / 2 even labels and m – 1 posible vertical boundaries where to accomodate them, therefore, there are

C_{(m – 1), (R – 1) / 2}

ways to do so, and the total different paths we can get considering the horizontal and vertical ordering of the vertixes is

C_{(n – 1), (R – 1) / 2} C_{(m – 1), (R – 1) / 2}

The case where the walk starts upwards and finishes to the right is simmilar, with n and m reserved, and therefore the formula is the same.

Consider the case when the movement start and finishes going to the right, like in the next figure:


A path in a lattice with an even number of corners

A path in a lattice with an even number of corners

in contrast with the previous cases, there is an even number of corners, and every leftwise corner in a row, except the first, is even labeled, so that from the m – 1 inner rows in the lattice, there should be chosen (R – 2) / 2 rows to accomodate the corners. Likewise, from the n – 1 inner columns in the lattice, we must choose R / 2 columns in order to acoomodate the corners. In total, there are

C_{(n – 1), R / 2} C_{(m – 1), (R – 2) / 2}

different ways to accomodate the corners.

The final case is analogous, and therefore there should be

C_{(n – 1), (R – 2) / 2} C_{(m – 1), R / 2}

different paths with first and last movement upwards and R corners.

Counting corners

For the details, see here.