Average Number

Weighted Average

兩數,依照比例(權重),各取一部分,加總,得到「加權平均數」。

加權平均數介於兩數之間。調整權重,可以得到兩數之間的每一種數字。

x = w x₁ + (1-w) x₂   (0 ≤ w ≤ 1)

推廣到多數。加權平均數介於最大值和最小值之間。

x = w₁x₁ + w₂x₂ + ... + wₙxₙ   (w₁ + ... + wₙ = 1)

推廣到高維度。加權平均數介於凸包之間。

⎡x⎤      ⎡x₁⎤      ⎡x₂⎤            ⎡xₙ⎤
⎢y⎥ = w₁ ⎢y₁⎥ + w₂ ⎢y₂⎥ + ... + wₙ ⎢yₙ⎥   (w₁ + ... + wₙ = 1)
⎣z⎦      ⎣z₁⎦      ⎣z₂⎦            ⎣zₙ⎦

其實只是每個維度分開處理
x = w₁ x₁ + w₂ x₂ + ... + wₙ xₙ
y = w₁ y₁ + w₂ y₂ + ... + wₙ yₙ
z = w₁ z₁ + w₂ z₂ + ... + wₙ zₙ

權重推廣成任意數。每個權重另外除以權重總和。

     (w₁)       (w₂)         (w₃)
      a          b            c        ax₁ + bx₂ + cx₃
x = ————— x₁ + —————  x₂ +  ————— x₃ = ———————————————
    a+b+c      a+b+c        a+b+c         a + b + c   
          a₁                       aₙ
x = ————————————— x₁ + ... + ————————————— xₙ
    a₁ + ... + aₙ            a₁ + ... + aₙ

    a₁ x₁ + ... + aₙ xₙ
  = ———————————————————
       a₁ + ... + aₙ   

數字推廣成任意事物。加權平均數無所不在。

主角    加權平均數
--------  ----------
質點    重心
溶液    混和濃度
機率    期望值
點座標   凸包範圍
函數值   一次內插
線性代數  線性組合
三原色   人類眼中的彩色

加權平均數的精髓:多數化作一數。

Floating Number

Random Variable與Distribution

現實世界的數值,通常是浮動數值,不是精準數值。數值具有多種可能性,有時高一點,有時低一點。

工程師活用了區間的概念,描述浮動數值。例如食品包裝經常見到的500±20,表示數值可能是區間[480,520]的其中一個。

工程師命名為「誤差範圍」。好用,但是太過陽春。

數學家活用了比例、函數兩個概念,描述浮動數值。我們可以自由控制要出現那些數值,個別的數值(離散)、一段範圍的數值(連續)。我們甚至可以個別調整每一種數值的出現程度高低。

數學家命名為「隨機變數」。這個名稱經常造成誤解,事實上這既非隨機、亦非變數。理想的名稱應是「浮動數字」。

兩個隨機變數可以加減乘除,但是計算過程非常複雜:試誤法,針對一個答案,窮舉各種得到此答案的方式,累加機率。

     add: X+Y  (Cauchy product) (convolution)
subtract: X-Y  (Cauchy product) (convolution)
multiply: XY   (Dirichlet product)
  divide: X/Y

數學家定義了一些簡易指標,可以迅速獲知隨機變數的重點。

一個隨機變數的
期望值/平均數 expected value / mean  : E[X]
平方期望值   expected squared value : E[X²]
變異數     variance               : E[(X-E[X])²] = Var[X]

兩個隨機變數的
共相關數 correlation             : E[XY]
共變異數 covariance              : E[(X-E[X])(Y-E[Y])] = Cov[X,Y]
相關係數 correlation coefficient : Cov[X,Y] / sqrt(Var[X]Var[Y])

由於隨機變數的四則運算非常複雜,數學家鮮少討論隨機變數的四則運算,轉而討論隨機變數的指標的四則運算。出乎意料地優雅。

E[X+Y] = E[X] + E[Y]
E[X⋅Y] = E[X] ⋅ E[Y]   if X and Y are independent
E[X+k] = E[X] + k
E[X⋅k] = E[X] ⋅ k
Var[X+Y] = Var[X] + Var[Y] + 2 ⋅ Cov[X,Y]
Var[X-Y] = Var[X] + Var[Y] - 2 ⋅ Cov[X,Y]
Cov[X,Y] = 0   if X and Y are independent
Var[X+k] = Var[X]
Var[X⋅k] = Var[X] ⋅ k²

至於「每一種數值的出現程度高低」的函數,數學家命名為「分布」。數學家創造了許多經典的分布,數學性質極強。例如兩個常態分布隨機變數,相加減還是常態分布。相乘除就不是。

uniform distribution
Gauss distribution (normal distribution)
binomial distribution
Poisson distribution

隨機變數的精髓:一數蘊含多數。

Mixture Distribution(Mixture Model)

數個隨機變數,浮動出現其中一個隨機變數。兩層隨機變數。

其實就是數個分布函數的加權平均數,因而稱作「混合分布」。想一想為什麼。

混合分布是計算學家的最愛。用幾個經典的分布,調整平均數、變異數,以及權重,組合出具有曼妙曲線的分布。

經典的混合分布,像是數個常態分布的加權平均數,稱作「高斯混合模型Gaussian Mixture Model」。

Floating Tuple

Multivariate Random Variable與Joint Distribution

我們可以個別調整每一種數組的出現程度高低。數學家命名為「多變量隨機變數」。理想的名稱應是「浮動數組」。

至於「每一種數組的出現程度高低」的函數,數學家命名為「聯合分布」。之前介紹了許多經典的分布,通通可以推廣成聯合分布。

l = {Line[{{3,3,1},{3,3,0}}], Line[{{5,6,1},{5,6,0}}], Line[{{8,2,1},{8,2,0}}], Line[{{2,8,1},{2,8,0}}]}; g = Show[ListPointPlot3D[{0,0,0}, Boxed -> False, Axes -> False, PlotRange -> {{0,10},{0,10}}], Graphics3D[{Thickness[0.01], CapForm["Butt"], Red, l}]] img = ImageResize[Rasterize[g, "Image", ImageResolution -> 72*3], Scaled[1/3]]; ImageCrop[RemoveBackground[img, {{{0, 0}}, 0.1}]]
F[x_, y_] := PDF[MultinormalDistribution[{3, 3}, {{1, 0}, {0, 1}}], {x, y}] + PDF[MultinormalDistribution[{5, 6}, {{1, 0}, {0, 1}}], {x, y}] + PDF[MultinormalDistribution[{8, 2}, {{1, 0}, {0, 1}}], {x, y}] + PDF[MultinormalDistribution[{2, 8}, {{1, 0}, {0, 1}}], {x, y}]; Show[ Plot3D[F[x,y], {x, 0, 10}, {y, 0, 10}, PlotRange -> All, Boxed -> False, Mesh -> None, Axes -> False, PlotPoints -> 50, ColorFunction -> (ColorData["CherryTones"][Rescale[#3, {-4, 4}]] &)], ParametricPlot3D[{x, 2, F[x,2]}, {x, 0, 10}, PlotStyle -> Red] ] Plot[F[x,2], {x, 0, 10}, PlotRange -> All, PlotStyle -> Red, Axes -> False] Show[ Plot3D[F[x,y], {x, 0, 10}, {y, 0, 10}, PlotRange -> All, Boxed -> False, Mesh -> None, Axes -> False, PlotPoints -> 50, ColorFunction -> (ColorData["CherryTones"][Rescale[#3, {-4, 4}]] &)], ParametricPlot3D[Table[{x, y, F[x,y]}, {y, 0.2, 9.8, 0.2}], {x, 0, 10}, PlotStyle -> Red] ] Plot[Integrate[F[x,y],{y,-20,+20}], {x, 0, 10}, PlotRange -> All, PlotStyle -> Red]

數學家發明了一些特殊觀點,可以幫忙分析聯合分布:

條件分布 conditional distribution:部分維度只看特定數值。
例如(X=x,Y)是垂直截面,(X,Y=y)是水平截面。(乘上適當倍率,調整成分布。)

邊緣分布 marginal distribution   :只看部分維度。
例如X是疊加水平截面,Y是疊加垂直截面。

Independent / Uncorrelated

一個數組(x,y),拆成兩個數字x與y,只有唯一一種方式。

兩個數字x與y,併成一個數組(x,y),只有唯一一種方式。

一個多變量隨機變數(X,Y),拆成兩個隨機變數X與Y,只有唯一一種方式:邊緣分布。

兩個隨機變數X與Y,併成一個多變量隨機變數(X,Y),卻有無限多種方式:(X,Y)的分布擁有無限多種可能性。

Plot3D[Piecewise[{{0.25, 1 < x < 3 && 1 < y < 3}}], {x, 0, 4}, {y, 0, 4}, PlotRange -> {0,1}, ExclusionsStyle -> Directive[Thick, Red], Boxed -> False, Mesh -> None, Axes -> False, PlotPoints -> 50, ColorFunction -> (ColorData["CherryTones"][Rescale[#3, {-4, 4}]] &)] F[x_,y_] := Piecewise[{ {0.15, 1 < x < 2 && 1 < y < 2}, {0.35, 2 < x < 3 && 1 < y < 2}, {0.35, 1 < x < 2 && 2 < y < 3}, {0.15, 2 < x < 3 && 2 < y < 3}}]; Plot3D[F[x,y], {x, 0, 4}, {y, 0, 4}, PlotRange -> {0,1}, ExclusionsStyle -> Directive[Thick, Red], Boxed -> False, Mesh -> None, Axes -> False, PlotPoints -> 50, ColorFunction -> (ColorData["CherryTones"][Rescale[#3, {-4, 4}]] &)]

數學家從中挑選比較特別的款式,方便討論與運用:

獨立  independent :p(X,Y)(x,y) = pX(x)pY(y)
不相關 uncorrelated:E[XY] = 0

數學家的敘述方式是「兩個隨機變數X與Y是獨立的」,背後意義是「多變量隨機變數(X,Y)的分布是一種特殊款式:獨立」。

p = {{1, 1, 0.05}, {1.5, 1, 0.1}, {-1, -1, 0.1}, {-1, 0, 0.05}, {0, 1.5, 0.05}, {0, 0, 0.1}, {-1, -1.5, 0.2}, {1, -2, 0.15}, {-2, 1, 0.2}}; l = Table[Line[{p[[i]], {p[[i,1]], p[[i,2]], 0}}], {i,1,9}]; g = Show[ListPointPlot3D[{0,0,0}, Boxed -> False, Axes -> False, DataRange -> {{-2,2},{-2,2}}, PlotRange->{0,0.4}], Graphics3D[{Thickness[0.01], CapForm["Butt"], RGBColor[192,0,0], l}]] img = ImageResize[Rasterize[g, "Image", ImageResolution -> 72*3], Scaled[1/3]]; ImageCrop[RemoveBackground[img, {{{0, 0}}, 0.1}]]
px = {{2, 0.6}, {3, 0.25}, {2.5, 0.15}}; py = {{3, 0.6}, {2, 0.25}, {1 , 0.15}}; pxy = {{2, 3, 0.6*0.6}, {2, 2, 0.6*0.25}, {2, 1, 0.6*0.15}, {3, 3, 0.25*0.6}, {3, 2, 0.25*0.25}, {3, 1, 0.25*0.15}, {2.5, 3, 0.15*0.6}, {2.5, 2, 0.15*0.25}, {2.5, 1, 0.15*0.15}}; l = Table[Line[{pxy[[i]], {pxy[[i,1]], pxy[[i,2]], 0}}], {i,1,9}]; g = Show[ListPointPlot3D[{0,0,0}, Boxed -> False, Axes -> False, PlotRange -> {{0,4},{0,4}}], Graphics3D[{Thickness[0.01], CapForm["Butt"], RGBColor[192,0,0], l}]] img = ImageResize[Rasterize[g, "Image", ImageResolution -> 72*3], Scaled[1/3]]; ImageCrop[RemoveBackground[img, {{{0, 0}}, 0.1}]]
F[x_] := PDF[GammaDistribution[2, 1], x]; G[y_] := PDF[NormalDistribution[2, 0.5], y]; Plot[F[x], {x, 0, 4}, PlotRange -> {0,1}, Filling -> Axis] Plot[G[y], {y, 0, 4}, PlotRange -> {0,1}, Filling -> Axis] Show[ Plot3D[F[x]*G[y], {x, 0, 4}, {y, 0, 4}, PlotRange -> All, Boxed -> False, Mesh -> None, Axes -> False, PlotPoints -> 50, ColorFunction -> (ColorData["CherryTones"][Rescale[#3, {-4, 4}]] &)], ParametricPlot3D[Table[{x, y, F[x]*G[y]}, {y, 0.1, 3.9, 0.1}], {x, 0, 4}, PlotStyle -> Red] ]

獨立:(X=x,Y=y)的出現程度,等於X=x的出現程度、Y=y的出現程度兩者相乘。

所有垂直截面皆相似、所有水平截面皆相似。

條件分布、邊緣分布,兩者相似(僅倍率不同,可以是零倍)。

無論有X沒X,都不影響Y的分布形狀,因而稱作獨立。

數學家很喜歡假設隨機變數是獨立的,讓分布變得很漂亮。

F[x_] := PDF[StudentTDistribution[1], x]; G[y_] := PDF[StudentTDistribution[1], y]; a = Cos[Pi/4]; b = Sin[Pi/4]; Plot3D[F[a*x-b*y]*G[b*x+a*y], {x, -5, 5}, {y, -5, 5}, PlotRange -> All, Boxed -> False, Mesh -> None, Axes -> False, PlotPoints -> 50, ColorFunction -> (ColorData["CherryTones"][Rescale[#3, {-4, 4}]] &)]

不相關:共相關數等於零。X與Y的點積是0。

共相關數 E[XY]    :每個數組的XY相乘,求平均數。
正相關  E[XY] > 0:一三象限比較厚實。大致成正比。
負相關  E[XY] < 0:二四象限比較厚實。大致成反比。
不相關  E[XY] = 0:一三象限、二四象限,勢均力敵。

獨立較嚴格,不相關較寬鬆。獨立僅一種,不相關有多種。

有件事值得一提:當X或Y的平均數是零,獨立導致不相關。白話解釋是左右等量或者上下等量。

independent => uncorrelated   if E[X] = 0 or E[Y] = 0

E[X] = sum x p(x)
        ˣ
E[Y] = sum y p(y)
        ʸ
E[XY] = sum sum x y p(x,y)
         ˣ   ʸ
      = sum sum x y p(x) p(y)       獨立
         ˣ   ʸ
      = sum sum x p(x) y p(y)
          ˣ   ʸ
      = (sum x p(x)) (sum y p(y))   交叉相乘
          ˣ            ʸ
      = E[X]E[Y] = 0

不相關的定義有兩種:共相關數是零、共相關係數是零。後者直接得到「獨立導致不相關」的結論,省去「當平均數是零」的限制。

definition of "uncorrelated"
E[XY] = 0

another definition of "uncorrelated"
    E[(X-E[X])(Y-E[Y])]     
———————————————————————————— = 0
√ E[(X-E[X])²] E[(Y-E[Y])²] 

Transformation of Multivariate Random Variable

Plot3D[F[x/1.2,y/0.6], {x, 0, 10}, {y, 0, 10}, PlotRange -> All, Boxed -> False, Mesh -> None, Axes -> False, PlotPoints -> 50, ColorFunction -> (ColorData["CherryTones"][Rescale[#3, {-4, 4}]] &)] t = Pi/6; Plot3D[F[x*Cos[t]-y*Sin[t], x*Sin[t]+y*Cos[t]], {x, 0, 10}, {y, 0, 10}, PlotRange -> All, Boxed -> False, Mesh -> None, Axes -> False, PlotPoints -> 50, ColorFunction -> (ColorData["CherryTones"][Rescale[#3, {-4, 4}]] &)]

多變量隨機變數可以實施函數變換。雙射函數,浮動數字一齊改變,出現程度互不干涉,機率不必增減。

translate: (X+a, Y+b)
    scale: (sX, tY)
   rotate: (Xcos‎θ-Ysin‎θ, Xsin‎θ+Ycos‎θ)

多變量隨機變數可以實施仿射變換,變成不相關;但是無法變得獨立,只能變得盡量獨立。請見本站文件「Principal Component Analysis」。

獨立、不相關的多變量隨機變數,實施仿射變換,性質可能保留或失效。

獨立       p(X,Y)(x,y) = pX(x)pY(y)
位移:仍然獨立  p(X,Y)(x+a,y+b) = pX(x+a)pY(y+b)
縮放:仍然獨立  p(X,Y)(sx,ty) = pX(sx)pY(ty)
旋轉:通常失效  p(X,Y)(xcos‎θ-ysin‎θ,xsin‎θ+ycos‎θ)

不相關      E[XY] = 0
位移:通常失效  E[(X+a)(Y+b)] = E[XY] + aE[Y] + bE[X] + ab
縮放:仍然不相關 E[(sX)(tY)] = stE[XY] = 0
旋轉:通常失效  E[(Xcos‎θ-Ysin‎θ)(Xsin‎θ+Ycos‎θ)] = (E[X²]-E[Y²])sin‎θcos‎θ

Random Vector

多個隨機變數,合稱「隨機向量」。

一個隨機變數推廣成多個隨機變數,衍生歧義:

多變量 multivariate :一個變數推廣成一個數組。重視聯合分布。
多變數 multivariable:一個變數推廣成多個變數。輕視聯合分布。

Floating Sequence

Random Variable

理想的名稱應是「浮動數字」,但是數學家卻稱作「隨機變數」,事實上這既非隨機、亦非變數。經典的隨機變數:

uniform random variable
binomial random variable
Gauss random variable
Poisson random variable

數學家定義了一些簡易指標,可以迅速獲知隨機變數的重點。

一個隨機變數的
期望值/平均數 expected value / mean  : E[X]
平方期望值   expected squared value : E[X²]
變異數     variance               : E[(X-E[X])²] = Var[X]

兩個隨機變數的
共相關數 correlation             : E[XY]
共變異數 covariance              : E[(X-E[X])(Y-E[Y])] = Cov[X,Y]
相關係數 correlation coefficient : Cov[X,Y] / sqrt(Var[X]Var[Y])

多個隨機變數的
共相關矩陣 correlation matrix : Rᵢⱼ = E[XᵢXⱼ]
共變異矩陣 covariance matrix  : Cᵢⱼ = E[(Xᵢ-E[Xᵢ])(Xⱼ-E[Xⱼ])]

Random Process(Stochastic Process)

理想的名稱應是「浮動數列」與「浮動函數」,但是數學家卻稱作「隨機過程」。經典的隨機過程:

Gauss process:每個隨機變數都是高斯分布,每個隨機變數組合都是多維高斯分布。
Wiener process:高斯過程的積分。就是「布朗運動」。
Markov process:以先前幾個隨機變數的數值,決定下一個隨機變數。
Ornstein–Uhlenbeck process:每個隨機變數都是高斯分布,隨機變數之間有相關。
martingale:最新的K個隨機變數,期望值是定值。

數學家定義了一些簡易指標,可以迅速獲知隨機過程的重點。

一個隨機過程的                   原數列、右移τ位,兩者點積,除以數列長度
自相關函數 autocorrelation     : rXX(τ) = avgt E[XtXt+τ]
自變異函數 autocovariance      : cXX(τ) = avgt E[(Xt-E[Xt])(Xt+τ-E[Xt+τ])]

兩個隨機過程的
互相關函數 cross-correlation   : rXY(τ) = avgt E[XtYt+τ]
互變異函數 cross-covariance    : cXY(τ) = avgt E[(Xt-E[Xt])(Yt+τ-E[Yt+τ])]

數學家定義了一些簡易指標,隨機過程打散成大量隨機變數。

一個隨機過程的
自相關矩陣 autocorrelation matrix : Rᵢⱼ = E[XᵢXⱼ]
自變異矩陣 autocovariance matrix  : Cᵢⱼ = E[(Xᵢ-E[Xᵢ])(Xⱼ-E[Xⱼ])]

兩個隨機過程的
互相關矩陣 cross-correlation matrix : Rᵢⱼ = E[XᵢYⱼ]
互變異矩陣 cross-covariance matrix  : Cᵢⱼ = E[(Xᵢ-E[Xᵢ])(Yⱼ-E[Yⱼ])]

*離散隨機過程,叫做OOO矩陣;連續隨機過程,叫做OOO函數。

隨機過程兩大主要應用:

一、讓數列和函數具有浮動範圍、彈性範圍、緩衝範圍。例如「Gauss Process Regression」、「Hidden Markov Model」。

二、亂跳的數列和函數。例如「CIR Model」。

Random Field

https://mathematica.stackexchange.com/questions/4829/ https://mathematica.stackexchange.com/questions/144443/ GaussianRandomField[ size : (_Integer?Positive) : 256, dim : (_Integer?Positive) : 2, Pk_: Function[k, k^-3]] := Module[ {Pkn, fftIndgen, noise, amplitude, s2}, Pkn = Compile[{{vec, _Real, 1}}, With[{nrm = Norm[vec]}, If[nrm == 0, 0, Sqrt[Pk[nrm]]]], CompilationOptions -> {"InlineExternalDefinitions" -> True}]; s2 = Quotient[size, 2]; fftIndgen = ArrayPad[Range[0, s2], {0, s2 - 1}, "ReflectedNegation"]; noise = Fourier[RandomVariate[NormalDistribution[], ConstantArray[size, dim]]]; amplitude = Outer[Pkn[{##}] &, Sequence @@ ConstantArray[N @ fftIndgen, dim]]; InverseFourier[noise * amplitude] ] ListPlot3D[GaussianRandomField[128, 2] // Chop, Mesh -> None, Boxed -> False, Axes -> False, ColorFunction -> (ColorData["CherryTones"][Rescale[#3, {-2, 2}]] &) ] data = GaussianRandomField[16, 2] // Chop; ListPointPlot3D[data, PlotStyle -> {PointSize[Large], Black}, Boxed -> False, Axes -> False] ListPointPlot3D[data, Filling -> Bottom, FillingStyle -> Directive[Gray, Thick], Boxed -> False, Axes -> False]

推廣成多變量函數。空間處處有浮動數字、甚至浮動數組。

理想的名稱應是「浮動矩陣」與「浮動函數」,但是數學家卻稱作「隨機場」。經典的隨機場:

Gauss random field:每個隨機變數都是高斯分布,每個隨機變數組合都是多維高斯分布。
Markov random field:以相鄰的隨機變數的數值,決定本處的隨機變數。
Gibbs random field:馬可夫隨機場,而且隨機變數皆是正數。

隨機場兩大主要應用:

一、隨機地形、紋路。例如「Matérn Covariance Function」。

二、圖片分割、生成。例如「Markov Random Field」。

Random Process的頻譜

隨機過程,實施「傅立葉轉換」,從時域變頻域。

普通的隨機過程:無解析解,頻譜混亂。

滿足wide-sense stationary條件的隨機過程:有解析解。兩兩的共相關數,可求得頻譜。具備傅立葉轉換的相關數學特性,諸如線性、卷積乘法對偶、能量守恆(Parseval's theorem)。

然而,滿足wss條件的隨機過程,就是每個數字幾乎一樣的數列。缺乏討論意義,也無法解決現實問題。數學家目前僅發現wss條件,尚未發現更具討論意義的條件。

Martingale

https://en.wikipedia.org/wiki/Doob_martingale
https://en.wikipedia.org/wiki/Azuma's_inequality

When analyzing sums, random walks, or other additive functions of independent
random variables, one can often apply the central limit theorem, law of large
numbers, Chernoff's inequality, Chebyshev's inequality or similar tools. When
analyzing similar objects where the differences are not independent, the main
tools are martingales and Azuma's inequality.

Azuma's inequality applied to the Doob martingale gives the method of bounded
differences (MOBD) which is common in the analysis of randomized algorithms.

Random Number

Random Number

「隨機數」、「亂數」。我們習慣一口氣取大量隨機數。

1694 19262 3252 4541 20 28590 6191 814 30047 9007 29380 1639 23559

什麼樣子叫做Random呢?目前沒有定論!

大家習慣把Random解讀為「沒有規律」、「不可預測」、「亂」,但是沒有人能明確描述詳細內容。

大致能想到的有:

一、數字的分布:每個數字都可能出現。
二、數字的排版:數字沒有特殊造型。
三、數字的擾動:數字歪了,多了點、少了點。
四、次序的更動:下個數字不知道是哪一個。

相關的數學概念有:

一、Inversion 逆序對
二、Entropy 熵
三、Discrepancy
四、Normal Number 正規數
五、Point Process 點程序

Pseudorandom Number

計算機只能接受明確指令,人類只好使用明確數學公式、明確演算法來製造隨機數。隨機數具有規律、可以預測,於是早期文獻稱作「偽隨機數」、「偽亂數」。

儘管隨機數具有規律、可以預測,我們還是可以努力讓隨機數「看起來似乎很亂」,讓人一時無法預測。但由於缺乏「亂」的明確定義,所以無法精準評比優劣。一切都是靠感覺,很不科學。

C標準函式庫,提供了隨機數。可惜不是均勻分布uniform distribution,時常為人詬病。

C++標準函式庫,提供了健全的隨機數。

演算法(Linear Congruential Generator)

先備知識是「餘數」。

以數學式子xnext = (((x ⋅ a) + b) % n);不斷製造隨機數。

當n是質數,則0到n-1恰好各出現一次,呈均勻分布。不過當n不是質數,就很難說了,必須小心設定a b n才行。

缺點:每n個數字循環出現,可以預測。實務上會讓n很大,以避開缺點。

C語言的rand()即是此演算法。

演算法(Xorshift)

餘數多項式,化作二進位數字。餘數多項式加法、乘法,化作xor、shift。請自行查詢細節。

演算法(Xoroshiro128+)

我沒有研究。請自行查詢細節。

演算法(Mersenne Twister)

我沒有研究。請自行查詢細節。

演算法(Fortuna)

我沒有研究。請自行查詢細節。

均勻隨機數調整範圍:浮點數

多種均勻隨機數的加減乘除,不再是均勻隨機數!別亂用。

random(0, 2) + random(0, 3) ≠ random(0, 5)
random(0, 2) × random(0, 3) ≠ random(0, 6)

均勻隨機數與常數的加減乘除,仍是均勻隨機數。

random(0, 2) + 3 = random(3, 5)
random(0, 2) - 3 = random(-3, -1)
random(0, 2) × 3 = random(0, 6)
random(0, 2) ÷ 3 = random(0, 2/3)

均勻隨機數調整範圍:無號數

多種均勻隨機數,佔據各個位數,仍是均勻隨機數,但是不連續。令基數大小等於均勻隨機數範圍,就會連續。

base 10:
  random[0, 4]
+ random[0, 2] × 10 = [0,4] or [10,14] or [20,24]
base 2:
  random[0, 2-1] × 2⁰
+ random[0, 2-1] × 2¹
+ random[0, 2-1] × 2² = random[0, 2³)
prime base:
  random[0, 2-1]
+ random[0, 3-1] × (2)
+ random[0, 5-1] × (2×3)
+ random[0, 7-1] × (2×3×5) = random[0, 2×3×5×7)

一種均勻隨機數,調整範圍的演算法比較複雜:

一、令位數足夠大,直到涵蓋範圍。

(尚無正式名稱。也許可以稱做Radix Sampling。)

二、不斷產生均勻隨機數,直到符合範圍。

(後面章節介紹的Rejection Sampling。)

缺點是計算過程可能溢位。解法是質因數分解,但是代價太大,實務上沒人使用。

為了避免溢位,折衷方式是隨便分解數字。無法整除的部分,導致隨機數不再是均勻分布。無法整除的部分是低位數,影響不大。

libstdc++的uniform_int_distribution,採用折衷方式,不是均勻分布。注意到註解的地方。

libc++的uniform_int_distribution,我沒有仔細看懂。

Random Tuple

2D Random Number

二維隨機數,更加講究排版,衍生許多演算法。

       regular:排列整齊。缺點是太過整齊,具有明顯紋路。
       uniform:均勻分布。缺點是不夠整齊,偶有空白小格。
      jittered:regular + uniform,每小格任取一點。
                宏觀整齊適中,微觀仍不夠整齊,常常靠太近。
        n-rook:n個城堡不互相攻擊。奇爛無比。
multi-jittered:每小格實施n-rook。稍微改善小處不夠整齊的問題。
  Poisson disk:每一點到其他點的最短距離為定值d。整齊。慢。
best candidate:每一點到先前點的最短距離盡量長。不太整齊。快。
    Hammersley:(i, i的二進位鏡射)。整齊適中。超快!
        Halton:(i的a進位鏡射, i的b進位鏡射),a與b互質。超快!
         Sobol:我沒有研究。

演算法(Poisson Disk Sampling)

每回合在圓形聯集的邊界上隨機生一點。自訂圓半徑。

演算法(Best Candidate Sampling)

每回合隨機生k個候選點,留下最遠的那一點。

演算法(Hammersley Sequence)

(i, i的二進位鏡射)。

i | i₍₂₎ |Φ(i)₍₂₎| Φ(i)
--|------|-------|------
1 |    1 | .1    | .5
2 |   10 | .01   | .25
3 |   11 | .11   | .75
4 |  100 | .001  | .125
5 |  101 | .101  | .635
6 |  110 | .011  | .325
7 |  111 | .111  | .875
8 | 1000 | .0001 | .0625

Φ(i): radical inverse of integer i

演算法(Halton Sequence)

(i的a進位鏡射, i的b進位鏡射),a與b互質。

演算法(Sobol Sequence)

演算法(Recursive Wang Tile)

隨機數調整範圍

一維隨機數,位於線段。可以變成圓形、半圓形。

二維隨機數,位於正方形。可以變成矩形、三角形、四邊形、多邊形、圓盤、球面、半球面。

Graphics3D[{PointSize[Large], Point[RandomPoint[Ball[], 200]]}, Boxed->False] Graphics3D[{PointSize[Large], Point[SpherePoints[200]]}, Boxed->False] u1 := RandomReal[{0,1}]; u2 := RandomReal[{0,1}]; f[{u1_, u2_}] := {Sqrt[u1]*Cos[2*Pi*u2], Sqrt[u1]*Sin[2*Pi*u2], Sqrt[1-u1]}; pts = f /@ Table[{u1, u2}, {200}]; Graphics3D[{PointSize[Large], Point /@ pts}, Boxed->False]

必須注意面積變化、密度變化,以確保均勻。

例如正方形變矩形:若長寬不相等,則寬密長疏。

例如正方形變圓盤:長變幅角、寬變半徑平方。若忘了開根號,則內密外疏。

Random Sequence

Random Sequence

古代數學家沒有仔細區分「浮動:有規矩」和「隨機:無規矩」的差別,把兩者都命名為隨機,混淆視聽。大家搞不清楚狀況的情況下,大家一直沒有深入研究隨機數列的演算法。

將就方式是1D Random Number。然而數字輪輪循環,很蠢。

將就方式是2D Random Number投影到一維。然而沒有任何理論根據,純粹憑感覺。

Random Sampling

Random Sampling

「隨機取樣」。創造大量隨機數字,符合指定分布。

使用均勻分布的隨機數,製作指定分布的隨機數。

UVa 12109

演算法(Importance Sampling)

均勻分布的隨機數,根據指定分布高低來複製數字。高處數量多,低處數量少。

缺點:很多數字相同、數量是整數而比例不精確、難以控制總數量。糟透了。

若起初是其他分布的隨機數,則指定分布除以隨機數分布,以比值高低來複製數字。

演算法(Inversion Sampling)

均勻分布的隨機數,代入「分布的積分的倒函數」,就得到該分布的隨機數。

若起初是其他分布的隨機數,則先變成均勻分布,再變成指定分布。

演算法(Rejection Sampling)

二維隨機數(x,p),在分布曲線下就保留,在分布曲線上就捨棄,x即為所求。相當直覺的方法。

缺點:一、很多隨機數沒有用處,白算了。二、下一個輸出,延遲時間不穩定。有時一下就得到,有時一直得不到。

減少空白處,增加使用率。想辦法建立一個上界函數upper(x),略大於等於分布,作為p的上界。

每個位置x的上界都不同,導致p有密有疏、有多有少;為了讓p均勻等量,x必須符合上界函數的分布。(上界函數除以曲線下方面積,面積調成1,就變成了分布。)

然而上界函數往往難想。這招往往難用。

演算法(Metropolis–Hasting Sampling)

原理源自Markov Chain。

直接講結論:隨機挑起點,隨機挑下一步。以分布高低比例,決定去或留。需要多少隨機數,就做多少回合。

步伐大小:可以採用任意分布,但是必須左右對稱。

去留判斷:一、下一步分布更高時:既然此處已取樣,分布更高的地方,也應該取樣,以符合分布高低。二、下一步分布更小時:依照比例高低來取樣,抽中原處的機會較高,抽中下一步的機會較低。

此演算法改善了先前缺點。遺珠之憾是隨機數有地緣關係。

演算法(Gibbs Sampling)

推廣到高維度。每次只沿一個維度走或停,每個維度隨機輪流一遍,再重新隨機輪流一遍,不斷下去。

演算法(Box–Muller Transform)

均勻分布變常態分布。因為常態分布的數學式子太長、計算時間太久,所以發明了快而不準的演算法。欲速則不達。

演算法(Central Limit Thorem)

任意分布變常態分布。中央極限定理:任意一個分布,取樣取多了,樣本們的平均數是一個浮動數字,呈現常態分布。

速度更快,準度更低。