# Markov chain decision problem, understanding solution a)

During any period, a potential customer arrives at a certain facility with probability $$1/2$$. If there are already two people at the facility (including the one being served), the potential customer leaves the facility immediately and never returns. However, if there is one person or less, he enters the facility and becomes an actual customer. The manager of the facility has two types of service configurations available. At the beginning of each period, a decision must be made on which configuration to use. If she uses her “slow” configuration at a cost of $$\3$$ and any customers are present during the period, one customer will be served and leave the facility with probability $$3/5$$. If she uses her “fast” configuration at a cost of $$\9$$ and any customers are present during the period, one customer will be served and leave the facility with probability $$4/5$$. The probability of more than one customer arriving or more than one customer being served in a period is zero. A profit of \$50 is earned when a customer is served.

(a) Formulate the problem of choosing the service configuration period by period as a Markov decision process. Identify the states and decisions. For each combination of state and decision, find the expected net immediate cost (subtracting any profit from serving a customer) incurred during that period.

Solution

Let the states $$i=0,1,2$$ be the number of customers at the facility. There are two possible actions when the facility has one or two customers. Let decision $$1$$ be to use the slow configuration and decision $$2$$ be to use the fast configuration. Also let $$C_{ij}$$ denote the expected net immediate cost of using decision $$j$$ in state $$i$$.

Then, $$C_{11}=C_{21}=3-(3/5)*50=-27$$

$$C_{12}=C_{22}=9-(4/5)*50=-31$$

$$C_{01}=3$$

$$C_{02}=9$$

Why is this the solution? I can understand the solution statement but not the $$C_{ij}'s$$. Why are those the subindex?

Also how will the matrix be defined?