Популярно о науке

Previous Entry Share Next Entry
Решение задачки.
ahiin
Условие.

Правильный ответ:


Первым правильное решение предложил asg_rus, всего через час после публикации условия. Sic!


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

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

Очевидно, что матрица, удовлетворяющая условию задачи имеет вполне определенный вид:


Найдем ее собственные значения:

Так как матрица у нас вещественнозначная и симметричная, то для нее существует спектральное разложение:


Отсюда тривиально


Ну и


Более того, строки матрицы совпадают с собственными векторами матрицы . Если же эти вектора еще и ортонормировать, то добавится свойство ортогональности

Аккуратно проделав все выкладки, найдем, что


Окончательно:


  • 1

Другое решение?

Жаль, увидел задачу только сейчас.
Предлагаю другое решение.
1. А - не единичная матрица (это тривиальный случай в котором, кстати, 2 нулевых элемента, т.е. не строго положительны)
2. | det A| < 1
3. lim | det A^n | = lim ( | det A |^n )= 0
4. Строки (и столбцы) предельной матрицы (вырожденной) - совпадают и сумма эл-тов строки (столбца) = 1 ==> все эл-ты = 1/2

Re: Другое решение?

Первые три пункта - ок.
Не до конца ясно, откуда следует 4 (хотя постфактум - это верно).

Re: Другое решение?

Раскрываю последний пункт
Матрица (предельная) вырождена, значит строки линейно зависимы
Если первая строка ( а в ), то вторая - ( k*а k*в )
Сумма элементов = 1 (для обеих строк) значит k = 1
Обе строки - ( а в ), ( а в ).
Сумма элементов столбцов = 1 значит а = в = 1/2

Re: Другое решение?

Это-то понятно как раз.
>Сумма элементов = 1 (для обеих строк)
вот это откуда следует.

Re: Другое решение?

Блииин...
"Тарапыцца нада нэт"
В общем, кажется, я отдельно (только что) доказал, что для предельной матрицы этот факт имеет место быть (но 1 - еще себя не перепроверил; 2 - изящество из-за необходимости этого доказательства и его длины ушло напрочь). Так что свой коммент считаю неудачным.
Сорри.

Re: Другое решение?

Если вы в доказательстве используете другой подход, чем выше - то почему же. Будет интересно взглянуть на решение.

Re: Другое решение

Виноват, долго не отвечал - уезжал в безинтернетную зону...
Да, так вот, доказательство. Матрица А, симметричная, первая строка (а 1-а), в квадрате дает также симметричную матрицу с первой строкой (1+2*а*а-2*а 2*а-2*а*а). То есть, с тем же свойством сумма элементов строки (столбца)= 1.
Соответственно, и в любой четной степени (пардон, в степени вида 2^n) матрица А также будет обладать тем же свойством.
Значит и предельная - такая же (если предел существует, что тоже надо доказывать, разумеется).
Вроде бы так...
А за задачку (не только эту) - всё равно, спасибо.


Re: Другое решение

Да, это проходит. Но доказывать сходимость все равно придется.
Комбинируя решение, которое привел я, с вашим подходом, целиком получится следующее: не будет необходимости искать конкретный вид матрицы S. Зато потребуются рассуждения об определителе и об особых свойствах степени двойки.
PS. Поторопился чуток, да.

Edited at 2014-07-12 06:44 pm (UTC)

Доказательство сходимости

Итак,
1) для любой начальной А (заданного условием вида (а 1-а)) предельная матрица S существует (но, пока, если рассматривать предел не по всем натуральным n, а по степеням двойки)
2) Эта S состоит из 4-х элементов по 0.5.
3) Любая исходная матрица А при умножении на S даёт... S (проверяется умножением)
4) Если опять идти по степеням двойки, то А ^ (2^n) = S + [Нечто малое (n)]
5) Это [Нечто малое (n)] уходит в ноль при росте n
6) Соответственно, для промежуточных степеней матрицы А получаем
А ^ k = S + [Нечто малое (n)] * A ^ (k - 2^n)
7) Последняя добавка ( [Нечто малое (n)] * A ^ (k - 2^n) ) уходит в ноль при соответствующем уходе пары (k, n) в бесконечность. Последний тезис тоже можно (нужно) развить и обосновать подробней, но... надо ли... от исходно красивого доказательства и так почти ничего не осталось (в плане красоты)

  • 1
?

Log in

No account? Create an account