Листок 1

\[\newcommand{\st}{\, : \:} \newcommand{\ind}[1]{\mathbf{1}_{#1}} \newcommand{\dd}{\mathrm{d}}\]

Что разрешено делать:

Обсуждать задачи с одноклассниками.
Обращаться за помощью к преподавателю.
Использовать компьютер для линейных операций (например, умножение матриц, умножение матрицы на вектор и т.д.), при условии, что вы знаете, как делать это вручную.

Что вы обязаны делать:

Записывать решения самостоятельно.

Что запрещено делать:

Копировать записанные решения у одноклассника.
Использовать ИИ для получения решений.

Задачи

Упражнение 1 У Карла скучная жизнь. Он либо проводит час в инстаграме, либо час в TikTok, либо смотрит видео на Youtube о цепях Маркова в течение 5 минут, либо спит 25 минут.

Когда он просыпается, он всегда сначала проверяет Instagram.

Закончив проверять Instagram, он с равной вероятностью либо смотрит Youtube, либо проверяет Tiktok.

Когда он заканчивает с Youtube, он всегда ложится спать, потому что цепи Маркова — это скучно.

Когда он заканчивает с Tiktok, он с равной вероятностью либо проверит Instagram, либо пойдёт спать.

Представьте жизнь Карла в виде цепи Маркова, с матрицей переходных вероятностей (стохастической матрицей) и взвешенным графом.
Прямо сейчас Карл в Instagram. Найдите вероятность того, что десятым приложением, которое он откроет на своём телефоне, будет Instagram. Например, при рассмотрении переходов I-> Y -> S -> I, вторым открытым приложением является Instagram.
После многих лет такой увлекательной жизни, какой процент своего времени он проведёт в Instagram?

Решение

Матрица переходных вероятностей $P$ имеет вид (1: Instagram, 2: TikTok, 3: YouTube, 4: Сон) \[ P = \begin{pmatrix} 0 & 1/2 & 1/2 & 0 \\ 1/2 & 0 & 0 & 1/2 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \end{pmatrix} \] и вот соответствующий граф.

Рисунок 1: Жизнь Карла и след на подпространстве приложений. Каждое второе приложение, которое он использует, — это Instagram.

Жизнь Карла в приложениях — Рисунок 1: Жизнь Карла и след на подпространстве приложений. Каждое второе приложение, которое он использует, — это Instagram.

Каждое второе приложение, которое он открывает, — это Instagram, поэтому эта вероятность равна $1$.
Обозначим через $\mathcal{N}_x$ количество раз, которое Карл посещает состояние $x$ по прошествии многих лет, скажем, после $N$ шагов. Мы понимаем, что задача спрашивает о пределе при $N\to \infty$.

Пусть $\gamma_x=\mathbb{E}_x[\mathcal{N}_x]/N$ — ожидаемое количество раз, которое он находился в состоянии $x$. Тогда
- Ожидаемое количество посещений YouTube равно половине количества посещений Instagram с точностью до малой (случайной) ошибки: $\gamma_Y= \gamma_I/2+\varepsilon_{Y}$.
- Ожидаемое количество посещений TikTok также равно половине количества посещений Instagram с точностью до малой случайной ошибки: $\gamma_T= \gamma_I/2+\varepsilon_{T}$.
- Аналогично: $\gamma_S = \gamma_Y + \gamma_T/2 + \varepsilon_{S}$.
- Аналогично: $\gamma_I= \gamma_S + \gamma_T/2+\varepsilon_{I}$.
- Для решения не следует забывать: $\gamma_I+\gamma_Y+\gamma_T+\gamma_S=1$.
Здесь мы имеем в виду, что $\varepsilon_{x}$ — это некоторая малая ошибка порядка $O(1/N)$, которая возникает из-за того, что Карл начинает в определённом состоянии (Instagram). Так, например, при $N=1$ мы имеем $\gamma_I=1$, а все остальные равны $0$. Таким образом, мы получаем $\gamma_I=4/11+O(1/N)$, $\gamma_Y=2/11+O(1/N)$, $\gamma_T=2/11+O(1/N)$, $\gamma_S=3/11+O(1/N)$. Тогда доля времени, которую он проводит в Instagram, будет равна \[ \begin{aligned} \frac{\gamma_I *60+O(1/N)}{ \gamma_I*60+\gamma_Y*5+\gamma_T*60+\gamma_S*25+O(1/N)}\simeq 0.5393+O(1/N) \end{aligned} \tag{1}\] Таким образом, по прошествии многих лет ($N\to\infty$) он проведёт около 54% своей скучной жизни в Instagram.

В качестве более строгой альтернативы мы можем рассмотреть \[ \lim_{T\to \infty} \frac{1}{T}\sum_{t=0}^{T-1} f(X_t)=m(f) \] где $m$ — инвариантная мера процесса. Фактически, $m_x$ — это не что иное, как главный член вышеупомянутого $\gamma_x$, а именно $m_I=4/11$, $m_Y=m_T=2/11$, $m_S=3/11$. Теперь возьмём $f(x)$ как количество времени, которое он проводит каждый раз в состоянии $x$ (например, $f(I)=60$ минут и т.д.), и $g(x)=f(x) \mathbf{1}_{x=I}$. Тогда мы получаем \[ \lim_{T\to \infty} \frac{\sum_{t=0}^{T-1} g(X_t)}{\sum_{t=0}^{T-1} f(X_t)}=\frac{m(g)}{m(f)} \simeq 0.5393 \]

Упражнение 2 Анна только что получила $m$ велосипедов на свой день рождения. Теперь каждый день она будет случайным образом выбирать один велосипед (каждый с вероятностью $1/m$) и возвращаться вечером. Пусть $X_t$ — количество различных велосипедов, которые она использовала после $t$ дней (таким образом, $X_0=0$, $X_1=1$, но $X_2$ может быть $1$ или $2$).

Объясните, почему $(X_t)$ является цепью Маркова.
Пусть $\tau_m$ — случайное время, в которое она попробует все велосипеды. Является ли это моментом остановки?
Найдите вероятность $\mathbb{P}(\tau_m=t)$, помня, что $X_0=0$.

Решение

Вероятность того, что в данный день она воспользуется ранее не использованным велосипедом, зависит только от того, сколько велосипедов она уже использовала, а не от того, какие именно или в каком порядке она их использовала. Таким образом, это цепь Маркова с пространством состояний $S=\{0,\ldots,m\}$ и $p_{x,x}=x/m=1-p_{x,x+1}$ (конечно, $p_{m,m}=1$, поэтому $p_{m,m+1}$ просто не определено). Каждый синглтон пространства состояний является сообщающимся классом, причём $\{m\}$ — единственный замкнутый.
Это момент остановки. Фактически, это момент первого достижения $\{m\}$.
Мы имеем $\mathbb{P}_x(\tau_m=t)=\mathbb{P}_x(X_{t-1}=m-1,X_t=m)=p^{(t-1)}_{x,m-1}p_{m-1,m}$. $p_{m-1,m}=1/m$, поэтому нам просто нужно вычислить степень $p^{(t-1)}_{0,m-1}$. Матрица $P$ имеет собственные значения $\{0,1/m,2/m,\ldots,1-1/m,1\}$. Все они вещественны и просты, и назовём их $\lambda_x=x/m$. Тот факт, что $\lambda_x=x/m$, соответствует следующему замечанию¹: как только Анна использовала ровно $x$ велосипедов (например, если цепь начинается в состоянии $x$), она не будет использовать новый велосипед в течение ещё $t$ дней с вероятностью $\lambda_x^t$. Соответствующие левые собственные векторы $f^x P =\lambda_x f^x$ и правые собственные векторы $P e^x=\lambda_x e^x$ равны \[ \begin{aligned} & (e^x)_y= \binom{m-y}{x-y} \mathbf{1}_{y\le x} \\ & (f^x)_y=(-1)^y \binom{m-x}{y-x} \mathbf{1}_{y\ge x} \end{aligned} \] Таким образом, из линейной алгебры \[ (p^{(t)})_{x,y} = \sum_{z=0}^{m} \frac{(e^z)_x \, \lambda_z^t \, (f^z)_y}{e^z \cdot f^z} = \sum_{z=x}^y (-1)^{y-z} \binom{m-x}{z-x,y-z,m-y} \left(\frac{z}{m}\right)^t \] В частности \[ \mathbb{P}(\tau_m=t)=p^{(t-1)}_{0,m}/m = \sum_{z=0}^{m-1} (-1)^{m-z+1} \binom{m-1}{z} \left(\frac{z}{m}\right)^{t-1} \tag{2}\] Альтернативный метод использует принцип включения-исключения. Пусть $A_i$ — событие, состоящее в том, что велосипед $i$ не был использован к дню $t$. Сначала вычислим \[ \mathbb{P}(X_t=m) = 1 - \mathbb{P}\left(\cup_{i=1}^m A_i\right) \] По принципу включения-исключения: \[ \mathbb{P}\left(\bigcup_{i=1}^m A_i\right) = \sum_i \mathbb{P}(A_i) - \sum_{i<j} \mathbb{P}(A_i \cap A_j) + \cdots + (-1)^{m+1} \mathbb{P}(A_1 \cap \cdots \cap A_m) \] Вероятность не выбрать определённый набор из $k$ велосипедов за $t$ дней равна: $\mathbb{P}(A_{i_1} \cap \cdots \cap A_{i_k}) = (\tfrac{m-k}{m})^t$ Существует $\binom{m}{k}$ способов выбрать, какие $k$ велосипедов исключить. Подставляя это в формулу включения-исключения, получаем \[ \mathbb{P}(\tau_m=t)=\mathbb{P}(X_t=m)-\mathbb{P}(X_{t-1}=m) = \sum_{k=1}^m (-1)^{k} \binom{m}{k}\left((\tfrac{m-k}{m})^t-(\tfrac{m-k}{m})^{t-1}\right) \] что даёт тот же ответ, что и в Уравнение 2.

Вероятность в зависимости от числа состояний, для фиксированного времени — Рисунок 2: На графиках показана $\mathbb{P}(X_t=m)$ как функция от $m$ при фиксированном $t$ и, что более интересно, как функция от $t$ при фиксированном $m$. При больших $t$, $\mathbb{P}(X_t \neq m)\simeq (\lambda_{m-1})^t \simeq e^{-t/m}$. Мы видим этот факт, вычисляя $\tfrac{1}{t}\log \mathbb{P}(X_t\neq m)$. При больших $t$ это выражение сходится к своей асимптоте $\log(1-1/m)$. При малых $m$ сходимость к $0$ быстрее: когда вероятность становится очень малой, мы наблюдаем проблему машинной ошибки (странное поведение на синем графике), что напоминает о сложной задаче численного вычисления экспонент.

Вероятность в зависимости от времени, для фиксированного числа состояний — Рисунок 2: На графиках показана $\mathbb{P}(X_t=m)$ как функция от $m$ при фиксированном $t$ и, что более интересно, как функция от $t$ при фиксированном $m$. При больших $t$, $\mathbb{P}(X_t \neq m)\simeq (\lambda_{m-1})^t \simeq e^{-t/m}$. Мы видим этот факт, вычисляя $\tfrac{1}{t}\log \mathbb{P}(X_t\neq m)$. При больших $t$ это выражение сходится к своей асимптоте $\log(1-1/m)$. При малых $m$ сходимость к $0$ быстрее: когда вероятность становится очень малой, мы наблюдаем проблему машинной ошибки (странное поведение на синем графике), что напоминает о сложной задаче численного вычисления экспонент.

Упражнение 3 В теннисном матче два игрока, А и Б, играют на очки. Игрок А выигрывает очко с вероятностью $p$, а игрок Б — с вероятностью $1-p$. Игра заканчивается, когда один из игроков выиграл 4 очка в общей сложности и по крайней мере на 2 очка больше, чем соперник.

Смоделируйте игру как цепь Маркова на конечном пространстве состояний и представьте её в виде взвешенного графа.
Является ли это неразложимой цепью Маркова? Если нет, определите сообщающиеся классы и замкнутые из них.
Какова вероятность того, что игрок А выиграет игру?
Какова вероятность того, что игра продлится не более $5$ очков?

Теперь предположим, что у игрока А есть психологическое преимущество, и если очко решает исход игры, он выигрывает его с вероятностью $q > p$.

Какова теперь вероятность того, что игрок А выиграет игру?
(Необязательно) Проведите компьютерное моделирование для численной оценки результатов пунктов a. и b. для фиксированного значения $p$. Сравните результаты с теоретическими.

Решение

Хотя в принципе счёт очков может расти бесконечно, мы можем свести это к цепи с конечным числом состояний, отслеживая только преимущество игроков после того, как оба набрали по 3 очка. Именно так официально ведётся счёт в теннисных геймах, и это можно легко представить следующим ориентированным графом.

Рисунок 3

Каждое состояние, в котором хотя бы у одного из двух игроков не более 2 очков, является сообщающимся классом, состоящим из одного элемента (синглтоном). Действительно, такой счёт никогда не может быть достигнут снова. Каждое из двух состояний, в которых один из игроков выигрывает, является замкнутым сообщающимся классом. Наконец, три состояния: Ровно, Преимущество А и Преимущество Б — вместе образуют сообщающийся класс (однако не замкнутый).
Игра длится не более 5 очков, если она заканчивается ровно за 4 или 5 очков.
- Игра заканчивается за 4 очка с вероятностью $p^4 + (1-p)^4$ (вероятность траектории, где А всегда выигрывает, плюс та, где Б всегда выигрывает).
- Игра заканчивается ровно за 5 очков при следующих траекториях: А выигрывает 3 из первых 4 очков, а затем выигрывает последнее; или Б выигрывает 3 из первых 4 очков, а затем выигрывает последнее. Вероятность в этом случае равна $\binom{4}{1} p^4(1-p) +\binom{4}{1} p(1-p)^4$.
Искомая вероятность тогда равна $p^4 + (1-p)^4 + 4p^4(1-p) + 4p(1-p)^4$.
Пусть $a,b$ — состояния, в которых выигрывают А и Б соответственно, $i$ — начальное состояние со счётом $(0,0)$, а $d$ — состояние Ровно. Мы используем обозначения, введённые в лекциях: $h_x(y)$ — это вероятность достижения состояния $x$ при старте из $y$, а $h_{x,y}(z)$ — вероятность достичь $x$ раньше, чем $y$, при старте из $z$. Поскольку $\mathbb{P}(\tau_{\{a,b\}}<\infty)=1$, в принципе, мы можем просто определить $h_a(x)$ как вероятность выигрыша А при счёте $x$, решить линейную задачу для вероятностей достижения и найти требуемое $h_a(i)$.

Однако пространство состояний здесь довольно велико, поэтому давайте вычислим эту вероятность менее систематически. Событие, состоящее в том, что игрок А выигрывает игру, является объединением всех возможных траекторий, заканчивающихся в $a$. Существует два типа траекторий: те, в которых Б никогда не набирает 3 очка (так что состояние Ровно не достигается), и те, в которых достигается состояние Ровно.
- Вероятность выиграть, ни разу не достигнув состояния Ровно, равна сумме вероятностей всех таких траекторий: $h_{a,d}(i)=p^4+ \binom{4}{1} p^4(1-p)+ \binom{5}{2} p^4 (1-p)^2$ (существует одна траектория, где А выигрывает все очки, $\binom{4}{1}$ — где Б выигрывает 1 очко, а А выигрывает 4 очка, включая последнее, $\binom{5}{2}$ — где Б выигрывает 2 очка, а А выигрывает 4 очка, включая последнее).
- Вероятность достижения состояния Ровно равна $h_d(i) = \binom{6}{3} p^3 (1-p)^3$.
- Как только мы оказываемся в состоянии Ровно, мы можем забыть об остальном и решать гармоническую задачу с этого момента: если А выигрывает следующие два очка (вероятность $p^2$), А выигрывает игру. Если Б выигрывает следующие два очка (вероятность $(1-p)^2$), Б выигрывает игру. Если каждый из них выигрывает по одному очку (вероятность $2p(1-p)$), счёт возвращается к Ровно. Мы можем записать рекурсивное уравнение для $h_a(d)$: \[ h_a(d)= p^2+2p(1-p) h_a(d) \] или $h_a(d)=\frac{p^2}{p^2 + (1-p)^2}$.
- Вероятность достичь состояния Ровно и затем выиграть равна $h_d(i) h_a(d)$ (по сильному свойству Маркова).
Следовательно, вероятность выигрыша А равна \[ h_a(i)=h_{a,d}(i)+h_a(d) h_d(i)= p^4(1 + 4(1-p) + 10(1-p)^2) + 20 p^3(1-p)^3 \frac{p^2}{p^2 + (1-p)^2} \]
Здесь работает тот же подход, что и раньше, но, надеюсь, это решение нельзя найти в интернете! Давайте вычислим вероятность выигрыша А при этом новом условии.
- Вероятность выиграть, ни разу не достигнув состояния Ровно, равна $h_{a,d}(i)=[p^3]q + [p^3(1-q) + \binom{3}{1} p^3(1-p)]q+[p^3(1-q)^2 + \binom{3}{1} p^3(1-p)(1-q) + \binom{4}{2}p^3(1-p)^2]q$, где члены в квадратных скобках, умноженные на $q$, соответствуют вероятностям выигрыша за 4, 5 и 6 очков соответственно.
- Вероятность достижения состояния Ровно можно вычислить как \[ \begin{aligned} h_d(i) & = (1-q) h_{(3,2)}(i) + q h_{(2,3)} = (1-q)\left[p^3(1-q)^2 + \binom{3}{1} p^3(1-p)(1-q) + \binom{4}{2}p^3(1-p)^2\right] \\ & \qquad + q \left[(1-p)^3q^2 + \binom{3}{1} (1-p)^3p q + \binom{4}{2}(1-p)^3p^2 \right] \end{aligned} \]
- Вероятность выигрыша из состояния Ровно удовлетворяет уравнению \[ h_a(d)= p(q+(1-q)h_a(d))+(1-p)(q h_a(d)) \] или $h_a(d)=(p q)/(1-p-q+2p q)$.
В конечном счёте, вероятность выигрыша равна \[ h_a(i)= h_{a,d}(i)+h_a(d) \cdot h_d(i)= \tfrac{p q \left(-9 p^4 (q-1)-p^3 \left(q^2-24 q+23\right)+p^2 \left(2 q^3-2 q^2-15 q+15\right)-3 p (q-1) q^2+q^3\right)}{p (2 q-1)-q+1} \]

Эту задачу можно проще решить, просто используя решатель линейных систем (для гармонического уравнения), что даёт тот же ответ
Click to view the code
import sympy as sp # Declare sympy symbols p, q, h_d, h_a, h_b = sp.symbols('p q h_d h_a h_b') # Solve the deuce sub-problem in-line to get the win probability from deuce. h_deuce = sp.solve([ sp.Eq(h_d, p*h_a + (1-p)*h_b), sp.Eq(h_a, q + (1-q)*h_d), sp.Eq(h_b, q*h_d) ], (h_d, h_a, h_b))[h_d] # Define a recursive solver for the probability from any score (a,b). def prob(a, b): if a >= 4 and a >= b + 2: return 1 if b >= 4 and b >= a + 2: return 0 if a == 3 and b == 3: return h_deuce # Use 'q' on game points, otherwise 'p'. pt_prob = q if (a == 3 and b < 3) or (b == 3 and a < 3) else p return pt_prob * prob(a + 1, b) + (1 - pt_prob) * prob(a, b + 1) # Print the result from the initial score (0,0) result = sp.simplify(prob(0, 0)) print(f"""--- Probability of Player A Winning a Game --- [ LaTeX format ] {sp.latex(result)} [ Mathematica format ] {sp.mathematica_code(result)} [ Plain text format ] {result}""")
```
--- Probability of Player A Winning a Game ---

[ LaTeX format ]
\frac{p q \left(- 9 p^{4} q + 9 p^{4} - p^{3} q^{2} + 24 p^{3} q - 23 p^{3} + 2 p^{2} q^{3} - 2 p^{2} q^{2} - 15 p^{2} q + 15 p^{2} - 3 p q^{3} + 3 p q^{2} + q^{3}\right)}{2 p q - p - q + 1}

[ Mathematica format ]
p*q*(-9*p^4*q + 9*p^4 - p^3*q^2 + 24*p^3*q - 23*p^3 + 2*p^2*q^3 - 2*p^2*q^2 - 15*p^2*q + 15*p^2 - 3*p*q^3 + 3*p*q^2 + q^3)/(2*p*q - p - q + 1)

[ Plain text format ]
p*q*(-9*p**4*q + 9*p**4 - p**3*q**2 + 24*p**3*q - 23*p**3 + 2*p**2*q**3 - 2*p**2*q**2 - 15*p**2*q + 15*p**2 - 3*p*q**3 + 3*p*q**2 + q**3)/(2*p*q - p - q + 1)
```
Вот сравнение. Не стесняйтесь изменять размер окна и редактировать код.

#| '!! shinylive warning !!': |
#|   shinylive does not work in self-contained HTML documents.
#|   Please set `embed-resources: false` in your metadata.
#| standalone: true
#| components: [viewer, editor]
#| viewerHeight: 970
#| editorHeight: 120
#| layout: vertical
#| id: tennis

from shiny import App, render, ui, reactive, req
import matplotlib.pyplot as plt
import random
import theme

# ========= 1. UI DEFINITION =========
app_ui = theme.layout(
    ui.sidebar(
        ui.h4("Simulation Controls"),
        ui.input_slider(
            "p",
            "Player A's point win probability (p):",
            min=0.0, max=1.0, value=0.6, step=0.01
        ),
        ui.input_slider(
            "N",
            "Number of Games to Simulate (N):",
            min=100, max=20000, value=1000, step=100
        ),
        ui.input_action_button("run_simulation", "Run Simulation", class_="btn-success"),
        title="Tennis Game Simulation",
    ),
    
    ui.output_ui("results_display"),
    ui.output_plot("game_length_plot", height="500px"),
    title="Tennis Game Markov Chain Simulation",
)

# ========= 2. SERVER LOGIC =========
def server(input, output, session):
    theme.setup_plot_style()
    # This reactive value holds the simulation results.
    simulation_results = reactive.Value(None)

    def simulate_one_game(p):
        """Simulates a single game of tennis and returns the winner and duration."""
        score_a, score_b = 0, 0
        points_played = 0
        while True:
            points_played += 1
            if random.random() < p:
                score_a += 1
            else:
                score_b += 1

            # Check for win condition
            if score_a >= 4 and score_a >= score_b + 2:
                return 'A', points_played
            if score_b >= 4 and score_b >= score_a + 2:
                return 'B', points_played

    def calculate_theoretical_probs(p):
        """Calculates the theoretical probabilities based on the solution formulas."""
        # Probability the game lasts not more than 5 points
        prob_le_5_points = (p**4 + (1-p)**4) + (4 * p**4 * (1-p) + 4 * p * (1-p)**4)

        # Probability Player A wins
        prob_a_wins_no_deuce = p**4 + 4 * p**4 * (1-p) + 10 * p**4 * (1-p)**2
        prob_deuce = 20 * (p**3) * ((1-p)**3)
        prob_a_wins_from_deuce = (p**2) / (p**2 + (1-p)**2) if (p**2 + (1-p)**2) > 0 else 0
        prob_a_wins_total = prob_a_wins_no_deuce + prob_deuce * prob_a_wins_from_deuce

        return {
            "prob_a_wins": prob_a_wins_total,
            "prob_le_5_points": prob_le_5_points
        }

    @reactive.Effect
    @reactive.event(input.run_simulation, ignore_init=True)
    def _():
        """This function runs ONLY when the run_simulation button is clicked."""
        p = input.p()
        N = input.N()

        wins_a = 0
        short_games = 0
        game_lengths = []

        for _ in range(N):
            winner, length = simulate_one_game(p)
            if winner == 'A':
                wins_a += 1
            if length <= 5:
                short_games += 1
            game_lengths.append(length)

        sim_prob_a_wins = wins_a / N
        sim_prob_le_5 = short_games / N

        theoretical = calculate_theoretical_probs(p)

        simulation_results.set({
            "sim_prob_a_wins": sim_prob_a_wins,
            "sim_prob_le_5": sim_prob_le_5,
            "theo_prob_a_wins": theoretical["prob_a_wins"],
            "theo_prob_le_5": theoretical["prob_le_5_points"],
            "game_lengths": game_lengths,
            "N": N
        })

    @output
    @render.ui
    def results_display():
        results = simulation_results.get()
        if not results:
            return ui.p("Click 'Run Simulation' to see the results.", class_="text-center")

        return ui.div(
            ui.h4("Comparison of Results"),
            ui.div(
                ui.div(
                    ui.h5("Probability A Wins"),
                    ui.p(f"Theoretical: {results['theo_prob_a_wins']:.4f}"),
                    ui.p(f"Simulated: {results['sim_prob_a_wins']:.4f}"),
                    class_="card-body"
                ),
                class_="card bg-light mb-3"
            ),
            ui.div(
                ui.div(
                    ui.h5("Probability Game Lasts ≤ 5 Points"),
                    ui.p(f"Theoretical: {results['theo_prob_le_5']:.4f}"),
                    ui.p(f"Simulated: {results['sim_prob_le_5']:.4f}"),
                    class_="card-body"
                ),
                class_="card bg-light mb-3"
            ),
        )

    @output
    @render.plot
    def game_length_plot():
        results = simulation_results.get()
        req(results)

        game_lengths = results["game_lengths"]
        N = results["N"]

        fig, ax = plt.subplots(figsize=(8.5, 6))

        # Calculate discrete bins for the histogram 
        max_len = 0
        if game_lengths:
            max_len = max(game_lengths)
            # Create bin edges like [3.5, 4.5, 5.5, ...]
            bins = [i + 0.5 for i in range(3, max_len + 2)]
        else:
            bins = [i + 0.5 for i in range(3, 10)]

        ax.hist(game_lengths, bins=bins, rwidth=0.8, align='mid', color='royalblue', alpha=0.7)
        # Set x-axis ticks using a standard range
        ax.set_xticks(range(4, (max_len if game_lengths else 9) + 2))
        ax.set_xlabel("Total Points in Game", fontsize=12)
        ax.set_ylabel("Frequency", fontsize=12)
        ax.set_title(f"Distribution of Game Lengths over {N} Simulations", fontsize=14)
        ax.grid(True, linestyle='--', alpha=0.5)

        return fig

# ========= 3. APP INSTANTIATION =========
app = App(app_ui, server)


## file: theme.py
from shiny import ui
import matplotlib.pyplot as plt

def layout(sidebar, *args, **kwargs):
    """
    Standard layout wrapper for all Shinylive apps.
    
    Args:
        sidebar: A ui.sidebar() object.
        *args: Main content elements.
        **kwargs: Additional arguments for ui.page_sidebar (e.g., title, fillable).
    """
    return ui.page_sidebar(
        sidebar,
        # Standard CSS across all apps
        ui.tags.style("""
            :root {
                --bs-body-font-family: "Source Sans 3", sans-serif;
                --bs-font-monospace: "Source Code Pro", monospace;
            }
            body { 
                font-family: var(--bs-body-font-family) !important; 
            }
            .bslib-sidebar-layout .sidebar-content { 
                font-size: 14px; 
            }
            /* Ensure plots blend in if needed */
            .shiny-plot-output {
                background-color: transparent;
            }
        """),
        *args,
        **kwargs
    )

def setup_plot_style():
    """
    Configures Matplotlib to match the web theme (Source Sans 3).
    Call this at the top of your server function or global scope.
    """
    # Attempt to use Source Sans Pro/3 if available, else fallback to sans-serif
    plt.rcParams.update({
        "font.family": "sans-serif",
        "font.sans-serif": ["Source Sans 3", "Source Sans Pro", "DejaVu Sans", "sans-serif"],
        "axes.titlesize": 13,
        "axes.labelsize": 11,
        "xtick.labelsize": 10,
        "ytick.labelsize": 10,
        "figure.figsize": (8, 5),
        "axes.grid": True,
        "grid.alpha": 0.3,
        "grid.linestyle": ":",
        # Transparent backgrounds to match web theme
        "figure.facecolor": "none",
        "axes.facecolor": "none",
        "savefig.facecolor": "none"
    })

Упражнение 4 Мы хотим дать аналитическую характеристику переходных вероятностей $q_{x,y}$ следа рекуррентной цепи Маркова. Мы доказали, что след $\mathbf{X}$ на $A$ имеет переходные вероятности \[ q_{x,y}=\mathbb{P}_x(X_{\tau^+_A}=y) \] Определим оператор $P^{(A)}$ с элементами \[ p^{(A)}_{x,y}= \begin{cases} p_{x,y} & \text{if $y\in A$} \\ 0 & \text{if $y\notin A$} \end{cases} \] Докажите, что для каждого фиксированного $y\in A$, $q_{x,y}$ является минимальным решением задачи для неизвестной $h \ge 0$ \[ ((I-P^{(A^c)}) h)(x) = p_{x,y}, \qquad x\in S \tag{3}\] означает $q_{x,y} - \sum_{z \notin A} p_{x,z} q_{z,y} = p_{x,y}$ для всех $x\in A$.

Решение

Зафиксируем $y \in A$ и обозначим $h(x) \equiv q_{x,y}= \mathbb{P}_x(X_{\tau_A^+} = y)$ для $x\in S$. Обусловливая по первому шагу: \[ h(x) = \sum_{z \in S} p_{x,z} \mathbb{P}_x(X_{\tau_A^+}=y | X_1=z) = \sum_{z\in A} p_{x,z} \mathbf{1}_{y=z}+\sum_{z\notin A} p_{x,z} h(z)= p_{x,y}+\sum_{z\notin A} p_{x,z} h(z) \]

Чтобы доказать минимальность, пусть теперь $g \ge 0$ — любое неотрицательное решение системы Уравнение 3 для фиксированного $y\in A$ (которое мы опускаем в обозначениях). Определим $h^{(n)}(x):= \mathbb{P}_x(X_{\tau_A^+} = y, \tau_A^+\le n)$. Тогда $h^{(n)}(x) \le q_{x,y}$, и по свойству непрерывности вероятности на монотонных последовательностях, $h^{(n)}(x) \uparrow h(x)$. Следовательно, достаточно проверить, что $g\ge h^{(n)}$ для всех $n\ge 0$. Теперь докажем по индукции.

Тривиально, $g\ge h^{(0)}\equiv 0$.
$h^{(n)}$ удовлетворяет (рассуждая как для $q_{\cdot,y}$ выше) \[ h^{(n+1)}(x)=p_{x,y}+\sum_{z\notin A} p_{x,z} h^{(n)}(z) \] Следовательно, по индукционному предположению \[ g(x)= p_{x,y}+(P^{(A^c)}g)(x) \ge p_{x,y}+(P^{(A^c)}h^{(n)})(x) = h^{(n+1)}(x) \]

Сноски

Можно проверить, что если $p^{(t)}_{x,x}=\lambda^t$ для некоторого $x\in S$, $\lambda \in [0,1]$ и всех $t\in \mathbb{N}$, то $\lambda$ является собственным значением $P$.↩︎