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
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:每個隨機變數都是高斯分布,隨機變數之間有相關。

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

一個隨機過程的                   原數列、右移τ位,兩者點積,除以數列長度
自相關函數 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」。

二、亂跳的數列和函數。例如「Cox–Ingersoll–Ross 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 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)

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

速度更快,準度更低。