均勻分佈比特但密度不斷增加的算法

Question

我正在尋找一種算法來生成一系列比特，使得該系列開始時的密度非常低（即大部分爲0），並且在系列非常高（即大部分爲1s）。我通過改變隨機數落入一個範圍內的概率來解決這個問題，但我希望找到一種更結構化的[read：deterministic]算法，就像某種方法來穩定地增加1s的密度。

有沒有人知道類似的東西？或者也許讀一些這樣的話題？這被證明是相當有趣的思考，但也相當具有挑戰性（除非我錯過簡單的東西）！

Answer 1

A到確定性（不隨機數）做到這一點非常普遍的方式是有西格瑪 - 三角調製器。

接從0開始，並在1結束然後用調製器算法以0和1的近似平滑遞增函數。

NB：Σ-Δ調製器被非常普遍地應用於電子成模擬信號（聲音，視頻等）轉換爲1/0比特流。

爲了說明，我要從0一個坡道1在一段100，並使用一階轉換器。但是你可以選擇你喜歡的任何曲線。例如，水平縮放的hyperbolic tangent會使中間的更快更改的起始和結束斜率更小。而二階轉換器可能會提供「更好」的模式。他們往往不太經常。

這是一個非常簡單的算法。在C：

#include <stdio.h> 

int main(void) { 
    int x_max = 99; 
    double vn = 0; 
    for (int x = 0; x <= x_max; ++x) { 
    double xn = (double) x/x_max; // linear ramp from 0 to 1. 
    int yn = vn > 0.5; 
    printf("%d", yn); 
    vn += xn - yn; 
    } 
    printf("\n"); 
    return 0; 
} 

正如你所看到的，它是確定性的。它也非常簡單和快速：沒有三角函數，指數等，這就是爲什麼它對硬件實現有好處。

輸出分成2行以方便查看：

00000000000100000010000100010001001001001010100101 
01010110101011011011011101110111101111110111111111 

Here是Σ-Δ轉換一開創性論文。上述程序中的變量與圖8相匹配。圖13顯示了一個二階圖，如果你想嘗試。

爲了好玩，這裏是與1000的間隔運行：

00000000000000000000000000000000010000000000000000 
00000010000000000000001000000000000100000000001000 
00000010000000010000000100000001000000010000001000 
00010000010000010000010000010000010000100001000010 
00010000100001000010001000010001000100001000100010 
00100010001000100100010001001000100100010010001001 
00010010010010010001001001001001001001001001001001 
00101001001001001010010010100100101001010010010100 
10100101010010100101001010100101010010101010010101 
01001010101010100101010101010101010010101010101010 
10101010101010101101010101010101010110101010101011 
01010101101010101101010110101011010110101101010110 
10110101101101011010110110101101101011011011011010 
11011011011011011011011011011011011101101101101101 
11011011101101110110111011011101110110111011101110 
11101110111011110111011101111011101111011110111101 
11101111011110111101111101111101111101111101111101 
11111011111101111111011111110111111101111111101111 
11111011111111110111111111111011111111111111101111 
11111111111111111101111111111111111111111111111111 

Answer 2

有幾種可能性來做到這一點，它取決於你想要的發行版。這是一個很簡單的例子，我覺得應該爲你的目的工作：

for (i=0; i<end; i++) 
    value = rand(0,1) * (2*i/end) * (2*(end-i)/end); 
    if(i>end/2) 
    value = 1 - value; 

凡蘭特（0,1）產生0和1之間的一個數值。在你有舍的結果結束。

編輯：我做了一個快速的算法實現和模擬它50次（結束= 500）。它顯示了1和0的分佈（在舍入之前）。

Answer 3

如果0和1被完全設置，那麼你可以在中間分割結果，左半部分應該有1/3的1/3與右半部分相比（換句話說：左半部分有1/4所有的和右半部分的3/4）。所以我們可以用這個想法來生成這些位。

private static boolean[] res; 

public static boolean[] generate(int len) { 
    res = new boolean[len]; 
    generate(0, len, len/2); 
    return res; 
} 

private static void generate(int start, int len, int bits) { 
    if (bits == len) 
     for (int i = start; i < start + len; i++) 
      res[i] = true; 
    else if (bits > 0) { 
     int l1 = len/2, l2 = len - l1, b1 = (bits + 2)/4, b2 = bits - b1; 
     if (l2 < b2) { 
      b2 = l2; 
      b1 = bits - b2; 
     } 
     generate(start, l1, b1); 
     generate(start + l1, l2, b2); 
    } 
} 

輸出爲63，64和65位：

000000100000001000100010001011100010001000111111111111111111111 
0000000100000001000100010001011100010001010111111111111111111111 
00000001000000010001000100010111000100010001111111111111111111111 

Answer 4

可以使用高斯分佈，其高度在許多應用中使用。

我使用Matlab，因爲它很容易適用於這種應用程序，但它應該很容易轉換爲另一種語言。

所以，假設你想用你問的標準創建一個20個值的數組。

len = 20; 
x = 1:len; 
y = normdist(x, len, len/5); % you can play with mean and standard deviation. 
plot(x,y) 

然後，添加隨機性公式，並根據需要添加的閾值。

rn = rand(1,len); 
res = y.*rn; 

，並添加一個門檻，讓說，低於平均值的那些都是零。

您可以用價值發揮，並得到一組值的，因爲你需要。

Answer 5

一種方法，其是相當靈活的是使用logistic function用於產生1比0。這假設你知道序列先驗的長度的概率，但給你很多的靈活性斜坡率以及獲得1的最小和最大概率。

既然你沒有指定的語言，我在Ruby的原型是：

# Creates an array of desired length whose values are symmetric 
# about the mid-point of the array, are bounded below and above 
# by min & max, and have a ramp up rate determined by steepness. 
def logistic_function(length, min, max, steepness) 
    mid = 0.5 * (length - 1) 
    range = max - min 
    # create, initialize elements via logistic fn, and return resulting array 
    Array.new(length) { |x| min + range/(1 + Math.exp(-steepness * (x - mid))) } 
end 

length = 80 
# 80 probabilities will vary from 0.1 to 0.9, with a relatively slow ramp-up 
probability = logistic_function(length, 0.1, 0.9, 0.1) 

# Create an array of bits where each entry's probability of being 1 
# is determined by the logistic function we generated 
bits = Array.new(length) { |i| rand <= probability[i] ? 1 : 0 } 
puts bits.join 

樣本輸出從運行兩次：

00000000011000001000001100001101001010000011001011001111000111011111101011111011 
10100000000000000000010000010111000000110110111011111000111011111111111110111111 

的結果是隨機的，但你可以（隨機）控制的1的密度和通過min，max，和steepness轉變速度。

注意，通過邏輯函數的對稱性，1位總比例預期值(min + max)/2。使用我在示例中使用的參數，即0.5。爲了說明這一點，我計算了一組80位中1的數量，並重復了10,000次試驗的生成/計數。由於預期的比例爲0.5，1次的每次實驗的預期數是40.這是實證結果：