Implementing Probability and Expected Value DP
1. Implementing Probability DP
| Component | Description | Usage |
|---|---|---|
| State Definition | Defines the probability state at each step, often represented as P(i) or E(i) |
Used to track the probability of reaching a state or achieving an outcome |
| Transition Probabilities | Represents the probability of moving from one state to another, P(i → j) |
Used in recurrence relations to compute expected values |
| Base Cases | Initial probabilities or expected values for terminal states | Essential for dynamic programming recursion to terminate |
| Recurrence Relation | Formula connecting current state to previous states, e.g., E(i) = Σ P(i → j) * E(j) |
Core logic for computing expected values or probabilities |
Example: Expected Value of Dice Roll
const expectedValue = (1/6) * 1 + (1/6) * 2 + (1/6) * 3 + (1/6) * 4 + (1/6) * 5 + (1/6) * 6;
console.log(expectedValue); // 3.5Example: Probability of Coin Toss Sequence
const prob = (1/2) * (1/2) * (1/2); // Three heads in a row
console.log(prob); // 0.125
Note: Probability DP is often used in game theory, decision trees, and stochastic processes where outcomes depend on chance.
2. Solving Dice Throw Problems
| Problem | Description | Solution Approach | Time Complexity |
|---|---|---|---|
| Number of dice | Given n dice each with k faces, find the number of ways to get sum S | Dynamic Programming - build up from smaller sums | O(n * S) |
| Probability of sum | Calculate probability of getting a specific sum with n dice | Use DP to count combinations, divide by total outcomes (k^n) | O(n * S) |
| Expected value | Calculate expected sum when rolling n dice with k faces | E(X) = n * (k+1)/2 | O(1) |
Example: Counting Ways to Get Sum
function countWays(n, k, sum) {
const dp = Array(n + 1).fill().map(() => Array(sum + 1).fill(0));
dp[0][0] = 1;
for (let i = 1; i <= n; i++) {
for (let j = i; j <= Math.min(i * k, sum); j++) {
for (let face = 1; face <= k && face <= j; face++) {
dp[i][j] += dp[i - 1][j - face];
}
}
}
return dp[n][sum];
}
// Example usage:
console.log(countWays(2, 6, 7)); // Output: 6
Example: Expected Value Calculation
function expectedValue(n, k) {
// Expected value of one die is (1 + 2 + ... + k) / k
const singleDieExpected = (k * (k + 1)) / (2 * k);
return n * singleDieExpected;
}
// Example usage:
console.log(expectedValue(3, 6)); // Output: 10.5
Note: For n dice with k faces, the minimum sum is n (all 1s) and maximum sum is n*k (all k's). The number of ways to get sum S can be computed using dynamic programming where dp[i][j] represents the number of ways to get sum j with i dice.
3. Calculating Expected Number of Steps
| Scenario | Formula | Notes |
|---|---|---|
| Simple Random Walk | E[X] = n * p |
Where n is steps, p is probability of success |
| Geometric Distribution | E[X] = 1/p |
Expected steps to first success |
| Markov Chain Absorbing State | E[X] = (1 - p) / p |
For a single absorbing state with probability p of transitioning |
Example: Expected Steps in a Random Walk
const expectedSteps = (n, p) => n * p;
console.log(expectedSteps(10, 0.5)); // Output: 5Example: Geometric Distribution
const expectedStepsToSuccess = (p) => 1 / p;
console.log(expectedStepsToSuccess(0.2)); // Output: 54. Implementing Random Walk Problems
| Component | Description | Implementation |
|---|---|---|
| State Representation | Represents the position in the random walk | currentPosition |
| Transition Function | Defines how to move to the next state | nextPosition = currentPosition + randomStep() |
| Step Size | Size of each move in the walk | stepSize = 1 |
Example: Simple Random Walk
function randomWalk(steps) {
let position = 0;
for (let i = 0; i < steps; i++) {
const step = Math.random() > 0.5 ? 1 : -1;
position += step;
}
return position;
}
console.log(randomWalk(10)); // Example output: 2Example: Random Walk with Bounds
function boundedRandomWalk(steps, min, max) {
let position = 0;
for (let i = 0; i < steps; i++) {
const step = Math.random() > 0.5 ? 1 : -1;
position = Math.max(min, Math.min(max, position + step));
}
return position;
}
console.log(boundedRandomWalk(20, -5, 5)); // Example output: 3
Note: In a random walk, each step is independent and determined by a probability distribution.
Key Concepts in Random Walks
- Position is updated based on random steps.
- Each step can be modeled as a Bernoulli trial.
- Expected position after n steps is 0 (assuming symmetric probabilities).
5. Solving Gambler's Ruin
The Gambler's Ruin problem is a classic probability problem where a gambler starts with some amount of money and bets on a game with a fixed probability of winning or losing. The goal is to determine the probability of reaching a target amount before going broke.
| Parameter | Description | Value |
|---|---|---|
| initialCapital | Initial amount of money the gambler has | 10 |
| targetCapital | Target amount of money to reach | 20 |
| winProbability | Probability of winning a single bet | 0.5 |
| betAmount | Fixed amount bet per round | 1 |
Example: Calculating Probability of Ruin
function gamblerRuinProbability(initialCapital, targetCapital, winProbability) {
if (winProbability === 0.5) {
// For fair game, use closed-form solution
return (targetCapital - initialCapital) / targetCapital;
} else {
const q = 1 - winProbability;
const p = winProbability;
const r = q / p;
return (Math.pow(r, initialCapital) - Math.pow(r, targetCapital)) / (1 - Math.pow(r, targetCapital));
}
}
const prob = gamblerRuinProbability(10, 20, 0.5);
console.log(`Probability of reaching $20 before going broke: ${prob.toFixed(2)}`);
Note: For a fair game (p = 0.5), the probability of reaching the target before going broke is simply
(targetCapital - initialCapital) / targetCapital.
Example: Simulating Gambler's Ruin
function simulateGamblerRuin(initialCapital, targetCapital, winProbability, numSimulations = 10000) {
let successes = 0;
for (let i = 0; i < numSimulations; i++) {
let currentCapital = initialCapital;
while (currentCapital > 0 && currentCapital < targetCapital) {
if (Math.random() < winProbability) {
currentCapital += 1;
} else {
currentCapital -= 1;
}
}
if (currentCapital === targetCapital) {
successes++;
}
}
return successes / numSimulations;
}
const simProb = simulateGamblerRuin(10, 20, 0.5, 10000);
console.log(`Simulated probability: ${simProb.toFixed(2)}`);Solving Gambler's Ruin
- For a fair game (p = 0.5), use the closed-form formula:
(targetCapital - initialCapital) / targetCapital - For an unfair game (p ≠ 0.5), use the general formula involving
r = q/p - Simulation can be used to verify results or when analytical solutions are complex
6. Finding Expected Value
| Method | Description | Formula | Notes |
|---|---|---|---|
| E[X] | Expected value of a random variable X | E[X] = Σ x * P(x) |
Sum over all possible values of X |
| E[X + Y] | Expected value of sum of two random variables | E[X + Y] = E[X] + E[Y] |
Linearity of expectation |
| E[cX] | Expected value of a constant times a random variable | E[cX] = c * E[X] |
Constant can be pulled out |
| E[X * Y] | Expected value of product of independent random variables | E[X * Y] = E[X] * E[Y] |
Only valid if X and Y are independent |
Example: Expected Value of Dice Roll
const diceRolls = [1, 2, 3, 4, 5, 6];
const probability = 1 / 6;
const expectedValue = diceRolls.reduce((sum, roll) => sum + (roll * probability), 0);
console.log(expectedValue); // 3.5
Example: Expected Value of Two Dice
const dice1 = [1, 2, 3, 4, 5, 6];
const dice2 = [1, 2, 3, 4, 5, 6];
const probability = 1 / 36;
let expectedSum = 0;
for (let d1 of dice1) {
for (let d2 of dice2) {
expectedSum += (d1 + d2) * probability;
}
}
console.log(expectedSum); // 7
Note: For independent random variables, the expected value of their product equals the product of their expected values.
7. Implementing Conditional Probability
| Concept | Formula | Description |
|---|---|---|
| P(A|B) | P(A ∩ B) / P(B) |
Conditional probability of A given B |
| P(A ∩ B) | P(A|B) * P(B) |
Joint probability of A and B |
Example: Calculating Conditional Probability
const P_A_and_B = 0.3;
const P_B = 0.5;
const P_A_given_B = P_A_and_B / P_B;
console.log(P_A_given_B); // 0.6
Note: Ensure P(B) > 0 for valid conditional probability.
Key Points
- Conditional probability measures the likelihood of an event given another event has occurred.
- Used in Bayesian inference and decision-making under uncertainty.
8. Solving Card Probability
| Card Deck | Properties | Notes |
|---|---|---|
| totalCards | 52 |
Total number of cards in a standard deck |
| suits | ["Hearts", "Diamonds", "Clubs", "Spades"] |
Four suits in a deck |
| ranks | ["A", "2", "3", "4", "5", "6", "7", "8", "9", "10", "J", "Q", "K"] |
Thirteen ranks per suit |
Example: Probability of Drawing a Royal Flush
const royalFlushCount = 4; // Only 4 possible royal flushes (one per suit)
const totalPossibleHands = 2598960; // Combinations of 5 cards from 52
const probability = royalFlushCount / totalPossibleHands;
console.log(probability); // ~0.000154%
Example: Expected Value of a Card Draw
const cardValues = {
"A": 1, "2": 2, "3": 3, "4": 4, "5": 5,
"6": 6, "7": 7, "8": 8, "9": 9, "10": 10,
"J": 11, "Q": 12, "K": 13
};
const expectedValue = Object.values(cardValues).reduce((sum, val) => sum + val, 0) / 13;
console.log(expectedValue); // ~7.0
Note: Expected value in card games often depends on game rules and hand values.
9. Calculating Expected Path Length
| Property | Description | Formula | Example |
|---|---|---|---|
| E[X] | Expected value of a random variable X | E[X] = Σ x * P(x) |
|
| E[X + Y] | Expected value of sum of two random variables | E[X + Y] = E[X] + E[Y] |
let expectedSum = expectedX + expectedY; |
| E[cX] | Expected value of a constant times a random variable | E[cX] = c * E[X] |
let expectedConstant = 3 * expectedX; |
Example: Expected Path Length in a Graph
const graph = {
'A': [{ to: 'B', weight: 2 }, { to: 'C', weight: 3 }],
'B': [{ to: 'D', weight: 4 }],
'C': [{ to: 'D', weight: 1 }],
'D': []
};
function expectedPathLength(graph, start, end) {
const queue = [[start, 0]];
let totalLength = 0;
let count = 0;
while (queue.length > 0) {
const [node, length] = queue.shift();
if (node === end) {
totalLength += length;
count++;
continue;
}
const neighbors = graph[node] || [];
for (const neighbor of neighbors) {
queue.push([neighbor.to, length + neighbor.weight]);
}
}
return count > 0 ? totalLength / count : 0;
}
console.log(expectedPathLength(graph, 'A', 'D'));10. Implementing Monte Carlo Methods
| Method | Description | Use Case | Notes |
|---|---|---|---|
| Monte Carlo Tree Search (MCTS) | Expands a tree of possible moves using random sampling to estimate node values. | Game-playing AI, decision trees with uncertainty | Uses UCB1 formula to balance exploration and exploitation |
| Value Iteration | Iteratively updates state values using expected rewards and transition probabilities. | Markov Decision Processes (MDPs) | Converges to optimal policy if transition probabilities are known |
| Policy Iteration | Alternates between policy evaluation and policy improvement steps. | MDPs with unknown transition probabilities | More efficient than value iteration in some cases |
Example: Simple Monte Carlo Roll Simulation
const rollDice = () => Math.floor(Math.random() * 6) + 1;
const monteCarloSimulation = (numRolls) => {
let sum = 0;
for (let i = 0; i < numRolls; i++) {
sum += rollDice();
}
return sum / numRolls;
};
console.log(monteCarloSimulation(10000)); // Expected ~3.5Example: Policy Evaluation with Monte Carlo
const policy = (state) => state < 5 ? 0 : 1; // 0 = stay, 1 = roll
const monteCarloPolicyEval = (policy, numEpisodes) => {
const values = {};
for (let i = 0; i < numEpisodes; i++) {
let state = 0;
const returns = [];
while (state < 10) {
const action = policy(state);
state += action === 0 ? 0 : Math.floor(Math.random() * 6) + 1;
returns.push(state);
}
returns.forEach((s, idx) => {
values[s] = (values[s] || 0) + returns[idx];
});
}
return values;
};
console.log(monteCarloPolicyEval(policy, 1000));
Note: Monte Carlo methods are particularly useful when the full model (transition probabilities) is unknown or intractable. They rely on sampling to estimate expected values.