Probability and Expected Value DP

DP states can store real-valued probabilities or expectations. We study a process with remaining work i:each move removes one unit, two units, or none, with fixed probability weights a, b, c. Zero is absorbing. The self-loop means a naive direct tabulation equation refers to itself; we first isolate that term algebraically. A supplementary finite-time probability program shows how adding a time dimension also breaks cyclic dependencies.

Prerequisites: Probability Fundamentals; Expected Value; tabulation; simple linear equations. Related existing lessons: Probability Fundamentals, Expected Value and Linearity of Expectation, Gaussian Elimination.

Build the idea

1. Recognize the repeated subproblems

   Enumerating random histories repeats the same remaining work and can involve arbitrarily many stays. Expected remaining time depends only on current i under independent identical outcome probabilities. Fixed nonnegative integer weights define p=a/T, q=b/T, r=c/T with T=a+b+c>0. A zero-progress process with positive work never absorbs and must not receive a finite expectation.

2. Define the state

   E[i] is expected additional moves to reach zero from remaining work i. E[0]=0. In the supplementary program, P[t][i] is probability of work i after exactly t moves, starting at n. These states answer different questions:an expectation over an unbounded stopping time versus absorption probability by a finite horizon. The absorbing state keeps any probability mass already at zero.

3. Derive the transition

   For i>0, first-step conditioning gives E[i]=1+pE[i−1]+qE[max(0, i−2)]+rE[i]. Rearrange to E[i]=(T+aE[i−1]+bE[max(0, i−2)])/(a+b). This is legal only if a+b>0. Probability transitions instead distribute mass to i−1, max(0, i−2), i in the next time layer; stays are then acyclic in t even though work i does not change.

   $$E\left[i\right]=(T+\mathrm{aE}[i-1]+\mathrm{bE}[\max (0,i-2)\left]\right)/(a+b)$$

4. Base cases and computation order

   Check T>0, otherwise output INVALID. If n>0 and a+b=0, output INFINITE. Otherwise fill i increasingly after solving the self-loop. The probability version starts P[0][n]=1, uses fresh rolling time rows and carries P[t][0] directly into P[t+1][0]. For n=0, the expected remaining moves are zero without any division.

5. Correctness and invariant

   First-step conditioning partitions outcomes by their known probabilities and the law of total expectation. Positive progress probability makes absorption time finite here:each successful event removes at least one unit and has finite geometric waiting time. The algebraically reduced dependencies are smaller work states, so induction is valid. More general cycles involving several different states require a coupled linear system or another justified method; self-reference is not resolved by merely caching a half-computed value.

6. Work the example

   For n=3 and weights (1,1,2), p=q=1/4, r=1/2. E[1]=2, E[2]=3, E[3]=4.5. The supplementary two-move absorption probability is 3/16=0.1875 from outcome pairs (1,2),(2,1),(2,2). These are approximate printed decimals, not an exact analytic claim about arbitrary stochastic systems.

   remaining i	0	1	2	3
   expected moves	0	2	3	4.5

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<iomanip>
int main(){
    int n;
    long long a,b,c;
    std::cin>>n>>a>>b>>c;
    if(a+b+c==0){
        std::cout<<"INVALID\n";
        return 0;
    }
    if(n>0&&a+b==0){
        std::cout<<"INFINITE\n";
        return 0;
    }
    std::vector<long double>expected(n+1);
    for(int i=1;i<=n;++i){
        expected[i]=((long double)(a+b+c)+a*expected[i-1]+b*expected[i>=2?i-2:0])/
            (a+b); // Solve the stay-state self-loop algebraically before tabulation.
    }
    std::cout<<std::fixed<<std::setprecision(6)<<expected[n]<<'\n';
}

Complexity analysis

Expectation:n+1 states, constant transitions, O(n) time/O(n) vector space, compressible to O(1). Supplementary probability:n+1 states per time layer, three transitions each, O(n·steps) time/O(n) rolling space with its smaller bounds. long double output has numerical error; it is not an exact rational result.

Example input and output

Read n a b c (0≤n≤100000, weights in 0..10^6). Outcome weights remove 1,2,0 work; work cannot go below zero, and zero is absorbing. Print approximate expected moves to six decimals, INFINITE for positive work with no progress, or INVALID when all weights are zero.

Input

3 1 1 2

Output

4.500000

For n=3 and weights (1,1,2), p=q=1/4, r=1/2. E[1]=2, E[2]=3, E[3]=4.5. The supplementary two-move absorption probability is 3/16=0.1875 from outcome pairs (1,2),(2,1),(2,2). These are approximate printed decimals, not an exact analytic claim about arbitrary stochastic systems.

Read n steps a b c (0≤n,steps≤1000,nonnegative weights≤10^6 and positive total). Same removal/stay model;print approximate probability of zero work after exactly steps moves.

#include<iostream>
#include<vector>
#include<iomanip>
#include<algorithm>
int main(){
    int n,steps;
    long long a,b,c;
    std::cin>>n>>steps>>a>>b>>c;
    if(a+b+c==0){
        std::cout<<"INVALID\n";
        return 0;
    }
    long double total=a+b+c;
    std::vector<long double>dp(n+1),next(n+1);
    dp[n]=1;
    for(int t=0;t<steps;++t){
        std::fill(next.begin(),next.end(),0);
        next[0]=dp[0];
        for(int i=1;i<=n;++i){
            next[i-1]+=dp[i]*a/total;
            next[std::max(0,i-2)]+=dp[i]*b/total;
            next[i]+=dp[i]*c/total;
        }
        dp.swap(next);
    } // Absorbed probability remains at state zero.
    std::cout<<std::fixed<<std::setprecision(6)<<dp[0]<<'\n';
}

Input

3 2 1 1 2

Output

0.187500

Two moves absorb from work three for outcomes (1,2),(2,1),(2,2),each of probability 1/16. Absorbed mass stays at zero,so this also means absorption by the horizon.

Complexity: O(n·steps) time,O(n) rolling probability arrays;three outcome updates per live state.

Practical applications

Use for stochastic completion times, random walks with a well-founded state reduction and finite-horizon event probabilities. Detect nonabsorbing classes before assuming a finite expectation. Gaussian elimination from Mathematics can solve suitable finite coupled expectation systems when a proper finite solution exists.

Check your understanding

Why can the original expectation equation not be used as a plain earlier-state assignment?

Put it into practice

Compare small instances with exact rational recurrences and finite-time probability enumeration.