The equilibrium distribution for a class of multi-dimensional random walks

G.J. van Houtum, I.J.B.F. Adan, J. Wessels, W.H.M. Zijm

    Research output: Book/ReportReportProfessional

    5 Downloads (Pure)

    Abstract

    In previous papers, it has been proved that the equilibrium distribution of homogeneous, nearest-neighboring random walks on a two-dimensional grid can be constructed explicitly through a compensation procedure if and only if there are no transitions to the North, North-East and East for points in the interior. In the present paper the extension to N-dimensional random walks is investigated. It appears that for higher dimensions the same condition should be satisfied for each plane in the grid space. Since induction with respect to the dimension is applied. the step from dimension 2 to dimension 3 is worked out in detail. For the proof of the if-part the condition is added that the random walk satisfies the so-called projection property on the boundaries. For 3-dimensional random walks, the eqUilibrium distribution appears to be the sum of six alternating series of binary trees of product forms. These analytic results make it possible to develop efficient numerical procedures. Such procedures are sketched in the paper. As a numerical illustration, the procedures are applied to the model of a 2 x 3 switch.
    Original languageEnglish
    Place of PublicationEindhoven
    PublisherEindhoven University of Technology
    Number of pages54
    Publication statusPublished - 1 Feb 1994

    Publication series

    NameCOSOR Memorandum
    PublisherEindhoven University of Technology
    Volume94-01
    ISSN (Print)0926-4493

    Fingerprint

    Equilibrium Distribution
    Random walk
    Alternating series
    Projection Property
    Grid
    Product Form
    Binary Tree
    Numerical Procedure
    Higher Dimensions
    Switch
    Proof by induction
    Interior
    If and only if
    Class
    Model

    Keywords

    • Multi-dimensional random walk
    • Markov chain
    • Equilibrium distribution
    • Product forms
    • Compensation approach

    Cite this

    van Houtum, G. J., Adan, I. J. B. F., Wessels, J., & Zijm, W. H. M. (1994). The equilibrium distribution for a class of multi-dimensional random walks. (COSOR Memorandum; Vol. 94-01). Eindhoven: Eindhoven University of Technology.
    van Houtum, G.J. ; Adan, I.J.B.F. ; Wessels, J. ; Zijm, W.H.M. / The equilibrium distribution for a class of multi-dimensional random walks. Eindhoven : Eindhoven University of Technology, 1994. 54 p. (COSOR Memorandum).
    @book{3e36f18f60b240adb7ec9d3d83fef31a,
    title = "The equilibrium distribution for a class of multi-dimensional random walks",
    abstract = "In previous papers, it has been proved that the equilibrium distribution of homogeneous, nearest-neighboring random walks on a two-dimensional grid can be constructed explicitly through a compensation procedure if and only if there are no transitions to the North, North-East and East for points in the interior. In the present paper the extension to N-dimensional random walks is investigated. It appears that for higher dimensions the same condition should be satisfied for each plane in the grid space. Since induction with respect to the dimension is applied. the step from dimension 2 to dimension 3 is worked out in detail. For the proof of the if-part the condition is added that the random walk satisfies the so-called projection property on the boundaries. For 3-dimensional random walks, the eqUilibrium distribution appears to be the sum of six alternating series of binary trees of product forms. These analytic results make it possible to develop efficient numerical procedures. Such procedures are sketched in the paper. As a numerical illustration, the procedures are applied to the model of a 2 x 3 switch.",
    keywords = "Multi-dimensional random walk, Markov chain, Equilibrium distribution, Product forms, Compensation approach",
    author = "{van Houtum}, G.J. and I.J.B.F. Adan and J. Wessels and W.H.M. Zijm",
    year = "1994",
    month = "2",
    day = "1",
    language = "English",
    series = "COSOR Memorandum",
    publisher = "Eindhoven University of Technology",

    }

    van Houtum, GJ, Adan, IJBF, Wessels, J & Zijm, WHM 1994, The equilibrium distribution for a class of multi-dimensional random walks. COSOR Memorandum, vol. 94-01, Eindhoven University of Technology, Eindhoven.

    The equilibrium distribution for a class of multi-dimensional random walks. / van Houtum, G.J.; Adan, I.J.B.F.; Wessels, J.; Zijm, W.H.M.

    Eindhoven : Eindhoven University of Technology, 1994. 54 p. (COSOR Memorandum; Vol. 94-01).

    Research output: Book/ReportReportProfessional

    TY - BOOK

    T1 - The equilibrium distribution for a class of multi-dimensional random walks

    AU - van Houtum, G.J.

    AU - Adan, I.J.B.F.

    AU - Wessels, J.

    AU - Zijm, W.H.M.

    PY - 1994/2/1

    Y1 - 1994/2/1

    N2 - In previous papers, it has been proved that the equilibrium distribution of homogeneous, nearest-neighboring random walks on a two-dimensional grid can be constructed explicitly through a compensation procedure if and only if there are no transitions to the North, North-East and East for points in the interior. In the present paper the extension to N-dimensional random walks is investigated. It appears that for higher dimensions the same condition should be satisfied for each plane in the grid space. Since induction with respect to the dimension is applied. the step from dimension 2 to dimension 3 is worked out in detail. For the proof of the if-part the condition is added that the random walk satisfies the so-called projection property on the boundaries. For 3-dimensional random walks, the eqUilibrium distribution appears to be the sum of six alternating series of binary trees of product forms. These analytic results make it possible to develop efficient numerical procedures. Such procedures are sketched in the paper. As a numerical illustration, the procedures are applied to the model of a 2 x 3 switch.

    AB - In previous papers, it has been proved that the equilibrium distribution of homogeneous, nearest-neighboring random walks on a two-dimensional grid can be constructed explicitly through a compensation procedure if and only if there are no transitions to the North, North-East and East for points in the interior. In the present paper the extension to N-dimensional random walks is investigated. It appears that for higher dimensions the same condition should be satisfied for each plane in the grid space. Since induction with respect to the dimension is applied. the step from dimension 2 to dimension 3 is worked out in detail. For the proof of the if-part the condition is added that the random walk satisfies the so-called projection property on the boundaries. For 3-dimensional random walks, the eqUilibrium distribution appears to be the sum of six alternating series of binary trees of product forms. These analytic results make it possible to develop efficient numerical procedures. Such procedures are sketched in the paper. As a numerical illustration, the procedures are applied to the model of a 2 x 3 switch.

    KW - Multi-dimensional random walk

    KW - Markov chain

    KW - Equilibrium distribution

    KW - Product forms

    KW - Compensation approach

    M3 - Report

    T3 - COSOR Memorandum

    BT - The equilibrium distribution for a class of multi-dimensional random walks

    PB - Eindhoven University of Technology

    CY - Eindhoven

    ER -

    van Houtum GJ, Adan IJBF, Wessels J, Zijm WHM. The equilibrium distribution for a class of multi-dimensional random walks. Eindhoven: Eindhoven University of Technology, 1994. 54 p. (COSOR Memorandum).