如何使用Monte Carlo的方法求极限概率

Question

我想了解如何使用Monte Carlo的方法来搜索某系统S的极限概率

例如：

    S0  S1  S2  S3
S0  0.1 0.9 0   0
S1  0   0.2 0.3 0.5
S2  0.2 0.1 0.5 0.2
S3  0.5 0   0.4 0.1

按照我的理解，我们需要生成一些数字（x）然后比较概率的方法：

if x 
   0   <= x < 0.1 => S0 -> S0
   0.1 <= x < 0.9 => S0 -> S1
   0.9 <= x < 0.9 => S0 -> S2
   0.9 <= x < 0.9 => S0 -> S3
   0.9 <= x < 1   => S0 -> S4

当 S4 - 限制（边界）

其他州也是如此。

按照这种方法，我可以计算转换次数：

  static double[] SimpleMonte(double[][] a, int iter = 1)
    {
        var n = a.GetLength(0);

        var p =
            a
            .Select(x => x.Select((_, i) => x.Take(i + 1).Sum()).ToArray())
            .ToArray();

        Random rand = new Random();

        double[] X = new double[n];
        for (int x = 0; x < n; x++)
        {
            double count = 0;
            for (int i = 0; i < iter; i++)
            {
                int row = x;
                bool notG = true;
                Console.Write("{0} -> ", row);
                while (notG)
                {

                    var e = rand.NextDouble();
                    Console.Write("({0})", Math.Round(e, 2));
                    bool ch = false;
                    for (int j = 0; j < n - 1; j++)
                    {
                        if (p[row][j] <= e && e < p[row][j + 1])
                        {
                            row = j + 1;
                            ch = true;
                            break;
                        }
                    }
                    if (!ch)
                        notG = false;
                    else
                    {
                        Console.Write("{0} -> ", row);
                        count++;
                    }
                }
                Console.WriteLine();
            }
            X[x] = count / iter;
        }
        return X;
    }

https://dotnetfiddle.net/nJF5sm

我很高兴听到有关如何解决此问题的提示。

Answer 1

在实际意义上，找到这样一个系统的极限的最佳方法是重复矩阵的平方，直到条目收敛。这是有效的，因为它是一个随机矩阵（每行的总和等于 1）。当我尝试它时，我得到了一个答案：

S0        S1        S2        S3
0.1939252 0.2593458 0.3294393 0.2172897

它给出了您将处于特定状态的平均概率。

要使用 Monte Carlo 方法，您应该像之前那样生成随机数并记录转换次数。那么你处于某种状态的平均概率是

(Amount of Transitions to State S)/(Total Transitions)

当你的 Total Transitions 足够大时。

在您提供的代码中，如果您不断增加 iter 变量的大小（并且它确实需要相对较大），那么输出的最后四行应该会收敛到上面的数字。希望对您有所帮助。

原始代码中存在一个错误，导致无法转换到初始状态。这是正确的版本：

static double[] SimpleMonte(double[][] a, int iter = 10000)
    {
        var n = a.GetLength(0);

        var p =
            a
            .Select(x => x.Select((_, i) => x.Take(i + 1).Sum()).ToArray())
            .ToArray();

        Random rand = new Random();
        double[] X = new double[n];
        int row = rand.Next(n);
        for (int i = 0; i < iter; i++)
        {
            var e = rand.NextDouble();
            X[row]++;
            if (e < p[row][0])
                row = 0;
            else
                for (int j = 0; j < n - 1; j++)
                {
                    if (p[row][j] <= e && e < p[row][j + 1])
                    {
                        row = j + 1;
                        break;
                    }
                }

        }
        return X.Select(x => x / iter).ToArray();
    }

如何使用Monte Carlo的方法求极限概率

How to use the method of Monte Carlo to search for the limit probabilities

c#

algorithm

statistics

montecarlo