一様性とは？ わかりやすく解説

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/03/30 19:16 UTC 版)

「連続一様分布」の記事における「一様性」の解説

一様分布する確率変数の任意の固定長の区間での確率は、その区間が分布の台に含まれる限りにおいて、その区間自体の位置とは独立である（ただし、区間の長さには依存する）。 これを示すため、X ≈ U(0, b) で [x, x + d] が [0, b] の部分区間であり、定数 d > 0 とすると、 P ( X ∈ [ x , x + d ] ) = ∫ x x + d d y b − a = d b − a {\displaystyle P\left(X\in \left[x,x+d\right]\right)=\int _{x}^{x+d}{\frac {\mathrm {d} y}{b-a}}\,={\frac {d}{b-a}}} となり、x とは独立となる。この事実から「一様」分布と名付けられた。

※この「一様性」の解説は、「連続一様分布」の解説の一部です。
「一様性」を含む「連続一様分布」の記事については、「連続一様分布」の概要を参照ください。

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/05/02 09:30 UTC 版)

「ハッシュ関数」の記事における「一様性」の解説

良いハッシュ関数は、考えられる入力範囲が出力範囲全体になるべく一様に分布するようにマッピングを行う。つまり、出力範囲のそれぞれのハッシュ値はほぼ同じ確率で生成されるべきである。このような条件があるのは、異なる入力が同じハッシュ値にマッピングされてしまう「衝突」が発生すると、ハッシュに基づく各種技法のコストは衝突発生回数と共に増大するためである。あるハッシュ値が他のハッシュ値より生成されやすいなら、参照操作で衝突しているエントリ間でどれが探しているエントリかを調べる作業が基本的に大きな部分を占めることになる。 注意しなければならないのは、「一様分布」が必要なのであって「無作為」である必要はないという点である。よい無作為化関数はハッシュ関数にも適していることが多いが、ハッシュ関数が無作為化関数である必要はない。 ハッシュテーブルには可能な入力のうちのごく一部が格納されているということが多い。例えば、ある会の会員名簿には100人ほどの会員の名前が並んでいるが、それはこの世に存在する人名のごく一部である。その場合、一様性はほぼ全ての典型的な部分集合に対して成り立てばよいのであって、全ての可能なエントリ全体の集合に対して成り立たせる必要はない。 言い換えれば、典型的な m 個のレコードの集合を n 個のバケットにマッピングする場合、1つのバケットに対応するレコード数が m/n より大きくなる可能性をなるべく小さくすればよい。特に m が n より小さい場合、一部のバケットだけが1つまたはせいぜい2つのレコードを格納するようにすべきである。理想的な完全ハッシュ関数では、各バケットには最大でも1つのレコードしか格納されない。しかし、n が m よりずっと大きくても、衝突を完全に無くすことはできない（誕生日のパラドックスを参照）。 ハッシュ関数を評価する場合、ハッシュ値の分布の一様性はカイ二乗検定で評価できる。

※この「一様性」の解説は、「ハッシュ関数」の解説の一部です。
「一様性」を含む「ハッシュ関数」の記事については、「ハッシュ関数」の概要を参照ください。

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2009/10/30 11:39 UTC 版)

「回路計算量」の記事における「一様性」の解説

論理回路は一様でない計算模型の典型例であり、入力長が違えば回路も異なる。一方チューリングマシンのような一様な計算模型では、同じ計算機械を任意の入力長に使うことができる。従って、ある計算問題に対応した論理回路は（入力長に従って） C1,C2,... のように複数存在し、Cn の回路は n ビットの入力を扱う。従って一様性はそれら論理回路群全体で成り立つものであり、個々の回路は計算資源を制限したチューリングマシンで計算可能である。

※この「一様性」の解説は、「回路計算量」の解説の一部です。
「一様性」を含む「回路計算量」の記事については、「回路計算量」の概要を参照ください。