title: Calculating final market distribution - competitive programming
body: <p>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.</p>
  
  <p><strong>Question</strong>: </p>
  
  <p>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. </p>
  
  <p>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? </p>
  
  <p><strong>Assumptions</strong>: Total market share is 1.0, probability that a customer switches is independent of other customers and days. </p>
  
  <p><strong>Example</strong>: 2 coffee chains: A and B market share of A: 0.4 market share of B: 0.6.</p>
  
  <p>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</p>
  
  <p><code>input: market_share=[0.4,0.6]</code>,</p>
  
  <p><code>switch_prob = [[.8,.2][.1,.9]]</code> </p>
  
  <p><code>output: [0.3333 0.6667]</code></p>
  
  <p><em>Everything till here is part of a question, I did not form the example or assumptions, they were given with the question.</em></p>
  
  <p><strong>My_attempt</strong>: In my understanding, switch probabilities indicate the probability of switching the from A to B. </p>
  
  <p>Hence, </p>
  
  <pre><code>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]
  </code></pre>
  
  <p>As stated earlier, expected answers are <code>[0.3333 0.6667]</code>.</p>
  
  <ol>
  <li><p>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.</p></li>
  <li><p>In the example, they demonstrated an easy case that there were only two competitors. What if there are more? Let us say three - <code>A, B, C</code>. I think input has to provide switch probabilities in the form <code>[[0.1, 0.3, 0.6]..]</code> because <code>A</code> can lose its customers to <code>B</code> as well as <code>C</code> and there would be many instances of that. Now, I will have to compute at least two companies market share, third one will be <code>(1-sum_of_all)</code>. And while computing B's market share, I will have to compute it's lost customers as well as gained and formula would be <code>(current - lost + gained)</code>. Gained will be sum of <code>gain_from_A and gain_from_C</code>. Is this correct? </p></li>
  </ol>