我在练习竞争性编程时遇到了以下问题。我手动解决了它,有点设计了一种方法,但我的答案是错误的,我无法想象如何扩展我的方法。
问题:
N家咖啡链式店正在通过一场激烈的广告 war 夺市场份额。每天都会有一定比例的顾客被说服从一个链式店转到另一个链式店。
给出了当前的市场份额和客户转换的每日概率。如果广告永远播放,市场份额的最终分配是什么?
假设:总市场份额为 1.0,客户转换的概率与其他客户和天数无关。
示例:2 家咖啡链式店:A 和 B 的市场份额 A:0.4 B 的市场份额:0.6。
每天,客户从 A 切换到 B 的概率为 0.2 每天,客户从 B 切换到 A 的概率为 0.1
输入:market_share=[0.4,0.6]
,
switch_prob = [[.8,.2][.1,.9]]
输出:[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]
。
我不明白我哪里错了?如果有什么不对的地方,那一定是我对问题的理解。请提供您的想法。
在示例中,他们演示了一个简单的案例,即只有两个竞争对手。如果还有更多呢?让我们说三个 -
A、B、C
。我认为输入必须以[[0.1, 0.3, 0.6]..]
的形式提供转换概率,因为A
可能会失去其客户给B
以及C
并且会有很多这样的实例。现在,我必须计算至少两家公司的市场份额,第三家将是(1-sum_of_all)
。在计算 B 的市场份额时,我将不得不计算它失去的客户以及获得的客户,公式为(current - lost + gained)
。 Gained 将是gain_from_A 和 gain_from_C
的总和。它是否正确?
最佳答案
根据我的评论,这个问题可以表示为矩阵方程。
“转换”矩阵的元素T(i, j)
(维度N x N
)定义如下:
i = j
(对角线):客户留在链i
的概率
i != j
(非对角线):链j
的客户转移到链i
的概率
这个矩阵的物理意义是什么?让市场份额状态由大小为 N
的向量 P(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)
大小为
N - 1
的向量Q(i)
包含P 的前
N - 1
个元素(i)大小为
N - 1
的向量R(i)
,这样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 |
请原谅鲁滨逊漂流记风格的格式 - 我稍后会尝试用 LaTeX 编写这些格式以提高可读性。
关于algorithm - 计算最终市场分布——竞争性编程,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/49684606/