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)
均勻分布的隨機數,代入「分布的積分的倒函數」,就得到該分布的隨機數。
若起初是其他分布的隨機數,則先變成均勻分布,再變成指定分布。