Шахматная доска

[Scully-Wolf]

Методом имитационного моделирования определить математическое ожидание количества шагов, необходимых путнику, чтобы добраться из точки $A$ в точку $B$, если на каждом шаге выбор направления равновероятен. Возможные расположения точек находятся в квадрате $5\times 5$ (всего $25$ точек). $A=20 \ B=13$

01 02 03 04 05
06 07 08 09 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25

[Shadow]

Мне этот метод неизвестен, но...кое-что нужно уточнить. Путник не выходит из решетки, движется вверх-вниз-налево-направо (если имеет возможность, но не по диагонали) В любой момент все допустимые направления равновероятны? Тогда
$X_{12}=\frac 1 3 (1+X_{22})+\frac 1 3 (1+X_{03})+\frac 1 3 (1+X_{11})$
...
Получится системма уравнений

[_Ivana]

У меня смутные подозрения, что метод может заключаться в написании программы, проведении серии экспериментов и оценки матожидания.

[Shadow]

Нееет, линейная системма из 5-ти уравнений с 5 неизвестными. $X_{01},X_{02},X_{11},X_{12},X_{22}$
Нужно найти $X_{12}$

[Yu_K]

Shadow
Что маловато уравнений - с учетом симметрии неизвестных будет 15.

Scully-Wolf
Если нужно точно посчитать - то погуглите марковские цепи с поглощающими состояниями - там подобные задачи разобраны. Придется матрицу обращать размером около $24\cdot24$.

И если речь идет об имитационном моделировании - то похоже нужно просто написать программу для случайных блужданий и считать число шагов до прихода в нужное поле. Пару миллионов таких расчетов позволит дать оценку матожидания.

[Deggial]

Scully-Wolf, формулы оформляйте $\TeX$ом. Инструкции по оформлению формул здесь или здесь (или в этом видеоролике).
Пока формулы поправил, а потом буду переносить неоформленные темы в Карантин.

[Shadow]

Yu_K Именно с учетом симетрии уравнений будет 5. Есть 5 разных позиций относительно центра

E D C D E
D B A B D
C A * A C
D B A B D
E D C D E

С учетом что $E=1+D$ даже 4.
(из ячейки E можно попасть только в D)

[Scully-Wolf]

Да, мне вот уточнили, что это нужно промоделировать с Scilab, и посчитать вероятность попадания и одной точки в другую с помощью метода Монте-Карло. Да , за пределы доски он не выходит и по диагонали двигаться не может. каждый его ход случаен и в любую сторону. Я просто не знаю с чего начать и пытаюсь понять примерный алгоритм решения этой задачи, как примерно запрограммировать чтобы он перемещался случайно в любую сторону. но не по диагонали и т.п.

[Shadow]

Монте Карло говорите? Хорошо, я по своему, заодно потом проверим
$\\A=\frac 1 4+\frac 1 2(1+B)+\frac 1 4(1+C)\\ \\ B=\frac 1 2(1+A)+\frac 1 2(1+D)\\ \\ C=\frac 1 3(1+A)+\frac 2 3(1+D)\\ \\ D=\frac 1 3(1+B)+\frac 1 3(1+C)+\frac 1 3(1+E)\\ \\ E=1+D$


$\\A=19\\ B=23.6\\ C=24.8\\ D=26.2\\ E=27.2$

[Yu_K]

Действительно при этих конкретных начальной и конечной точке получается всего пять уравнений - если бы искали МО длины траектории выходящей из угла и туда же возвращающейся - то было бы уранений побольше.

Ну а про Монте Карло - используйте датчики случайных чисел и выбирайте направление - для внутренних клеток четыре возможных направления - если взять случайное число от 0 до 1 - то каждому направлению сопоставьте одну четвёртую долю единичного отрезка. Для граници углов будут свои процедуры выбора направления.

[_Ivana]

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