Как рассчитать функцию вероятности массы случайной величины по модулю N, где N - простое число?

Question

Я пытаюсь решить следующую математическую задачу:

Рыцарь в стандартных международных шахматах сидит на доске следующим образом

0  1  2  3
4  5  6  7
8  9  10 11
12 13 14 15

Конь начинает с квадрата "0" и совершает прыжки на другие квадраты в соответствии с допустимыми ходами в шахматах (так, чтобы в каждом пространстве было от двух до четырех действительных ходов). Рыцарь выбирает среди допустимых ходов при каждом прыжке равномерно случайным образом и отслеживает текущую сумму S клавиш, на которые он приземляется.

а. Что означает среднее значение величины S после модуля T = 16 по модулю 13?

б. Что такое стандартное отклонение?

с. Что означает среднее значение величины S по модулю 311 после перемещения T = 512?

д. Что такое стандартное отклонение?

е. После перемещения T = 16, какова вероятность того, что сумма делится на 5, учитывая, что она делится на 13?

е. После перемещения T = 512, какова вероятность того, что сумма делится на 7, учитывая, что она делится на 43?

До сих пор я написал программу, которая вычисляет функцию вероятности массы (pmf) для S:

from itertools import chain, product
import numpy as np
import pytest


def index_to_grid(index):
    return index // 4, index % 4

def grid_to_index(i, j):
    return 4*i + j

def in_board(i, j):
    return (0 <= i < 4) and (0 <= j < 4)

def available_moves(index):
    pos = np.array(index_to_grid(index))
    knight_hops = [np.array(hop) for hop in chain(product([-2, 2], [-1, 1]), product([-1, 1], [-2, 2]))]
    return set(grid_to_index(*newpos) for newpos in pos + knight_hops if in_board(*newpos))

def transition_matrix():
    T = np.zeros((16, 16))
    for i in range(16):
        js = available_moves(i)
        for j in js:
            T[i, j] = 1/len(js)
    return T

def calculate_S(N):
    '''Calculate the matrix S(i, n) of the expected value of S given initial state i after n transitions'''
    T = transition_matrix()
    S = np.zeros((16, N+1))
    for i in range(16):
        S[i, 0] = i

    # Use a bottom-up dynamic programming approach
    for n in range(1, N+1):
        for i in range(16):
            S[i, n] = sum(T[i, j] * (i + S[j, n-1]) for j in range(16))
    return S

Вот несколько юнит-тестов, которые я использовал для проверки своих результатов:

def test_available_moves():
    assert available_moves(0) == {6, 9}
    assert available_moves(1) == {8, 10, 7}
    assert available_moves(10) == {4, 1, 12, 3}

def test_transition_matrix():
    T = transition_matrix()
    assert T[0, 6] == T[0, 9] == 1/2
    assert all(T[0, j] == 0 for j in set(range(16)) - {6, 9})
    assert T[1, 8] == T[1, 10] == T[1, 7] == 1/3
    assert all(T[1, j] == 0 for j in set(range(16)) - {8, 10, 7})
    assert T[10, 4] == T[10, 1] == T[10, 12] == T[10, 3] == 1/4
    assert all(T[10, j] == 0 for j in set(range(16)) - {4, 1, 12, 3})

def test_calculate_S():
    S = calculate_S(2)
    assert S[15, 1] == 15 + 1/2 * 6 + 1/2 * 9
    assert S[4, 1] == 4 + 1/3 * 2 + 1/3 * 10 + 1/3 * 13
    assert S[15, 2] == 15 + 1/2 * 9 + 1/2 * (1/4 * 0 + 1/4 * 2 + 1/4 * 7 + 1/4 * 15) \
                          + 1/2 * 6 + 1/2 * (1/4 * 0 + 1/4 * 8 + 1/4 * 13 + 1/4 * 15)


if __name__ == "__main__":
    pytest.main([__file__, "-s"])

Так, например, чтобы вычислить ожидаемое значение самого S после T = 16, я бы оценил calculate_S()[0, 16],

Проблема в том, что у меня возникают проблемы с обобщением этого значения до ожидаемого значения S % 13 (По модулю 13). Учитывая, что 13 (и все его "эквиваленты" в последующих вопросах) являются простыми числами, я подозреваю, что необходимо сделать ключевое наблюдение, используя "простоту", но до сих пор я не выяснил, что именно. Есть идеи?

Answer 1

Хитрость заключается в том, чтобы использовать динамическое программирование и выполнять все вычисления в некотором количестве. Для каждого шага вам нужна вероятность того, что он будет в каждом квадрате, с некоторой суммой, модом, некоторым числом.

Например, для задачи f вам нужно сделать мод расчета суммы 7*43 = 301, Таким образом, для каждого шага вам нужны шансы быть во всех 16*301 = 4816 возможные комбинации положения и бегущей суммы мод 301.

Это делает вашу необходимую матрицу перехода намного больше.