Steven R. Dunbar
Department of Mathematics
203 Avery Hall
Lincoln, NE 68588-0130
http://www.math.unl.edu
Voice: 402-472-3731
Fax: 402-472-8466

Stochastic Processes and

__________________________________________________________________________

A Stochastic Process Model of Cash Management

_______________________________________________________________________

Note: These pages are prepared with MathJax. MathJax is an open source JavaScript display engine for mathematics that works in all browsers. See http://mathjax.org for details on supported browsers, accessibility, copy-and-paste, and other features.

_______________________________________________________________________________________________ ### Rating

Mathematically Mature: may contain mathematics beyond calculus with proofs.

_______________________________________________________________________________________________ ### Section Starter Question

Suppose that you have a stock of 5 units of a product. It costs you $r$ dollars per unit of product to hold the product for a week. You sell and eliminate from the stock one unit of product per week. What is the total cost of holding the product? Now suppose that the amount of product sold is $0$ or $1$ each week, determined by a coin-tossing game. How would you calculate the expected cost of holding the product?

_______________________________________________________________________________________________ ### Key Concepts

1. The reserve requirement is a bank regulation that sets the minimum reserves of cash a bank must hold on hand for customer deposits. An important question for the bank is: What is the optimal level of cash for the bank to hold?
2. We model the cash level with a sequence of cycles or games. Each cycle begins with $s$ units of cash on hand and ends with either a replenishment of cash, or a reduction of cash. In between these levels, the cash level is a stochastic process, speciﬁcally a coin-tossing game or random walk.
3. By solving a non-homogeneous diﬀerence equation we can determine the expected number of visits to an intermediate level in the random process.
4. Using the expected number of visits to a level we can model the expected costs of the reserve requirement as a function of the maximum amount to hold and the starting level after a buy or sell. Then we can minimize the expected costs with calculus to ﬁnd the optimal values of the maximum amount and the starting level.

__________________________________________________________________________ ### Vocabulary

1. The reserve requirement is a bank regulation that sets the minimum reserves of cash a bank must hold for customer deposits.
2. The mathematical expression ${\delta }_{sk}$ is the Kronecker delta

3. If $X$ is a random variable assuming some values including $k$, the indicator random variable is
${1}_{\left\{X=k\right\}}=\left\{\begin{array}{cc}1\phantom{\rule{1em}{0ex}}\hfill & X=k\hfill \\ 0\phantom{\rule{1em}{0ex}}\hfill & X\ne k.\hfill \end{array}\right\$

The indicator random variable indicates whether a random variable assumes a value, or is in a set. The expected value of the indicator random variable is the probability of the event.

__________________________________________________________________________ ### Mathematical Ideas

#### Background

The reserve requirement is a bank regulation that sets the minimum reserves of cash a bank must hold on hand for customer deposits. This is also called the Federal Reserve requirement or the reserve ratio. These reserves exist so banks can satisfy cash withdrawal demands. The reserves also help regulate the national money supply. Speciﬁcally in 2016 the Federal Reserve regulations require that the ﬁrst $15.2 million are exempt from reserve requirements. A 3 percent reserve ratio applies to net transaction accounts (a net total of certain account types deﬁned by the Federal Reserve) over$15.2 million up to and including $110.2 million. A 10 percent reserve ratio applies to net transaction accounts in excess of$110.2 million. The Federal Reserve adjusts these amounts from time to time.

Of course, bank customers are frequently depositing and withdrawing money so the amount of money for the reserve requirement is constantly changing. If customers deposit more money, the cash on hand exceeds the reserve requirement. The bank would like to put the excess cash to work, perhaps by buying Treasury bills. If customers withdraw cash, the available cash can fall below the required amount to cover the reserve requirement so the bank gets more cash, perhaps by selling Treasury bills.

The bank has a dilemma: buying and selling the Treasury bills has a transaction cost, so the bank does not want to buy and sell too often. On the other hand, the bank could put excess cash to use by loaning it out, and so the bank does not want to have too much cash idle. What is the optimal level of cash that signals a time to buy, and how much should the bank buy or sell?

We assume for a simple model that a bank’s cash level ﬂuctuates randomly as a result of many small deposits and withdrawals. We model this by dividing time into successive, equal length periods, each of short duration. The periods might be weekly, the reporting period the Federal Reserve Bank requires for some banks. In each time period, assume the reserve randomly increases or decreases one unit of cash, perhaps measured in units of $100,000, each with probability $1∕2$. That is, in period $n$, the change in the bank’s reserves is The equal probability assumption simpliﬁes calculations for this model. It is possible to relax the assumption to the case $p\ne q$, but we will not do this here. Let ${T}_{0}=s$ be the initial cash on hand. Then ${T}_{n}={T}_{0}+{\sum }_{j=1}^{n}{Y}_{j}$ is the total cash on hand at period $n$. The bank will intervene if the reserve gets too small or too large. Again for simple modeling, if the reserve level drops to zero, the bank sells assets such as Treasury bonds to replenish the reserve back up to $s$. If the cash level ever increases to $S$, the bank buys Treasury bonds to reduce the reserves to $s$. What we have modeled here is a version of the Gambler’s Ruin, except that when this “game” reaches the “ruin” or “victory” boundaries, $0$ or $S$ respectively, the “game” immediately restarts again at $s$. Now the cash level ﬂuctuates in a sequence of cycles or games. Each cycle begins with $s$ units of cash on hand and ends with either a replenishment of cash, or a reduction of cash. See Figure 1 for a simple example with $s=2$ and $S=5$. Figure 1: Several typical cycles in a model of the reserve requirement. #### Mean number of visits to a particular state Now let $k$ be one of the possible reserve states with $0 and let ${W}_{sk}$ be the expected number of visits to the level $k$ up to the ending time of the cycle starting from $s$. A formal mathematical expression for this expression is ${W}_{sk}=𝔼\left[\sum _{j=1}^{N-1}{1}_{\left\{{T}_{j}=k\right\}}\right]$ where ${1}_{\left\{{T}_{j}=k\right\}}$ is the indicator random variable where ${1}_{\left\{{T}_{j}=k\right\}}=\left\{\begin{array}{cc}1\phantom{\rule{1em}{0ex}}\hfill & {T}_{j}=k\hfill \\ 0\phantom{\rule{1em}{0ex}}\hfill & {T}_{j}\ne k.\hfill \end{array}\right\$ Note that the inner sum is a random sum, since it depends on the length of the cycle $N$, which is cycle dependent. Then using ﬁrst-step analysis ${W}_{sk}$ satisﬁes the equations ${W}_{sk}={\delta }_{sk}+\frac{1}{2}{W}_{s-1,k}+\frac{1}{2}{W}_{s+1,k}$ with boundary conditions ${W}_{0k}={W}_{Sk}=0$. The term ${\delta }_{sk}$ is the Kronecker delta The explanation of this equation is very similar to the derivation of the equation for the expected duration of the coin-tossing game. The terms $\frac{1}{2}{W}_{s-1,k}+\frac{1}{2}{W}_{s+1,k}$ arise from the standard ﬁrst-step analysis or expectation-by-conditioning argument for ${W}_{sk}$. The non-homogeneous term in the prior expected duration equation (which is $+1$) arises because the game will always be at least $1$ step longer after the ﬁrst step. In the current equation, the ${\delta }_{sk}$ non-homogeneous term arises because the number of visits to level $k$ after the ﬁrst step will be $1$ more if $k=s$ but the number of visits to level $k$ after the ﬁrst step will be $0$ more if $k\ne s$. For the ruin probabilities, the diﬀerence equation was homogeneous, and we only needed to ﬁnd the general solution. For the expected duration, the diﬀerence equation was non-homogeneous with a non-homogeneous term which was the constant $1$, making the particular solution reasonably easy to ﬁnd. Now the non-homogeneous term depends on the independent variable, so solving for the particular solution will be more involved. First we ﬁnd the general solution ${W}_{sk}^{h}$ to the homogeneous linear diﬀerence equation ${W}_{sk}^{h}=\frac{1}{2}{W}_{s-1,k}^{h}+\frac{1}{2}{W}_{s+1,k}^{h}.$ This is easy, we already know that it is ${W}_{sk}^{h}=A+Bs$. Then we must ﬁnd a particular solution ${W}_{sk}^{p}$ to the non-homogeneous equation ${W}_{sk}^{p}={\delta }_{sk}+\frac{1}{2}{W}_{s-1,k}^{p}+\frac{1}{2}{W}_{s+1,k}^{p}.$ For purposes of guessing a plausible particular solution, temporarily re-write the equation as $-2{\delta }_{sk}={W}_{s-1,k}^{p}-2{W}_{sk}^{p}+{W}_{s+1,k}^{p}.$ The expression on the right is a centered second diﬀerence. For the prior expected duration equation, we looked for a particular solution with a constant centered second diﬀerence. Based on our experience with functions it made sense to guess a particular solution of the form $C+Ds+E{s}^{2}$ and then substitute to ﬁnd the coeﬃcients. Here we seek a function whose centered second diﬀerence is $0$ except at $k$ where the second diﬀerence jumps to $1$. This suggests the particular solution is piecewise linear, say In the exercises, we verify that the coeﬃcients of the function are We can write this as ${W}_{sk}^{p}=-2max\left(s-k,0\right)$ Then solving for the boundary conditions, the full solution is ${W}_{sk}=2\left[s\left(1-k∕S\right)-max\left(s-k,0\right)\right].$ #### Expected Duration and Expected Total Cash in a Cycle Consider the ﬁrst passage time $N$ when the reserves ﬁrst reach $0$ or $S$, so that cycle ends and the bank intervenes to change the cash reserves. The value of $N$ is a random variable, it depends on the sample path. We are ﬁrst interested in ${D}_{s}=𝔼\left[N\right]$, the expected duration of a cycle. From the previous section we already know ${D}_{s}=s\left(S-s\right)$. Next, we need the mean cost of holding cash on hand during a cycle $i$, starting from amount $s$. Call this mean ${W}_{s}$. Let $r$ be the cost per unit of cash, per unit of time. We then obtain the cost by weighting ${W}_{sk}$, the mean number of times the cash is at number of units $k$ starting from $s$, multiplying by $k$, multiplying by the factor $r$ and summing over all the available amounts of cash: $\begin{array}{llll}\hfill {W}_{s}& =\sum _{k=1}^{S-1}rk{W}_{sk}\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill & =2\left[\frac{s}{S}\sum _{k=1}^{S-1}rk\left(S-k\right)-\sum _{k=1}^{s-1}rk\left(s-k\right)\right]\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill & =2\left[\frac{s}{S}\left[\frac{rS\left(S-1\right)\left(S+1\right)}{6}\right]-\frac{rs\left(s-1\right)\left(s+1\right)}{6}\right]\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill & =r\frac{s}{3}\left[{S}^{2}-{s}^{2}\right].\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\end{array}$ These results are interesting and useful in their own right as estimates of the length of a cycle and the expected cost of cash on hand during a cycle. Now we use these results to evaluate the long run behavior of the cycles. Upon resetting the cash at hand to $s$ when the amount of cash reaches $0$ or $S$, the cycles are independent of each of the other cycles because of the assumption of independence of each step. Let $K$ be the ﬁxed cost of the buying or selling of the treasury bonds to start the cycle, let ${N}_{i}$ be the random length of the cycle $i$, and let ${R}_{i}$ be the total cost of holding cash on hand during cycle $i$. Then the cost over $n$ cycles is $nK+{R}_{1}+\cdots +{R}_{n}$. Divide by $n$ to ﬁnd the average cost but we have another expression for the expectation $𝔼\left[{R}_{i}\right]$, Likewise the total length of $n$ cycles is ${N}_{1}+\cdots +{N}_{n}$. Divide by $n$ to ﬁnd the average length, These expected values allow us to calculate the average costs Then $𝔼\left[{R}_{i}\right]={W}_{s}$ and $𝔼\left[{N}_{i}\right]=s\left(S-s\right)$. Therefore Simplify the analysis by setting $x=s∕S$ so that the expression of interest is Remark. Aside from being a good thing to non-dimensionalize the model as much as possible, it also appears that optimizing the original long run cost average in the original variables $S$ and $s$ is messy and diﬃcult. This of course would not be known until you had tried it. However, knowing the optimization is diﬃcult in variables $s$ and $S$ additionally motivates making the transformation to the non-dimensional ratio $x=s∕S$. Now we have a function in two variables that we wish to optimize. Take the partial derivatives with respect to $x$ and $S$ and set them equal to $0$, then solve, to ﬁnd the critical points. The results are that $\begin{array}{llll}\hfill {x}_{\text{opt}}& =\frac{1}{3}\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill {S}_{\text{opt}}& =3{\left(\frac{3K}{4r}\right)}^{\frac{1}{3}}.\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\end{array}$ That is, the optimal value of the maximum amount of cash to keep varies as the cube root of the cost ratios, and the reset amount of cash is $1∕3$ of that amount. #### Criticism of the model The ﬁrst test of the model would be to look at the amounts $S$ and $s$ for well-managed banks and determine if the banks are using optimal values. That is, one could do a statistical survey of well-managed banks and determine if the values of $S$ vary as the cube root of the cost ratio, and if the restart value is $1∕3$ of that amount. Of course, this assumes that the model is valid and that banks are following the predictions of the model, either consciously or not. This model is too simple and we could modify in a number of ways. One change might be to change the reserve requirements to vary with the level of deposits, just as the 2010 Federal Reserve requirements vary. Adding additional reserve requirement levels to the current model adds a level of complexity, but does not substantially change the level of mathematics involved. The most important change would be to allow the changes in deposits to have a continuous distribution instead of jumping up or down by one unit in each time interval. Modiﬁcation to continuous time would make the model more realistic instead of changing the cash at discrete time intervals. The assumption of statistical independence from time step to time step is questionable, and so could also be relaxed. All these changes require deeper analysis and more sophisticated stochastic processes. #### Sources This section is adapted from: Section 6.1.3 and 6.2, pages 157-164 in An Introduction to Stochastic Modeling, . ### Algorithms, Scripts, Simulations Set the top boundary state value and the start and reset state value. Set the probability of a transition of an interior state to the next higher state. Set the number of steps in the Markov chain. Create the Markov chain transition probability matrix. For this Markov chain, the transition probability matrix is tridiagonal, with $0$ on the main diagonal, $p$ on the upper diagonal and $1-p$ on the lower diagonal. For the boundary states, the transition probability is $1$ to the start or reset state. Initialize the vector holding the number of visits to each state, the number of cycles from start to reset, and the length of each cycle. For each transition, choose a random value $u$ chosen from a uniform distribution on $\left(0,1\right)$. Starting from an initialized cumulative probability of $0$, compute the cumulative probability of the current state’s transition probability distribution. Compare the cumulative probability to $u$ until the cumulative probability exceeds $u$. This is the new state. Update the number of visits to each state, the number of cycles from start to reset, and the length of each cycle and at the end of a cycle compute the average number of visit and the average length of the cycle. Print the average number of visits, and compare to the theoretical number of visits, Or for cash management, compute the actual cash management cost and the theoretical cash management value. #### Markov Chain Algorithm Geogebra R 1n <- 10 # Top boundary, number of states 0..n is n+1 2s <- 5 # Start and Reset state number 1 <= s <= n-1 3p <- 1/2 4steps <- 1000 5 6diag.num <- outer(seq(1,n+1),seq(1,n+1), "-") 7# diag.num is a matrix whose ith lower diagonal equals i, opposite for upper diagonal 8T <- mat.or.vec(n+1,n+1) 9# mat.or.vec creates an nr by nc zero matrix if nc is greater than 1 10# Also remember that matrices in R are 1-based, so need n+1 states, 0..n 11T[diag.num == -1] <- p 12T[diag.num == 1] <- 1-p 13T[1,2] <- 0; T[1,s+1] <- 1; 14T[n+1,n] <- 0; T[n+1,s+1] <- 1; 15 16# vector to hold the count of visits to each state during a cycle 17count <- mat.or.vec(1, n+1) 18# Initialize the number of cycles 19numberCycles <- 0 20# Initialize the length of the cycle 21cycleLength <- 0 22# Start in the state s 23state = s+1 24 25# Make steps through the markov chain 26for (i in 1:steps) 27{ 28 x = 0; 29 u = runif(1, 0, 1); 30 31 32 newState = state; 33 for (j in 1:ncol(T)) 34 { 35 x = x + T[state, j]; 36 if (x >= u) 37 { 38 newState = j; 39 break; 40 } 41 } 42 ## newState <- sample(1:ncol(T), 1, prob=T[state,]) 43 state = newState; 44 count[state] <- count[state] + 1 45 cycleLength <- cycleLength + 1 46 47 if (state == n+1 || state == 1) { 48 numberCycles <- numberCycles + 1 49 avgVisits <- count/numberCycles 50 avgCycleLength <- i/numberCycles 51 } 52} 53 54Wsk <- avgVisits 55theoreticalWsk <- 2*( s*(1-(0:n)/n) - pmax( s - (0:n),0) ); 56 57cat(sprintf("Average number of visits to each state in a cycle: \n ")) 58cat(Wsk) 59cat("\n\n") 60cat(sprintf("Theoretical number of visits to each state in a cycle: \n ")) 61cat(theoreticalWsk) 62cat("\n") 63 Octave 1n = 10; # Top boundary, number of states 0..n is n+1 2s = 5; # Start and Reset state number 1 <= s <= n-1 3p = 1/2; 4steps = 1000; 5rate = 1.0; 6K = 2; # Charge or cost to reset the Markov chain 7 8T = diag( p*ones(1,n), 1) + diag( (1-p)*ones(1,n), -1); 9T(1,2) = 0; T(1,s+1) = 1; 10T(n+1,n) = 0; T(n+1,s+1) = 1; 11 12# vector to hold the count of visits to each state during a cycle 13count = zeros(1, n+1); 14# Initialize the cyclelength 15numberCycles = 0; 16# Start in the state s 17state = s+1; 18 19# Make steps through the markov chain 20for i = 1:steps 21 x = 0; 22 u = rand(1, 1); 23 24 newState = state; 25 for j = 1:n+1 26 x = x + T(state, j); 27 if (x >= u) 28 newState = j; 29 break; 30 endif 31 endfor 32 ## newState = sample(1:ncol(T), 1, prob=T[state,]) 33 state = newState; 34 count(state) = count(state) + 1; 35 36 if (state == n+1 || state == 1) 37 numberCycles = numberCycles + 1; 38 avgVisits = count/numberCycles; 39 avgCycleLength = i/numberCycles; 40 endif 41endfor 42 43disp("Average number of visits to each state in a cycle:") 44Wsk = avgVisits 45disp("Theoretical number of visits to each state in a cycle") 46theoreticalWsk = 2*( s*(1-(0:n)/n) - max( s - (0:n), zeros(1,n+1) ) ) 47 Perl 1use PDL::NiceSlice; 2 3$n     = 10;      # Top boundary, number of states 0..n is n+1
4$s = 5; # Start and Reset state number 1 <= s <= n-1 5$p     = 1 / 2;
6$steps = 1000; 7 8$T = zeroes( $n + 1,$n + 1 );
9$T ($s, 0 )  .= 1;    # note order of indices, note concat operation
10$T ($s, $n ) .= 1; 11for ($i = 1; $i <=$n - 1; $i++ ) { 12$T ( $i + 1,$i ) .= $p; 13$T ( $i - 1,$i ) .= 1 - $p; 14} 15 16# vector to hold the count of visits to each state during a cycle 17$count = zeroes( $n + 1 ); 18 19# Initialize the number of cycles 20$numberCycles = 0;
21
22# Start in the state s
23$state =$s;
24
25# Make steps through the markov chain
26for ( $i = 1;$i <= $steps;$i++ ) {
27    $x = 0; 28$u = rand(1);
29
30    for ( $j = 0;$j <= $n;$j++ ) {
31        $x =$x + $T ($j, $state ); 32 33 if ($x >= $u ) { 34$state = $j; 35 last; 36 } 37 38 } 39$count ($state)++; 40 if ($state == $n ||$state == 0 ) {
41        $numberCycles++; 42$avgVisits      = $count /$numberCycles;
43        $avgCycleLength =$i / $numberCycles; 44 } 45} 46 47$Wsk            = $avgVisits; 48$theoreticalWsk = 2 * (
49    $s * ( 1 - sequence($n + 1 ) / $n ) - maximum( 50 ( pdl( [$s - sequence( $n + 1 ), zeroes($n) ] ) )->xchg( 0, 1 )
51    )
52);
53
54print "Average number of visits to each state in a cycle:\n ", $Wsk, "\n"; 55print "Theoretical number of visits to each state in a cycle: \n", 56$theoreticalWsk, "\n";
57
SciPy
1import scipy
2
3n = 10;   # Top boundary, number of states 0..n is n+1
4s = 5;   # Start and Reset state number 1 <= s <= n-1
5p = 0.5;
6steps = 1000;
7
8T = scipy.diag( p*scipy.ones( n ), 1) + scipy.diag( (1-p)*scipy.ones( n ), -1);
9T[0,1] = 0; T[0,s] = 1;
10T[n,n-1] = 0; T[n,s] = 1;
11
12# vector to hold the count of visits to each state during a cycle
13count = scipy.zeros(n+1, float);
14# Initialize the cyclelength
15numberCycles = 0;
16# Start in the state s
17state = s;
18
19# Make steps through the markov chain
20for i in range(1, steps+1):
21    x = 0;
22    u = scipy.random.random(1);
23    newState = state;
24    for j in range(n+1):
25  x = x + T[state, j];
26  if (x >= u):
27      newState = j;
28      break;
29    ## newState = scipy.random.choice(1, 1, prob=T[state,])
30    state = newState;
31    count[state] = count[state] + 1;
32
33    if (state == n or state == 0):
34        numberCycles = numberCycles + 1;
35        avgVisits = count/numberCycles;
36        avgCycleLength = i/numberCycles;
37
38Wsk = avgVisits
39theoreticalWsk = 2*(  s*(1-scipy.arange(0,n+1,dtype=float)/n) - scipy.maximum(s-scipy.arange(0,n+1), scipy.zeros(n+1, int) ) )
40print "Average number of visits to each state in a cycle:\n ", Wsk
41print "Theoretical number of visits to each state in a cycle: \n", theoreticalWsk

#### Cash Management Algorithm

R
1n <- 10   # Top boundary, number of states 0..n is n+1
2s <- 5   # Start and Reset state number 1 <= s <= n-1
3p <- 1/2
4steps <- 1000
5rate <- 1.0
6K <- 2   # Charge or cost to reset the Markov chain
7
8diag.num <- outer(seq(1,n+1),seq(1,n+1), "-")
9# diag.num is a matrix whose ith lower diagonal equals i, opposite for upper diagonal
10T <- mat.or.vec(n+1,n+1)
11# mat.or.vec creates an nr by nc zero matrix if nc is greater than 1
12# Also remember that matrices in R are 1-based, so need n+1 states, 0..n
13T[diag.num == -1] <- p
14T[diag.num == 1] <- 1-p
15T[1,2] <- 0; T[1,s+1] <- 1;
16T[n+1,n] <- 0; T[n+1,s+1] <- 1;
17
18# vector to hold the count of visits to each state during a cycle
19count <- mat.or.vec(1, n+1)
20# Initialize the number of cycles
21numberCycles <- 0
22# Initialize the total cost of the cashmanagement
23totalCost <- 0
24# Start in the state s
25state = s+1
26
27# Make steps through the markov chain
28for (i in 1:steps)
29{
30    x = 0;
31    u = runif(1, 0, 1);
32
33    newState = state;
34    for (j in 1:ncol(T))
35    {
36  x = x + T[state, j];
37  if (x >= u)
38  {
39      newState = j;
40      break;
41  }
42    }
43    ## newState <- sample(1:ncol(T), 1, prob=T[state,])
44    state = newState;
45    count[state] <- count[state] + 1
46
47    if (state == n+1 || state == 1) {
48        numberCycles <- numberCycles + 1
49        totalCost <- K + totalCost
50    } else {
51        totalCost <- rate*(state-1) + totalCost
52    }
53}
54
55avgCost <- totalCost/steps
56theoreticalAvgCost <- ( K + (1/3)*(rate*s*(n^2 - s^2)) )/( s*(n-s) )
57
58cat(sprintf("Average cost: \n "))
59cat(avgCost)
60cat("\n\n")
61cat(sprintf("Theoretical average cost: \n "))
62cat(theoreticalAvgCost)
63cat("\n")
64
Octave
1n = 10;   # Top boundary, number of states 0..n is n+1
2s = 5;   # Start and Reset state number 1 <= s <= n-1
3p = 1/2;
4steps = 1000;
5rate = 1.0;
6K = 2;   # Charge or cost to reset the Markov chain
7
8T = diag( p*ones(1,n), 1) + diag( (1-p)*ones(1,n), -1);
9T(1,2) = 0; T(1,s+1) = 1;
10T(n+1,n) = 0; T(n+1,s+1) = 1;
11
12# vector to hold the count of visits to each state during a cycle
13count = zeros(1, n+1);
14# Initialize the number of cycles
15numberCycles = 0;
16# Initialize the total cost of the cashmanagement
17totalCost = 0;
18# Start in the state s
19state = s+1;
20
21# Make steps through the markov chain
22for i = 1:steps
23    x = 0;
24    u = rand(1, 1);
25
26    newState = state;
27    for j = 1:n+1
28  x = x + T(state, j);
29  if (x >= u)
30      newState = j;
31      break;
32  endif
33    endfor
34    ## newState = sample(1:ncol(T), 1, prob=T[state,])
35    state = newState;
36    count(state) = count(state) + 1;
37
38    if (state == n+1 || state == 1)
39        numberCycles = numberCycles + 1;
40        totalCost = K + totalCost;
41    else
42        totalCost = rate*(state-1) + totalCost;
43    endif
44endfor
45
46disp("Average cost:")
47avgCost = totalCost/steps
48disp("Theoretical average cost:")
49theoreticalAvgCost = ( K + (1/3)*(rate*s*(n^2 - s^2)) )/( s*(n-s) )
50
Perl
1use PDL::NiceSlice;
2
3$n = 10; # Top boundary, number of states 0..n is n+1 4$s     = 5;       # Start and Reset state number 1 <= s <= n-1
5$p = 1 / 2; 6$steps = 1000;
7
8$rate = 1.0; 9$K    = 2;        # Charge or cost to reset the Markov chain
10
11$T = zeroes($n + 1, $n + 1 ); 12$T ( $s, 0 ) .= 1; # note order of indices, note concat operation 13$T ( $s,$n ) .= 1;
14for ( $i = 1;$i <= $n - 1;$i++ ) {
15    $T ($i + 1, $i ) .=$p;
16    $T ($i - 1, $i ) .= 1 -$p;
17}
18
19# vector to hold the count of visits to each state during a cycle
20$count = zeroes($n + 1 );
21
22# Initialize the number of cycles
23$numberCycles = 0; 24 25# Initialize the total cost of the cashmanagement 26$totalCost = 0.0;
27
28# Start in the state s
29$state =$s;
30
31# Make steps through the markov chain
32for ( $i = 1;$i <= $steps;$i++ ) {
33    $x = 0; 34$u = rand(1);
35    for ( $j = 0;$j <= $n;$j++ ) {
36        $x =$x + $T ($j, $state ); 37 if ($x >= $u ) { 38$state = $j; 39 last; 40 } 41 } 42$count ($state)++; 43 if ($state == $n ||$state == 0 ) {
44        $numberCycles++; 45$totalCost = $K +$totalCost;
46    }
47    else {
48        $totalCost =$rate * $state +$totalCost;
49    }
50
51    $avgCost =$totalCost / $steps; 52 53$theoreticalAvgCost =
54          ( $K + ( 1. / 3. ) * ($rate * $s * ($n**2 - $s**2 ) ) ) 55 / ($s * ( $n -$s ) );
56}
57
58print "Average Cost: ",             $avgCost, "\n"; 59print "Theoretical Average Cost: ",$theoreticalAvgCost, "\n";
60
SciPy
1import scipy
2
3n = 10;   # Top boundary, number of states 0..n is n+1
4s = 5;   # Start and Reset state number 1 <= s <= n-1
5p = 0.5;
6steps = 1000;
7rate = 1.0
8K = 2.0
9
10T = scipy.diag( p*scipy.ones( n ), 1) + scipy.diag( (1-p)*scipy.ones( n ), -1);
11# square brakets okay, assignment not
12T[0,1] = 0; T[0,s] = 1;
13T[n,n-1] = 0; T[n,s] = 1;
14
15# vector to hold the count of visits to each state during a cycle
16count = scipy.zeros(n+1, float);
17# Initialize the cyclelength
18numberCycles = 0;
19# Initialize the total cost of the cashmanagement
20totalCost = 0.0
21# Start in the state s
22state = s;
23
24# Make steps through the markov chain
25for i in range(1, steps+1):
26    x = 0;
27    u = scipy.random.random(1);
28    newState = state;
29    for j in range(n+1):
30  x = x + T[state, j];
31  if (x >= u):
32      newState = j;
33      break;
34    ## newState = scipy.random.choice(1, 1, prob=T[state,])
35    state = newState;
36    count[state] = count[state] + 1;
37
38    if (state == n or state == 0):
39        numberCycles = numberCycles + 1;
40        totalCost = K + totalCost
41    else:
42        totalCost = rate*state + totalCost
43
44avgCost = totalCost/steps
45theoreticalAvgCost = ( K + (1./3.)*(rate*s*(n**2 - s**2)) )/( s*(n-s) )
46print "Average cost:\n ", avgCost
47print "Theoretical average cost: \n", theoreticalAvgCost

__________________________________________________________________________ ### Problems to Work for Understanding

1. Find a particular solution ${W}_{sk}^{p}$ to the non-homogeneous equation
${W}_{sk}^{p}={\delta }_{sk}+\frac{1}{2}{W}_{s-1,k}^{p}+\frac{1}{2}{W}_{s+1,k}^{p}.$

using the trial function

2. Show that $\begin{array}{llll}\hfill {W}_{s}& =\sum _{k=1}^{S-1}k{W}_{sk}\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill & =2\left[\frac{s}{S}\sum _{k=1}^{S-1}k\left(S-k\right)-\sum _{k=1}^{s-1}k\left(s-k\right)\right]\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill & =2\left[\frac{s}{S}\left[\frac{S\left(S-1\right)\left(S+1\right)}{6}\right]-\frac{s\left(s-1\right)\left(s+1\right)}{6}\right]\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill & =\frac{s}{3}\left[{S}^{2}-{s}^{2}\right]\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\end{array}$

You will need formulas for ${\sum }_{k=1}^{N}k$ and ${\sum }_{k=1}^{N}{k}^{2}$ or alternatively for ${\sum }_{k=1}^{N}k\left(M-k\right)$. These are easily found or derived.

1. For the long run average cost
$C=\frac{K+\left(1∕3\right)r{S}^{3}x\left(1-{x}^{2}\right)}{{S}^{2}x\left(S-x\right)}.$

ﬁnd $\partial C∕\partial x$.

2. For the long run average cost
$C=\frac{K+\left(1∕3\right)r{S}^{3}x\left(1-{x}^{2}\right)}{{S}^{2}x\left(1-x\right)}.$

ﬁnd $\partial C∕\partial S$.

3. Find the optimum values of $x$ and $S$.

__________________________________________________________________________ ### References

   H. M. Taylor and Samuel Karlin. An Introduction to Stochastic Modeling. Academic Press, third edition, 1998.

__________________________________________________________________________ 1. Milton Friedman: The Purpose of the Federal Reserve system.. The reaction of the Federal Reserve system at the beginning of the Great Depression.

__________________________________________________________________________

I check all the information on each page for correctness and typographical errors. Nevertheless, some errors may occur and I would be grateful if you would alert me to such errors. I make every reasonable eﬀort to present current and accurate information for public use, however I do not guarantee the accuracy or timeliness of information on this website. Your use of the information from this website is strictly voluntary and at your risk.

I have checked the links to external sites for usefulness. Links to external websites are provided as a convenience. I do not endorse, control, monitor, or guarantee the information contained in any external website. I don’t guarantee that the links are active at all times. Use the links here with the same caution as you would all information on the Internet. This website reﬂects the thoughts, interests and opinions of its author. They do not explicitly represent oﬃcial positions or policies of my employer.

Information on this website is subject to change without notice.