Calculation of the final market distribution - competitive programming

Question

I came across the following question while practicing competitive programming. I solved it manually, but I don’t know how to scale my approach.

Question :

N coffee chains compete for market share for a fierce advertising battle. Every day, the percentage of customers will be convinced to switch from one chain to another.

Given the current market share and daily probability of switching customers. If advertising works forever, what will be the final distribution of market share?

Assumptions . The total market share is 1.0, the probability that the client will switch does not depend on other clients and days.

Example : 2 coffee chains: market share A and B in A: 0.4 market share B: 0.6.

Every day, there is a chance that the client will switch from A to B. Every day, there is a chance that the client will switch from B to A

input: market_share=[0.4,0.6],

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

output: [0.3333 0.6667]

Everything, until here is part of the question, I did not make an example or assumptions, they were asked with a question.

My_attempt . In my opinion, switching probabilities indicate the probability of switching between A and B.

Hence,

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]

As said earlier, the expected answers [0.3333 0.6667].

• I don’t understand, where am I mistaken? If something is wrong, this should be my understanding of the issue. Please provide your thoughts.

• , . , ? - 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 -th 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 th)) . :

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 - 1, N - 1 P(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 |

---

, - LaTeX .