Teorie

Opakování teorie – Poissonův proces¶

Definice pomocí trajektorií¶

Buďte $\{X_j | j \in \mathbb{N}\}$ i.i.d., $X_j \sim \text{Exp}(\lambda)$ , rozestupy mezi událostmi. Definujme $\{T_n | n \in \mathbb{N}\}$ jako časy jednotlivých událostí, tj.

$T_0 := 0, \quad T_n := T_{n-1} + X_n = \sum_{j=1}^{n} X_j, \quad n \geq 1.$

Pak náhodný proces $\{N_t | t \in [0, +\infty)\}$ , kde $N_t$ je počet událostí do času $t$ , tj. $N_t(\omega) := \max\{n \in \mathbb{N}_0 | T_n(\omega) \leq t\}$ nazvu Poissonovým procesem s intenzitou $\lambda$ .

Definice pomocí přírůstků¶

Proces $\{N_t | t \in [0, +\infty)\}$ je Poissonův proces s intenzitou $\lambda$ , pokud

$N_0 = 0$ skoro jistě,
$N_t - N_s \sim \text{Poisson}(\lambda(t - s))$ pro všechna $t > s \geq 0$ ,
$\{N_t\}$ má nezávislé přírůstky, tj. $\forall k \in \mathbb{N}$ a pro všechny $0 \leq t_0 < t_1 < \ldots < t_k$ jsou $N_{t_1} - N_{t_0}, N_{t_2} - N_{t_1}, \ldots, N_{t_k} - N_{t_{k-1}}$ nezávislé.

Opakování teorie – markovský řetězec se spojitým časem¶

Definice¶

Náhodný proces $\{X_t | t \in [0, +\infty)\}$ s nejvýše spočetnou množinou stavů $S$ nazýváme markovský řetězec se spojitým časem, pokud platí markovská podmínka:

$\forall n \in \mathbb{N}, \forall \text{ časy } t > 0, 0 \leq s_0 < s_1 < \ldots < s_{n-1} < s \text{ a } \forall \text{ stavy } i_0, \ldots, i_{n-1}, i, j \in S \text{ platí } P(X_{s+t} = j | X_s = i, X_{s_{n-1}} = i_{n-1}, \ldots, X_{s_0} = i_0) = P(X_{s+t} = j | X_s = i).$

Homogenní markovský řetězec se spojitým č¶

asem

Markovský řetězec $\{X_t | t \geq 0\}$ nazvu homogenní, pokud

$\forall t, s > 0 \text{ a } \forall i, j \in S \text{ platí } P(X_{t+s} = j | X_s = i) = P(X_t = j | X_0 = i).$

Matice pravděpodobností přechodu mezi jednotlivými stavy za čas $t \geq 0$ ¶

$P(t) := \left(P(X_t = j | X_0 = i)\right)_{i,j \in S}, \text{ pak } p(t) = p(0) \cdot P(t).$

Matici skokových intenzit $Q = (Q_{ij})_{i,j \in S}$ definujeme jako

$Q := P'(0), \text{ tj. } Q_{ij} = P'_{ij}(0) = \left\{ \begin{array}{ll} \lim_{t \to 0+} \frac{P_{ii}(t) - 1}{t}, & \quad i = j, \\ \lim_{t \to 0+} \frac{P_{ij}(t)}{t}, & \quad i \neq j. \end{array} \right.$

Opakování teorie – Časování Poissonem¶

Uvažujme homogenní markovský řetězec $X_t$ se spojitým časem a maticí intenzit $Q$ . Vlastnosti prvků matice $Q$ : $Q_{ij} \geq 0$ pro $i \neq j$ , $Q_{ii} = - \sum_{j \neq i} Q_{ij} \leq 0$ . Předpokládejme, že existuje $\lambda_M \in (0, +\infty)$ tak, že $-Q_{ii} \leq \lambda_M$ pro každé $i \in S$ . Je-li $S$ konečná, volíme $\lambda_M = \max_{i \in S} -Q_{ii}$ . Pak existuje ekvivalentní vyjádření $X_t$ jako $X_t = Y_{N_t}$ , tj. $X_t(\omega) = Y_{N_t(\omega)}(\omega)$ , kde $\{N_t\}$ a $\{Y_n\}$ jsou nezávislé procesy splňující:

$\{N_t | t \geq 0\}$ je Poissonův proces s intenzitou $\lambda_M$ ,
$\{Y_n | n \in \mathbb{N}_0\}$ je markovský řetězec s diskrétním časem s maticí přechodu $D$ , $D = \frac{1}{\lambda_M}Q + I$ .

Toto vyjádření lze přímo použít k simulaci běhu řetězce $X_t$ .

Opakování teorie¶

Uvažujme homogenní markovský řetězec se spojitým časem $X_t$ a maticí intenzit $Q$ . Buď $\tau_i$ čas do výskoku ze stavu $i$ , tj. $X_{\tau_i} \neq i$ , $X_s = i$ pro $s \in [0, \tau_i)$ . Pak:

Čas do výskoku z $i$ je exponenciální s $\lambda_i = -Q_{ii}$ , tj. $\tau_i \sim \text{Exp}(-Q_{ii})$ .
Pravděpodobnost, že řetězec skočí z $i$ do $j$ je dána poměrem intenzit $Q_{ij}$ , tj. $P(X_{\tau_i} = j | X_0 = i) = \frac{Q_{ij}}{\lambda_i} = \frac{Q_{ij}}{-Q_{ii}} = \frac{Q_{ij}}{\sum_{k \neq i} Q_{ik}}$ .

Pro matice přechodu $P(t)$ platí Kolmogorova dopředná rovnice:

$P'(t) = P(t) \cdot Q \quad \Rightarrow \quad p'(t) = p(t) \cdot Q.$

Stacionární rozdělení $\pi$ , tj. $\pi \cdot P(t) = \pi$ pro všechna $t \geq 0$ ,

lze najít jako řešení rovnice $\pi \cdot Q = 0$ .

Detailní rovnováha (pokud platí, je $\pi$ stacionární): $\pi_j Q_{ji} = \pi_i Q_{ij}$ pro všechna $i, j \in S$ .

Opakování teorie – systémy hromadné obsluhy¶

Systém hromadné obsluhy M|M|1¶

Proces zrodu a zániku s $\lambda_n = \lambda$ a $\mu_m = \mu$ . Značíme $\rho := \frac{\lambda}{\mu}$ . Stacionární rozdělení existuje pro $\rho < 1$ , pak pro $n \in \mathbb{N}_0$ platí $\pi_n = (1 - \rho)\rho^n$ .

Střední počet zákazníků v systému: $E[N] \equiv E_{\pi}[X_t] = \frac{\rho}{1-\rho}$ .
Střední počet zákazníků na serveru: $E[N_s] = 1 - \pi_0 = \rho$ .
Střední počet zákazníků ve frontě: $E[N_f] = E[N] - E[N_s] = \frac{\rho}{1-\rho} - \rho = \frac{\rho^2}{1-\rho}$ .

Doba $W$ čekání zákazníka ve frontě:

$P(W = 0) = \pi_0 = 1 - \rho \quad \Rightarrow \quad P(W > 0) = 1 - \pi_0 = \rho,$

$P(W > s) = \rho e^{-(\mu-\lambda)s} \quad \text{a tedy} \quad (W|W > 0) \sim \text{Exp}(\mu - \lambda).$

Věta (Littleho věta)¶

Mějme striktně stacionární proces hromadné obsluhy. Buďte dále $E[N]$ - střední počet zákazníků v systému, $E[T]$ - střední doba strávená zákazníkem v systému, $\lambda$ - intenzita procesu příchodů. Pak $E[N] = \lambda \cdot E[T]$ .

Systém hromadné obsluhy M|M|∞¶

Proces zrodu a zániku s parametry $\lambda_n = \lambda$ a $\mu_m = \mu \cdot m$ . Stacionární rozdělení $\pi$ vždy existuje a jedná se o Poissonovo rozdělení s parametrem $\frac{\lambda}{\mu}$ , tj. pro $n \in \mathbb{N}_0$ :

$\pi_n = \frac{1}{n!}\left(\frac{\lambda}{\mu}\right)^n e^{-\frac{\lambda}{\mu}}.$

Systém hromadné obsluhy M|G|∞¶

Poissonovské příchody s intenzitou $\lambda$ . Obecné rozdělení (General distribution) času obsluhy se střední hodnotou $E[S]$ . Počet zákazníků v systému má z dlouhodobého pohledu ( $t \to +\infty$ ) Poissonovo rozdělení s parametrem $\lambda \cdot E[S]$ .