Array the 2-D Irregular Sample Space for 8-Direction Random Walk

A-2D-Random-Walk.md

A 2D Random Walk: Array the 2-D Irregular Sample Space for 8-Direction Random Walk

If the 2-D sample space is not regular, it may cause asymmetry in probability during a random walk. This algorithm rearranges the sample space to a new array with nRow rows and nCol columns.

How it Works

m = 2;
funcLogic = @(data1, data2) ((0 <= data1 + data2) & (data1 + data2 <= m));

Irregular sample space caused by the above condition:

(0, 3)
(0, 2) (1, 2)
(0, 1) (1, 1) (2, 1) 
(0, 0) (1, 0) (2, 0) (3, 0)

Permute the sample space in one dimension randomly, using getCellSampleSpace2dim.

(0, 2) (0, 3) (2, 0) (3, 0) (1, 1) (0, 0) (2, 1) (1, 0) (1, 2) (0, 1)

Arrange the sample space to an array with 2 rows and 3 columns, using arrangeSampleSpace2dim.

(0, 2) (0, 3) (2, 0) (3, 0) (1, 1) 
(0, 0) (2, 1) (1, 0) (1, 2) (0, 1)

Plot the Result in 3-D Histogram

The result using this algorithm. There is no obvious asymmetry except volatility caused by simulation.

The result using simple step-wise random walk. There is some obvious asymmetry. Besides, the result is affected by the initial position.

func.m

% Major Functions File for Array the 2-D Irregular Sample Space for 8-Direction Random Walk
% Author: Edward J. Xu, edxu96@outlook.com
% Date: 190616
% Version: 1.0
% ######################################################################################################################


function [cellSampleSpace] = getCellSampleSpace2dim(vecData1, vecData2, n1, n2, funcLogic)
    cellSampleSpace = {};
    for i = 1:n1
        for j = 1:n2
            if funcLogic(vecData1(i), vecData2(j))
                cellSampleSpace{end + 1} = [vecData1(i), vecData2(j)];
            end
        end
    end
    cellSampleSpace = cellSampleSpace(randperm(length(cellSampleSpace)));
end


function [cellArraySSpace] = arrangeSampleSpace2dim(cellSampleSpace, nRow)
    nCol = length(cellSampleSpace) / nRow;
    if mod(nCol, 1) ~= 0
        error("nRow is impossible!!!")
    end
    cellArraySSpace = {};
    k = 1;
    for i = 1:nRow
        for j = 1:nCol
            cellArraySSpace(i, j) = cellSampleSpace(k);
            k = k + 1;
        end
    end
end


function [vecCandidate] = loopRandWalk2Dim(cellArraySSpace, vecPre)
    [m, n] = size(cellArraySSpace);
    % Find where vecPre is
    where = 1;
    while ~isequal(cellArraySSpace{where}, vecPre)
        where = where + 1;
    end
    [x, y] = returnPosition(where, m, n);
    % disp(x)
    % disp(y)
    if cellArraySSpace{x, y} ~= cellArraySSpace{where}
        error("Error when trying to find where the x is.")
    end
    % Random Walk
    x = loopRandWalk(x, m, 1);
    y = loopRandWalk(y, n, 1);
    % disp(x)
    % disp(y)
    vecCandidate = [cellArraySSpace{x, y}];
end

test.m

% Test File for Array the 2-D Irregular Sample Space for 8-Direction Random Walk
% Author: Edward J. Xu, edxu96@outlook.com
% Date: 190616
% Version: 1.0
% ######################################################################################################################
testRandomWalk2dim()


function testRandomWalk2dim()
    m = 10;
    nRow = 6;
    nSample = 100000;
    vecData1 = [0:1:m];
    vecData2 = [0:1:m];
    n1 = length(vecData1);
    n2 = length(vecData2);
    funcLogic = @(data1, data2) ((0 <= data1 + data2) & (data1 + data2 <= m));
    % Get `cellArraySSpace`
    cellSampleSpace = getCellSampleSpace2dim(vecData1, vecData2, n1, n2, funcLogic);
    cellArraySSpace = arrangeSampleSpace2dim(cellSampleSpace, nRow);
    % Simulation
    sState_1(1).x = cellArraySSpace{randi(length(cellArraySSpace))};
    sState_2(1).x = cellArraySSpace{randi(length(cellArraySSpace))};
    for i = 2:nSample
        sState_1(i).x = loopRandWalk2dim(cellArraySSpace, sState_1(i - 1).x);
        sState_2(i).x = loopRandWalk2dimStepByStep(m, sState_2(i - 1).x);
    end
    % Plot the final result
    vecX1_1 = zeros(nSample, 1);
    vecX2_1 = zeros(nSample, 1);
    vecX1_2 = zeros(nSample, 1);
    vecX2_2 = zeros(nSample, 1);
    for i = 1:nSample
        vecX1_1(i) = sState_1(i).x(1);
        vecX2_1(i) = sState_1(i).x(2);
        vecX1_2(i) = sState_2(i).x(1);
        vecX2_2(i) = sState_2(i).x(2);
    end
    plotHistgram2dimRaw(vecX1_1, vecX2_1, m, 'RandWalk2dim_1');
    plotHistgram2dimRaw(vecX1_2, vecX2_2, m, 'RandWalk2dim_2');
end


function [x] = loopRandWalk2dimStepByStep(m, xPre)
    x1 = loopRandWalk(xPre(1), m, 0);
    x2 = loopRandWalk(xPre(2), m - x1, 0);
    x = [x1, x2];
end


function [ fig ] = plotHistgram2dimRaw(vecX1, vecX2, m, strFileName)
    % Plot the histogram of RNG result and return the vector of values
    fig = figure("Visible", "off");
    fig = histogram2(vecX1, vecX2, [-0.5:1:(m + 0.5)], [-0.5:1:(m + 0.5)], 'FaceColor', 'flat');
    saveas(fig, [pwd '/images/test/', strFileName, '.png']);
    saveas(fig, [pwd '/images/test/', strFileName, '.fig']);
end