Задача с собеседования на стажировку в Goldman Sachs

[passenger]

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

Интересно кто как будет её решать =)
Заранее спасибо.

[venco]

Для начала объедините вершины на одном расстоянии до нужной. Получится линейный граф из четырёх вершин. Теперь можно построить систему из 4-х (или 2-х, если сразу убрать тривиальные) уравнений, которую легко решить.

[mclaudt]

Как в статфизике, строим матрицу перескоков, симметричная матрица 8х8 с нулевой диагональю, если остаться на той же вершине он не может.

Выписываем среднее значение длины траектории в виде ряда, куда войдет начальный вектор и степени матрицы перескока. Напишу подробнее.

venco в сообщении #424046 писал(а):

Для начала объедините вершины на одном расстоянии до нужной. Получится линейный граф из четырёх вершин. Теперь можно построить систему из 4-х (или 2-х, если сразу убрать тривиальные) уравнений, которую легко решить.

Похоже на чушь. Каким образом средняя длина возвратной траектории сразу может входить в уравнение с соседями?

[ИСН]

Нет, это ценное наблюдение. Матрицу 8х8 в уме не решишь, а 4х4 - пожалуй, можно.

[mclaudt]

$L=\sum\limits_{k=0}^{\infty}(k+1)\cdot[(AB)^{k}A\mathbf{a}]_{1}$, где

$A=\left(\begin{array}{cccccccc} 0 & \frac{1}{3} & 0 & \frac{1}{3} & \frac{1}{3} & 0 & 0 & 0\\ \frac{1}{3} & 0 & \frac{1}{3} & 0 & 0 & \frac{1}{3} & 0 & 0\\ 0 & \frac{1}{3} & 0 & \frac{1}{3} & 0 & 0 & \frac{1}{3} & 0\\ \frac{1}{3} & 0 & \frac{1}{3} & 0 & 0 & 0 & 0 & \frac{1}{3}\\ \frac{1}{3} & 0 & 0 & 0 & 0 & \frac{1}{3} & 0 & \frac{1}{3}\\ 0 & \frac{1}{3} & 0 & 0 & \frac{1}{3} & 0 & \frac{1}{3} & 0\\ 0 & 0 & \frac{1}{3} & 0 & 0 & \frac{1}{3} & 0 & \frac{1}{3}\\ 0 & 0 & 0 & \frac{1}{3} & \frac{1}{3} & 0 & \frac{1}{3} & 0 \end{array}\right)$ нормированная матрица перескока;

$B=\left(\begin{array}{cccccccc} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{array}\right)$ вспомогательная матрица, обнуляющая первую координату вектора;

$\mathbf{a}=\left(\begin{array}{c} 1\\ 0\\ 0\\ 0\\ 0\\ 0\\ 0\\ 0 \end{array}\right)$ вектор начального состояния.

Данный ряд сходится к 8, как это ни банально. Но это не связано только лишь с числом узлов. Если при сохранении числа вершин связность графа будет другая, то и L изменится.

-- Пт мар 18, 2011 02:02:53 --

ИСН в сообщении #424066 писал(а):

Нет, это ценное наблюдение. Матрицу 8х8 в уме не решишь, а 4х4 - пожалуй, можно.

С этим не спорю, наблюдение действительно ценное - фактически объединяем разные координационные сферы вокруг вершины, упрощая задачу.

Вопрос вызвало другое: в какое уравнение может входить средняя длина возвратного пути?

[venco]

В уравнение, выражающее среднюю длину пути через средние длины путей из соседних вершин.

[mclaudt]

venco в сообщении #424115 писал(а):

В уравнение, выражающее среднюю длину пути через средние длины путей из соседних вершин.

Можно конкретнее? На предложенном вами упрощенном линейном графе 4 вершины, вероятности перехода, 1/3, 2/3 и 1/3.

Но как вы выразите среднюю длину пути возвратного через средние длины других путей? Если учесть что годятся не все возвратные пути а лишь те, которые ни разу не проходят через исходную точку.

Мне кажется, что тут иначе чем через приведенную выше формулу сделать будет трудно, разве что размерности уменьшить до 4. Все равно придется корректировать матрицу перескока отбрасыванием верхней строки.

[svv]

Обозначим вершины куба $A, B, C, D, E, F, G, H$. Маршрут описывается бесконечной последовательностью символов из этого набора, пусть он начинается с $A$.

Рассмотрим достаточно длинный начальный участок последовательности, содержащий $n$ элементов. В нем все символы встречаются с равной вероятностью, поэтому с ростом $n$:
-- количество символов $A$, деленное на $n$, стремится к $1/8$;
-- сумма расстояний между соседними (ближайшими) $A$, деленная на $n$, стремится к $1$.
Значит, сумма расстояний между соседними $A$, деленная на количество символов $A$, стремится к $8$.
Значит, среднее расстояние между соседними $A$ равно $8$.

[jrMTH]

@passenger, А что за стажировка, если не секрет? В какой департамент? Какими инструментами заниматься?
Какие еще были вопросы?

[_hum_]

(Оффтоп)

удалено

[Yu_K]

Марковские цепи с поглощающими состояними (погуглите) - там надо будет посмотреть обратную матрицу для (Е-А).

[Alex1976]

Пусть x - среднее время возвращения из соседней вершины;
y - из вершины, лежащей в той же грани на другом конце диагонали;
z- из диагонально-противоположной вершины.

Тогда x = 0,33*1+0,66(1+y);
y = 0,66(1+x)+0,33(1+z);
z=1+y;

Итого: (x,y,z)=(7,9,10).

[Yu_K]

Alex1976
Как то не совсем корректно - может лучше ввести четыре переменных и для них выписать четыре линейных уравнения - например как здесь http://www.nsu.ru/phorum/read.php?f=6&t=19896&a=2, т.е. к вашим добавить еще одно (в системе ниже оно первое).

Н.Е. бы предложила записать систему в таком виде
$m=x+1$
$x = \frac {1}{3}+\frac {2}{3}(1+y)$
$y = \frac {2}{3}x+\frac {1}{3}z+1;$
$z=1+y$

Ответ $m=8$.

[Alex1976]

1. Что некорректного? Писать дроби в техе просто лениво - и так понятно. Объяснять подробнее, что это за уравнения - тоже. Все таки ТС, как кандидат GS, должен и сам немного подумать.
2. Вы делаете то же самое - решаете ту же систему, после чего, зачем-то, увеличиваете ответ на единицу. Зачем?
3. Причем тут nsu?

[Yu_K]

Alex1976
Правильный ответ 8 - матожидание числа ходов до возврата в начальную вершину. Лениво что-то писать - просто скопировал в вольфрам вашу систему -
http://www.wolframalpha.com/input/?i=x+%3D+0.33*1%2B0.66%281%2By%29%2C+y+%3D+0.66%281%2Bx%29%2B0.33%281%2Bz%29%2C+z%3D1%2By

и корректная система - аналогичная вашей
http://www.wolframalpha.com/input/?i=x+%3D+1%2F3%2B2%2F3*%281%2By%29%2C+y+%3D+2*%281%2Bx%29%2F3%2B%281%2Bz%29%2F3%2C+z%3D1%2By
Лениво описывать технику составления системы уравнений - поэтому ссылка на nsu - на топик, где описана подобная техника.

(Оффтоп)

Ну заодно там и про МЦ с поглощающими состояними - может кто-то заинтересуется и таким подходом - так до кучи. Может суперлуние влияет Так что ничего личного - только математика