Alpha: playing with randomness
===

[原文](https://blog.iota.org/alpha-d176d7601f1c)

如果您有追隨[Tangle簡介](https://wusyong.gitbooks.io/iota-guidebook/illustrated/tangle-illustrated.html)系列文章 , 那應該記得有一個控制隨機行走的參數 : $\alpha$
在這篇文章 , 會介紹 $\alpha$ 如何影響 tip 選擇算法與程式實作上的考量

注意這篇文章假設讀者已經知道 Tangle 如何建立 , 直接指向的交易和累積權重的計算
此外 , 讀者還需要知道[指數函數](https://zh.wikipedia.org/wiki/%E6%8C%87%E6%95%B0%E5%87%BD%E6%95%B0)的特性和基礎的機率論

# 為何我們需要隨機性

為了解 $\alpha$ 奠定基礎 , 我們需要記得為什麼一開始要隨機行走
目前的 tip 選擇算法 : 每筆新的交易都要驗證先前的兩筆交易 , 這樣的選擇方式決定了 Tangle 的外觀跟行為

Tip 選擇算法應該有下列兩點功能

1. 一旦交易累積大量的驗證交易 , 它就不太容易被拋棄
2. 誠實的交易應該被快速的驗證

為了實現第一點 , 我們可能決定隨機行走是從基因交易走到 tips , 行走過程總是選累積權重最大的指向交易
然而 , 這會破壞第二點 , 只有一條中心的鏈得到驗證 , 會有許多的交易被拋棄


(當行走總是選最大累積權重的交易 , 許多的交易會被拋棄)

為了這在兩點得到平衡 , 我們會介紹如何決定行走的下一步
我們希望累積權重較大的交易有比較高機率走到 , 但累積權重小的仍有機會被走到

# 數學的定義

我們定義轉移函數( transition function) , 轉移函數會告訴我們行走從當前交易到下一個直接指向交易的機率
我們希望這機率對於累積權重大的交易是高機率 , 而小的是低機率

轉移函數定義如下:


$P_{xy}$ 是行走從 $x$ 到 $y$ 的機率 , $H_{y}$ 是交易 $y$ 的累積權重 , $z$ ~> $x$ 是 " $z$ 直接指向 $x$ "

換句話說 , 從 $x$ 走到 $y$ 的機率對 $y$ 的累積權重是指數增加 , 對 $\alpha$ 是相乘 , 分母的和是歸一化因子 , 使得全部轉移機率和為一

# 例子

在下圖中 , 隨機行走抵達了交易 $X$ , 交易 $X$ 有三個直接指向的交易 : $A$ , $B$ 和 $C$
為了計算出轉移機率 , 我們先計算累積權重
$A$ 只有一筆交易直接驗證 , $A$ 的累積權重為 2
$B$ 有兩筆交易直接驗證 , $B$ 的累積權重為 3
$C$ 沒有交易直接驗證 , $C$ 的累積權重為 1


假設 $\alpha$ 為 1 , 代入轉移函數進行轉移機率的運算 , 得到下列結果


可以看到 $C$ 的機率相較 $A$ 與 $B$ 是小的 , 因為 $C$ 的累積權重小

如果降低 $\alpha$ 的數值 , 會減少累積權重的影響
例如 $\alpha = 0.1$ , 我們得到下列機率


雖然 $C$ 的機率是最小 , 但與 $A$ , $B$ 的差距不明顯了

如果讓 $\alpha = 0$ , 那 $A$ , $B$ 和 $C$ 就有同樣的機率 , 各是 ${1}/{3}$
這是權重完全沒影響 , 且行走完全隨機

另一個極端的情形 , 如果 $\alpha$ 很大 , $B$ 的轉移機率會很接近 $1$ , 而 $A$ 與 $C$ 的轉移機率會接近 $0$
這情況類似區塊鏈 , 我們只批准最長的鏈 , 而不合併其他分支

###### tags: `IOTA`