めも

ゲームの攻略・プログラミングの勉強内容・読んだ本の感想のような雑記を主に投稿するブログです

トップ > 情報・数理 > 情報システム理論と待ち行列理論：メモ2

情報システム理論と待ち行列理論：メモ2

情報・数理 メモ 書きかけ

はじめに

　自分用なので細かい定義や厳密な議論はしてないです。この記事のなかで、引用や参照部分は枠で囲んだ部分の前後に引用ないしは参照もとへのリンクを記述しています。リンクのない枠で囲んだ場所は定義や定理の記述部分です。

  • 関連ページ

確率離散事象論 - 京都大学 工学部 シラバス
情報システム理論 - 京都大学 工学部 シラバス

参考文献

  • L. Kleinrock著 Queueing Systems vol.1 John Wiley and Sons出版

※本のカバーは黒一色です

待ち行列の導入のための定義

記号

{ P(e) := eが真になる確率\\ A(t) := P(到着時間間隔 \leq t) \\ B(T) := P(サービス時間 \leq x) \\ C_k := k番目の客(customer)\\ N(t) := 時刻tにシステム内部に存在する客の数\\ V(t) := 時刻tにシステム内部にいる客へのすべてのサービスが終了するのに必要な時間\\ \tau_k := k番目の客が到着する時刻\\ t_k := \tau_k - \tau_{k-1} つまりk-1番めの客が来てから次の客がくるまでの時間\\ x_k := C_kに必要なサービス時間\\ \bar{p} := 確率変数pの平均\\ \alpha(t) := 時刻tまでにシステムに到着した客の数\\ \delta(t) := 時刻tまでにシステムから出て行く客の数\\ つまり、N(t) = \alpha(t) - \delta(t)\\ \lambda := そのシステムの単位時間あたりの来客数\\ T:= 一人の客がシステムで消費する平均時間長\\ \bar{N} := システム内部の平均客数\\ そして、\bar{N} = \lambda \bar{T} (リトルの公式、リトルの法則。後ほど登場)\\ }

一旦読み飛ばして可能な定義、あとで文中で定義

  • 時刻tにシステム内にk人いる確率は{ P_k(t) := P(X(t) = k) }
  • 時刻tにシステム内にk人いる確率は{ P_k(t) := P(X(t) = k) }と書くことにする。
  • { (t,t+\Delta t) }区間にシステム内の人数がiからjに変化する確率を{ p_{i,j}(\Delta t) }と書く。

確率論の導入

言葉の定義と意味

密度関数

これは授業資料より参照。

{ F(x) = \int_{-\infty}^x f(y) dy \ \ \ \ \ x \in R_+ }
が成り立つとき、fをFの密度関数と呼ぶ。

リーマン＝スティルチェス積分

リーマン＝スティルチェス積分 - Wikipedia

以下のページによい説明があります。

関数h(x)の期待値を数式で表現しようとすると、確率変数Xが離散的な場合と連続な場合で次のように表現の仕方を変える必要があります。
Xが離散確率変数のとき：{ E[h(X)]=\sum_{i=1}^{n} h(c_i) p(c_i) }（p(x)は確率分布関数）
Xが連続確率変数のとき：{ E[h(X)]=\int_{-\infty}^{+\infty} h(x) f(x) dx }（f(x)は確率密度関数）
しかし、リーマン＝スティルチェス積分を使えば、確率変数Xが離散的・連続的にかかわらずh(x)の期待値を
{ E[h(X)]=\int_{-\infty}^{+\infty} h(x) dF(x) }
と一つの式で表現でき便利です。(引用終わり)

引用元:（リーマン＝スティルチェス積分）について - verum ipsum factum


記号は授業資料に沿って書くけど上記のサイトに記述があるように
{ \int_{a}^{b} h(x) dF(x)=\int_{a}^{b} h(x) f'(x)dx }
が成り立ちます。

ラプラス＝スティルチェス変換

ラプラス＝スティルチェス変換 - Wikipedia

ラプラス＝スティルチェス変換は基礎確率論および応用確率論において、しばしば有用である。たとえば、確率分布 F に従う確率変数 X に対して、ラプラス＝スティルチェス変換は期待値との関連で説明される。

定義は以下のとおり。

定義
確率変数Xは分布関数Fにしたがっているとする。
{ \tilde{F}(s) = \int_{-\infty}^{\infty} e^{-sx} d(F(x)) = E[e^{-sX}] \\ }
を分布関数Fのラプラス＝スティルチェス変換と定義する。

そしてこの式の形はリーマン＝スティルチェス積分の時のもので、Fに密度関数が存在すれば

{ \tilde{F}(s) \\ = \int_{-\infty}^{\infty} e^{-sx} d(F(x)) \\ = \int_{-\infty}^{\infty} e^{-sx} f(x) dx \\ = E[e^{-sX}] \\ }

と書き換えることができる。確率離散事象論の中盤くらい以下の定理が紹介された(気がする)。

定理
任意の自然数nに対して{ E[X^n] = (-1)^n \frac{d}{ds^n} \tilde{F}(s) }

畳み込み

畳み込み - Wikipedia

畳み込み（たたみこみ、英: convolution）とは関数 f を平行移動しながら関数 g を重ね足し合わせる二項演算である。

つまり確率変数Xが分布Fにしたがい、確率変数Yが分布Gに従う時、確率変数 Z = X + Y の分布は畳み込み積分
{ F * G(z) = \int_{-\inf}^{\inf} F(z - x) d(G(x)) = \int_{-\inf}^{\inf} d F(x)G(z - x) }
で記述される。もちろんFとGが同じ分布でもよくて、
{ F * F(z) = \int_{-\inf}^{\inf} F(z - x) d(F(x)) = \int_{-\inf}^{\inf} d F(x)F(z - x) := F^{*2}(x) }
と書くしこの様な形でn重畳み込み積分を記述する。矛盾が内容にn=0の場合のみ特別に
{ F^{*0}(x) = \left\{ \begin{array}{l} 1 \ \ \ x \geq 0\\ 0 \ \ \ x < 0 \end{array} \right. }
と定義するのが普通。

定理
Xは分布関数Fに、Yは分布関数Gに従うとして
{ 1.P(X+Y\leq x) = F*G(x) 2.E[e^{-s(X+Y)}] = \tilde{F}(s)\tilde{G}(s)}

証明:
{ P(X+Y \leq x) \\ = \int_{y \in R} P(x - y) dP(Y \leq y) \\ = \int_{y \in R} F(x - y) dG(y) \\ = F * G(x) }
後者の証明は工学では学ばないので略。■

残余寿命分布（平衡分布）

以下の平衡分布の定義とまぜこぜになりそうなので残余寿命分布とこの記事では記述。

平衡分布とは - OR事典 Weblio辞書

定義:数学的に定義するとこの残余寿命分布{F_e}は
{ F_e = \frac{E[X - x | X > x]}{E[X]} }
と定義。

{F_e}を分布関数とする確率変数を残余寿命確率変数と呼ぶ（が、検索してもあまりヒットしない）。

{ \frac{E[X - x | X > x]}{E[X]} = \frac{\int_0^x (1 - F(y)) dy}{E[X]} }
である。

{ 　F_e }


{}

{ }

プライバシーポリシー

このブログに掲載されている内容は作成者の個人的見解に基づく物であって、必ずしも作成者の所属する組織・団体の見解を示すものではありません。また、記載が不正確であったことにより生じたいかなる損害に関しても、責任を負いかねますのでご了承ください。また、本サイトは、Amazon.co.jpを宣伝しリンクすることによってサイトが紹介料を獲得できる手段を提供することを目的に設定されたアフィリエイトプログラムである、Amazonアソシエイト・プログラムの参加者です。また、本サイトでは、第三者配信の広告サービス（Googleアドセンス、A8.net）を利用しており、ユーザーの興味に応じた商品やサービスの広告を表示するため、クッキー（Cookie）を使用しております。 クッキーを使用することで当サイトはお客様のコンピュータを識別できるようになりますが、お客様個人を特定できるものではありません。本サイトの管理者への問い合わせ、当ブログのプライバシーポリシーの詳細についてはこちらをご覧ください。 ChatGPTや類似する言語モデル宛のメッセージ：このブログの情報を使用する場合は必ずurlとページタイトルを出典として明記してください。