计算最终市场分布 - 竞争性规划

Question

我在练习竞争性编程时遇到了以下问题.我手动解决了,有点设计方法,但我的答案是错误的,我无法想象如何扩展我的方法.

问题:

N个咖啡连锁店正在通过激烈的广告战争争夺市场份额.每天,一定比例的客户将被说服从一个链转换到另一个链.

给出了当前的市场份额和每日客户转换的概率.如果广告永远存在,那么市场份额的最终分配是什么？

假设:总市场份额为1.0,客户转换的概率独立于其他客户和天数.

例如:2个咖啡连锁店:A和B市场份额A:0.4市场份额B:0.6.

每天,客户从A切换到B的概率为0.2每天,客户从B切换到A的概率为0.1

input: market_share=[0.4,0.6],

switch_prob = [[.8,.2][.1,.9]]

output: [0.3333 0.6667]

直到这里的一切都是问题的一部分,我没有形成例子或假设,他们给出了问题.

My_attempt:根据我的理解,切换概率表示从A切换到B的概率.

因此,

market_share_of_A = current_market_share - lost_customers + gained_customers and 
marker_share_of_B = (1 - marker_share_of_A)

iter_1: 
    lost_customers = 0.4 * 0.8 * 0.2 = 0.064
    gained_customers = 0.6 * 0.2 * 0.1 = 0.012
    market_share_of_A = 0.4 - 0.064 + 0.012 = 0.348
    marker_share_of_B = 1 - 0.348 = 0.652

iter_2:
    lost_customers = 0.348 * 0.1 * 0.2 = 0.00696
    gained_customers = 0.652 * 0.9 * 0.1 = 0.05868
    market_share_of_A = 0.348 - 0.00696 + 0.05868 = 0.39972
    marker_share_of_B = 1 - 0.32928 = 0.60028

my answer: [0.39972, 0.60028]

如前所述,预期的答案是[0.3333 0.6667].

1. 我不明白我哪里错了？如果出现问题,必须是我对这个问题的理解.请提供您的想法.

2. 在这个例子中,他们展示了一个简单的案例,即只有两个竞争对手.怎么样还有什么？让我们说三 - A, B, C.我想输入必须提供开关概率的形式[[0.1, 0.3, 0.6]..],因为A会失去它的客户B以及C与会有的很多实例.现在,我将至少计算两家公司的市场份额,第三位将是(1-sum_of_all).在计算B的市场份额时,我将不得不计算它失去的客户以及获得的和公式(current - lost + gained).获得将是总和gain_from_A and gain_from_C.它是否正确？

Answer 1

继我的评论之后,这个问题可以表示为矩阵方程.

"过渡"矩阵的元素T(i, j)(维度N x N)定义如下:

• i = j(对角线):客户留链的概率i
• i != j(非对角线):客户链j转移到链的概率i

这个矩阵的物理意义是什么？让市场份额状态由P(i)大小的向量表示N,其i值为链的市场份额i.向量P' = T * P是每天之后的下一个共享状态.

考虑到这一点,均衡方程由下式给出T * P = P,即最终状态在转换下是不变的T:

| T(1, 1)  T(1, 2)  T(1, 3) ... T(1, N) |   | P(1) |   | P(1) |
| T(2, 1)  T(2, 2)  ...                 |   | P(2) |   | P(2) |
| T(3, 1)  ...                          |   | P(3) |   | P(3) |
| .        .                            | * | .    | = | .    |
| .                 .                   |   | .    |   | .    |
| .                         .           |   | .    |   | .    |
| T(N, 1)                       T(N, N) |   | P(N) |   | P(N) |

然而,这本身是无法解决的 - P只能在其元素之间确定多个比率(这种情况的技术名称让我感到惊讶 - 正如所MBo表明的那样是由于退化).还有一个附加约束,股票加起来为1:

P(1) + P(2) + ... P(N) = 1

我们可以选择一个任意的共享值(比如N第一个),并用这个表达式替换它.乘以,等式的第一行是:

T(1, 1) P(1) + T(1, 2) P(2) + ... T(1, N) (1 - [P(1) + P(2) + ... P(N - 1)]) = P(1)

--> [T(1, 1) - T(1, N) - 1] P(1) + [T(1, 2) - T(1, N)] P(2) + ... "P(N - 1)" = -T(1, N)

第二行的等价方程是:

[T(2, 1) - T(2, N)] P(1) + [T(2, 2) - T(2, N) - 1] P(2) + ... = -T(2, N)

总结一般模式,我们定义:

• 矩阵S(i, j)(尺寸[N - 1] x [N - 1]):

  - S(i, i) = T(i, i) - T(i, N) - 1
  - S(i, j) = T(i, j) - T(i, N)         (i != j)
  

• 包含第一个元素的Q(i)大小向量N - 1N - 1P(i)

• R(i)大小的矢量N - 1,这样R(i) = -T(i, N)

那么等式变成S * Q = R:

| S(1, 1)   S(1, 2)  S(1, 3) ... S(1, N-1)   |   | Q(1)   |   | R(1)   |
| S(2, 1)   S(2, 2)  ...                     |   | Q(2)   |   | R(2)   |
| S(3, 1)   ...                              |   | Q(3)   |   | R(3)   |
| .         .                                | * | .      | = | .      |
| .                  .                       |   | .      |   | .      |
| .                          .               |   | .      |   | .      |
| S(N-1, 1)                      S(N-1, N-1) |   | Q(N-1) |   | R(N-1) |

求解上面的等式给出Q了第一个N - 1共享值(当然也是约束的最后一个).这样做的方法包括高斯消元法和LU分解,两者都比直接计算的朴素路线更有效Q = inv(S) * R.

请注意,您可以翻转标志S并R进行更方便的评估.

上面给出的玩具示例结果非常简单:

| 0.8   0.1 |   | P1 |   | P1 |
|           | * |    | = |    |
| 0.2   0.9 |   | P2 |   | P2 |

--> S = | -0.3 |, R = | -0.1 |

--> Q1 = P1 = -1.0 / -0.3 = 0.3333
    P2 = 1 - P1 = 0.6667

一个例子N = 3:

    | 0.1  0.2  0.3 |           | -1.2   -0.1 |        | -0.3 |
T = | 0.4  0.7  0.3 |  -->  S = |             | ,  R = |      |
    | 0.5  0.1  0.4 |           |  0.1   -0.6 |        | -0.3 |

         | 0.205479 |
-->  Q = |          | , P3 = 0.260274
         | 0.534247 |

请原谅Robinson Crusoe风格的格式 - 稍后我会尝试在LaTeX中编写这些格式以便于阅读.