Calculating final market distribution - competitive programming

Question

I came across following question while practicing competitive programming. I solved it manually, kinda designing an approach, but my answer is wrong and I cannot imagine how to scale my approach.

Question:

N coffee chains are competing for market share by a fierce advertising battle. each day a percentage of customers will be convinced to switch from one chain to another.

Current market share and daily probability of customer switching is given. If the advertising runs forever, what will be the final distribution of market share?

Assumptions: Total market share is 1.0, probability that a customer switches is independent of other customers and days.

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

Each day, there is a 0.2 probability that a customer switches from A to B Each day, there is a 0.1 probability that a customer switches from B to A

input: market_share=[0.4,0.6],

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

output: [0.3333 0.6667]

Everything till here is part of a question, I did not form the example or assumptions, they were given with the question.

My_attempt: In my understanding, switch probabilities indicate the probability of switching the from A to 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 stated earlier, expected answers are [0.3333 0.6667].

1. I do not understand where am I wrong? If something is wrong, it has to be my understanding of the question. Please provide your thoughts.

2. In the example, they demonstrated an easy case that there were only two competitors. What if there are more? Let us say three - A, B, C. I think input has to provide switch probabilities in the form [[0.1, 0.3, 0.6]..] because A can lose its customers to B as well as C and there would be many instances of that. Now, I will have to compute at least two companies market share, third one will be (1-sum_of_all). And while computing B's market share, I will have to compute it's lost customers as well as gained and formula would be (current - lost + gained). Gained will be sum of gain_from_A and gain_from_C. Is this correct?

Answer 1

Following on from my comment, this problem can be expressed as a matrix equation.

---

The elements of the "transition" matrix, T(i, j) (dimensions N x N) are defined as follows:

• i = j (diagonal): the probability of a customer staying with chain i
• i != j (off-diagonal): the probability of a customer of chain j transferring to chain i

What is the physical meaning of this matrix? Let the market share state be represented by a vector P(i) of size N, whose i-th value is the market share of chain i. The vector P' = T * P is the next share state after each day.

With that in mind, the equilibrium equation is given by T * P = P, i.e. the final state is invariant under transition 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) |

---

However, this is unsolvable by itself - P can only be determined up to a number of ratios between its elements (the technical name for this situation escapes me - as MBo suggests it is due to degeneracy). There is an additional constraint that the shares add up to 1:

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

We can choose an arbitrary share value (say, the Nth one) and replace it with this expression. Multiplying out, the first row of the equation is:

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)

The equivalent equation for the second row is:

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

---

To summarize the general pattern, we define:

• A matrix S(i, j) (dimensions [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)
  

• A vector Q(i) of size N - 1 containing the first N - 1 elements of P(i)

• A vector R(i) of size N - 1, such that R(i) = -T(i, N)

The equation then becomes 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) |

Solving the above equation gives Q, which gives the first N - 1 share values (and of course the last one too from the constraint). Methods for doing so include Gaussian elimination and LU decomposition, both of which are more efficient than the naive route of directly computing Q = inv(S) * R.

Note that you can flip the signs in S and R for slightly more convenient evaluation.

---

The toy example given above turns out to be quite trivial:

| 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

---

An example for 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 |

---

Please forgive the Robinson Crusoe style formatting - I'll try to write these in LaTeX later for readability.