Showing posts with label Simulation. Show all posts
Showing posts with label Simulation. Show all posts

Friday, November 29, 2013

VBA Simulation of Shuffling and Distributing a Deck of Cards

Here's a simple VBA program that simulates shuffling and distributing a standard deck of 52 cards to 4 players. The program outputs the results in cells A1 through D13 of the current Excel spreadsheet, with the 4 rows corresponding to the 4 players' cards.
Sub ShuffleCards()
'This program simulates shuffling of a standard deck of 52 cards to 4 players
'Results are outputted in 4 columns in cells A1:D13

'H: heart, S: spades, D: diamod, C: club
'2 thru 10, J for jack, Q for queen, K for king, A for ace
'2H would be 2 of hearts, KD would be king of diamonds, etc.

'Creating
suits = Array("H", "S", "D", "C")
num = Array("2", "3", "4", "5", "6", "7", "8", "9", "10", "J", "Q", "K", "A")

Dim cards(0 To 51) As String
For i = 0 To 3
For j = 0 To 12
cards(13 * i + j) = num(j) & suits(i)
Next j
Next i

'Shuffling
For i = 1 To 1000
c1 = Int(52 * Rnd)
c2 = Int(52 * Rnd)
temp = cards(c1)
cards(c1) = cards(c2)
cards(c2) = temp
Next i
'Distributing
For k = 0 To 51
Cells(k Mod 13 + 1, Int(k / 13) + 1) = cards(k)
Next k
End Sub

The shuffling algorithm is to run through 1000 iterations of swapping two randomly chosen cards.

Tuesday, March 19, 2013

Simulation of Simplified Version of Showcase Showdown Using MATLAB

See previous related post: Showcase Showdown Analysis: Circular Reasoning and Oscillating Nash Equilibrium

In the show The Price Is Right, contestants spin the Big Wheel, which has 20 sections randomly distributed, from 5 cents to $1.00 in 5-cent increments. The objective is to get the highest amount without going over $1, with one initial spin and an optional second spin. Clearly the first contestant is at a disadvantage, as the later contestants simply opt for the second optional spin if the first spin is not enough. For the first contestant, there needs to be a strategy consisting of a critical value for the first spin, at or above which the second spin is not preferred, as the probability of going over is too high. It's also a discrete case, as the critical value can only be from 5 to 100, in increments of 5.

In the actual show, there are three contestants. For the sake for simplicity, only two contestants are assumed in this simulation. In the case of tie, rerun the trial. For each possible critical value from 5 to 100 cents, 1 million trials are run in this Monte Carlo simulation to determine the winning percentage of player 1 under that strategy.

Here's the graph with the critical point on the x-axis and the winning percentage on the y-axis:


The maximum occurs at critical value of 55, corresponding with a winning percentage of 45.55%. At a value of 50, the winning percentage is up there at 45.22%. Even closer is 45.52% at a value of 60. The winning percentage gradually tapers off. Even at a value of 70, the winning percentage is still at 44.25%. Here's the MATLAB script to generate the data and graph:
x = zeros(1,20);
y = zeros(1,20);

for crit = 1:20
    x(crit) = 5*crit;
    n = 1000000;
    win = zeros(1,n);

    for i = 1:n
        done = false;
        while ~done
            firstSpin = ceil(20*rand)*5;

            if firstSpin >= x(crit)
                playerOne = firstSpin;
            else
                playerOne = firstSpin + ceil(20*rand)*5;
            end

            if playerOne > 100
                playerOne = 0;
            end

            playerTwo = ceil(20*rand)*5;
            if playerTwo < playerOne
                playerTwo = playerTwo + ceil(20*rand)*5;
            end
            if playerTwo > 100
                playerTwo = 0;
            end

            if playerOne > playerTwo
                win(i) = 1;
                done = true;
            elseif playerOne < playerTwo
                done = true;
            end
        end
    end
    
    y(crit) = sum(win)/n;
end
plot(x,y); grid on; xlabel('player 1 critical point'); ylabel('player 1 winning percentage')

In the code above, simply vary the value of n to change the number of trials at each strategy. Of course, this optimal strategy will be different if the third contestant is taken into consideration in the actual game.

Thursday, March 7, 2013

Acceptance Rejection Method for Simulation

In simulation, use the acceptance rejection method to simulate a random variable X with density f(x), for which there is no direct method to use the inverse transformation to generate it. However, suppose that there is a known algorithm to generate random variable Y with density g(x) such that f(x) / g(x) is bounded, that is f(x) / g(x) ≤ c. To find c, take the derivative of f(x) / g(x) to find the maximum value. Here's the algorithm:
  1. Generate Y according to the known algorithm
  2. Generate U, the uniform distribution from 0 to 1
  3. If U ≤ f(Y) / c*g(Y), then set X = Y
  4. Otherwise, start all over
Note that to produce each copy of X, the loop runs until condition 3 is satisfied. In the end, c become the average number of runs to produce a copy of X. In the following, a random variable with f(x) = 2x*e^(-x^2) is generated using MATLAB. The chosen g(x) = e^(-x), so f(x) / g(x) = 2x*e(x-x^2), and the maximum value c turns out to be exactly 2. 

There's no way to verify that this method does indeed generate a random variable with the given f(x). Instead, to test the accuracy of the algorithm here, two values (a and b) are inputted at the end. The program first calculates the integral of f(x) from [a, b], or the probability that X falls between the range of [a, b]. Finally, the program uses the simulated copies of X to count the proportion of the copies of X that fell in that interval of [a, b]. The two values should be close to each other.
func = @(x) 2*x.*exp(-x.^2);
n = 100000;
results = zeros(1,n);
numTimes = zeros(1,n);

for i=1:n
    trialDone = false;
    count = 0;
    while ~trialDone
        count = count + 1;
        y = -log(rand);
        u = rand;
        if u <= y*exp(y-y^2)
            results(i) = y;
            trialDone = true;
        end
    end
    numTimes(i) = count;
end

a = input('Lower bound for x: ');
b = input('Upper bound for x: ');
disp 'Evaluated integral using f(x): ';
quad(func, a, b)
disp 'Simulated integral using acceptance / rejection method: ';
length(results(results>a & results
disp 'Average trial runs per simulated copy: '
mean(numTimes)

Choose values between 0 and 2.5 for a and b, for over 99.8% of the data are in that range. Upon running the script using different values, the calculated integral closely matches the frequency proportion obtained from the simulation technique using the acceptance rejection method. While this does not verify the accuracy of the method, it at least illustrates that the resultant output resembles what the expected output should be. Finally, the resultant average trial runs per simulated copy hovers closely to 2 as expected.

Sunday, March 3, 2013

Simulating Correlated Pairs of Normally Distributed Random Variables

See previous related article: Simulating Normal Distribution with Polar Method

The previous article walked through how to generate independent copies of normally distributed random variables using the polar method. Here's an extension of that on how to generate pairs of normally distributed variables with a certain correlation between them. Polar method is still used to generate the variables. Recall that correlation ρ = cov(x,y) / (σ_x*σ_y). Both x and y can have its own σ and μ values.

n = input('Input the number of copies: ');
u_x = input('Input the mean of x: ');
s_x = input('Input the standard deviation of x: ');
u_y = input('Input the mean of y: ');
s_y = input('Input the standard deviation of y: ');
p = input('Input the correlation between x and y: ');
x = zeros(1,n);
y = zeros(1,n);

for i = 1:n
    z1 = sqrt(-2*log(rand))*cos(2*pi*rand);
    z2 = sqrt(-2*log(rand))*sin(2*pi*rand);
    x(i) = s_x*z1+u_x;
    y(i) = s_y*p*z1+s_y*sqrt(1-p^2)*z2+u_y;
end

disp 'Calculated mean and standard deviation for x:';
[mean(x), std(x)]
disp 'Calculated mean and standard deviation for y:';
[mean(y), std(y)]
disp 'Calculated correlation between x and y:';
corr(x',y')

The middle block of the codes here is the most essential. Variables z1 and z2 denote two independent copies of N(0,1). One copy is then used to generate x1 as σ_x*z1 + μ_x. Then the correlated pair y1 is generated as σ_y*ρ*z1 + σ_y*sqrt(1-ρ^2)*z2 + μ_y. Note that the z1 term is used in generating x1 as well as y1. Furthermore, note that the middle term σ_y*sqrt(1-ρ^2)*z2 disappears when ρ = ±1.

Simulating Normal Distribution with Polar Method

The polar method allows for quick generation of normally distributed random variables. For each trial, generate r^2 as exponentially distributed with λ = 1/2, and θ uniformly distributed between 0 and 2π. Within each trial, in fact 2 independent copies of the normally distributed random variables are generated: Z1 = sqrt(r^2)*cos(θ) and Z2 = sqrt(r^2)*sin(θ), both with μ = 0 and σ = 1. For normally distributed random variables with different parameters of μ and σ, simply use the transformation σ*Z+μ.
n = input('Input the number of copies: ');
u = input('Input the mean: ');
s = input('Input the standard deviation: ');
results = zeros(1,n);
for i = 1:2:n
    rsq = -2*log(rand);
    theta = 2*pi*rand;
    results(i) = s*sqrt(rsq)*cos(theta)+u;
    results(i+1) = s*sqrt(rsq)*sin(theta)+u;
end
disp 'Calculated mean and standard deviation using the polar method:';
[mean(results), std(results)]

The program at the end calculates the μ and σ values of the n copies of the random variables created as a result of this simulation, stored in the array named "results."

Tuesday, January 29, 2013

Inverse Transform Demonstration with Excel VBA

Given F(x) = 1-e^(-λ*x) as the cumulative distribution function, the inverse transform gives -1/λ*ln(U) as the function that has F(x) as its cdf, where U is the uniform distribution from [0, 1]. Here, the following VBA codes allow users to visualize this transformation in Microsoft Excel.

Upon the execution of this procedure, the user inputs a value for lambda. Then 10,000 simulations are run, initially generating a random number from [0, 1] and then inputting that random number into -1/λ*ln(U), and outputting the result in column A. At the end of the execution, column C contains the different x values from 0 to the maximum, in increments of 0.001. Column D reflects the cdf by counting entries of A that are smaller than the corresponding x value. Finally, column E calculates the true value of 1-e^(-λ*x). The idea is that the outputs in columns D and E are similar.

Sub InverseTransform()
'Demonstrates inverse transform of the cdf F(x) = 1-e^(-lambda*x)
Columns("A:E").Clear
Range("B1").Value = 1# * InputBox("Enter a positive value for lambda: ", "Input", 2)

'10,000 simulation trials to be performed
'Transform of F(x) gives -1/lambda*ln(U), where U is uniform distribution [0,1]
For i = 1 To 10000
Cells(i, 1) = -1 / Range("B1").Value * Log(Rnd)
Next i

'Determine the maximum for the range of numbers to work with
Range("B2").FormulaR1C1 = "=MAX(C[-1])"

'To determine the cumulative probability density, use 0.001 gradient from 0 to the maximum value as the counter
i = 1
While i / 1000 <= Range("B2").Value
Cells(i, 3).Value = i / 1000
'In column D, count entries in column A that are smaller than the counter, then divide by the number of trials
Cells(i, 4).FormulaR1C1 = "=COUNTIF(C[-3],""<""&RC[-1])/10000"
'In column E, calculate the true value of 1-e^(-lambda*x)
Cells(i, 5).FormulaR1C1 = "=(1-EXP(0-R1C2*RC[-2]))"
i = i + 1
Wend
Range("B2").Clear
End Sub

After the execution of this procedure, the user can perform further analysis. Graphing columns C through E does reveal that values in columns D and E are similar, as the points almost completely overlap. Error calculations from those two columns illustrate a similar result that the inverse transform method takes a function F(x), exponential function in this case, to produce a function whose cdf is F(x).

Wednesday, January 23, 2013

Monte Carlo Simulation of Pi with MATLAB

Using Monte Carlo simulation, the value of π can be approximated as (1/n) * Σ(4*sqrt(1-U_i^2)), where n is a large number representing the number of simulation trials, and U_i represents the i-th trial result from a uniform distribution in [0,1], for 1 ≤ i ≤ n. The MATLAB codes to run this simulation is quite straightforward:

numTrials = 1000000000;    %number of simulation trials
count = 0;
for trial = 1:numTrials
    roll = rand;    %uniform distribution [0,1]
    count = count + 4*sqrt(1-roll^2);
end
sum(count)/numTrials

In this simulation, n = 1,000,000,000. The output of 3.1416 matches the value of pi in all 4 displayed decimal places.

Saturday, September 8, 2012

Toss Coin Until Head Appears Twice In a Row

Take a fair coin and toss it until a head appears twice in a row. There is no finite sample space for this experience, for it theoretically can go on infinitely. That said, the first few elements are: {H,H}, {T,H,H}, {T,T,H,H}, {H,T,H,H}. To determine the probability of tossing exactly 4 times, we can take the elements in the sample space that corresponds to only 4 tosses. In that case, they are {T,T,H,H}, {H,T,H,H}. The probability of tossing either combination is 1/16, and two such combination gives a total probability of 1/8.

To see the result simulated, the following codes on MATLAB can help to illustrate that with 1 million trials. Documentations are added to clarify the algorithm.
probability = 0.5;      %prob of tossing head
numTrials = 1000000;    %number of simulation trials
trialResults = zeros(1,numTrials);

for trial = 1:numTrials
    done = false;
    lastHead = false;
    toss = 0;
    while ~done         %this loop controls each trial
        roll = rand;
        toss = toss + 1;
        if roll < probability && lastHead
            trialResults(trial) = toss;
            done = true;    %each trial over when last trial was H, and this trial is also
        elseif roll < probability && ~lastHead
            lastHead = true;    %last trial was not H, but this trial is
        else
            lastHead = false;   %did not toss a H
        end
    end
end

sum(trialResults == 4) / numTrials

The results vary very little from 0.1250.

Friday, June 22, 2012

1-D Random Walk with Equal Probability

This is the absolutely fundamental case of random walk. Start from position 0 on an one-dimensional number line. One unit step is taken on each step, with equal probability of going to the left and the right. The number of times stopped on each position is kept track. What's the distribution like after many steps?

It turns out that because the probability of moving in either direction is independent of the current position, increasing the number of steps in each trial doesn't help to reduce much variance. Instead, "resetting" the trials back to position 0, while keeping and continuing the tracking, helps to yield a smoother distribution curve. For this exercise, 100,000 runs were simulated, each with 1 million steps. In another word, 1 million steps were simulated, the position reset to 0, another 1 million steps simulated, the position reset to 0, and so forth until 100,000 of such cycles were completed. Overall, that's 100 billion steps. Here was the result:

Upon extraction of variable values, the following useful data were attained:
  • Most extreme positive value landed on: 4,729
  • Most extreme negative value landed on: 4,900
  • Number of times landed on position 0: 79,820,608
  • Percentage of time position was between [-100, 100]: 15.07%
  • Percentage of time position was between [-500, 500]: 58.15%
  • Percentage of time position was between [-1000, 1000]: 85.00%
  • Percentage of time position was between [-2000, 2000]: 98.85%

Tuesday, April 10, 2012

Random Walk: Simulation Given Varying Grid Sizes

Related previous post: Random Walk: Foundational Codes

In the previous post, we saw the codes, both in Java and MATLAB, that calculate the number of unit steps in cardinal direction that would take to get to one corner to the other extreme corner of a 10 x 10 grid. The Java codes were altered to create a RandomWalk object class and a driver class. In the driver class, we tested for grid size of 2 to 101 inclusive, and for each size, ran 100,000 trials. The average of the 100K trials was computed for each size and the results are summarized here:

It shows that the size of the grid and the average number of steps follow a quadratic pattern. The high coefficient of determination (R^2) is actually quite deceptive for low values of the size. In fact, when the size is 11 or smaller, the equation's prediction differs by at least 5%. Here are the values for those sizes:

Grid Size Simulation Avg. Eqn. Prediction    Error
2 4.005 1113.372 276.986
3 18.020 961.017 52.330
4 44.527 836.168 17.779
5 85.095 738.825 7.682
6 141.726 668.988 3.720
7 214.755 626.657 1.918
8 305.839 611.832 1.001
9 414.232 624.513 0.508
10 542.374 664.700 0.226
11 690.416 732.393 0.061

For each of the 100 size, 100K trials were run. Each trial on average took just over 38K steps, upon considering this entire range of grid sizes. Overall, that's around 100*100K*38K = 380 billion iterations in this simulation. This simulation took just over 12 hours to finish running on Eclipse.

Simulation of Expected Wait Time

Related previous post: Expected Wait Time given Multiple Trains

In the previous post, a simulation with 100 million trials was run on MATLAB to verify that in a scenario of two trains running independently with frequency of 10 minutes, the expected waiting time until the earlier train is 10/3 minutes. This was the code in a .m script, along with added comments for explanation:
%We will run 100 million trials, results to be stored in an array
results = zeros(1,100000000);

for i=1:100000000
    %Initiate the variable 'lowest' at 20 for now
    %It will eventually record the time to the earlier train
    %sure be less than 20
    lowest = 20;
   
    %Let both trains start at a random time t=(0,10)
    %This is the first round of the trains
    train1Start = 10*rand;
    train2Start = 10*rand;
   
    %There will be trains 10 minutes ahead, representing the second round
    another1Train = train1Start+10;
    another2Train = train2Start+10;

    %Let the passenger board the platform at a random time t=(10,20)
    passenger = 10*rand+10;
   
    %The next train may be train 1 from first round
    lowest = passenger-train1Start;
    %Or it may be train 2 from the first round
    lowest = min(lowest, passenger-train2Start);
   
    %Or it may be train 1 from the second round
    %Positive value verifies that passengers arrives become the train
    if passenger-another1Train>=0
        lowest = min(lowest, passenger-another1Train);
    end
    %Finally, the earlier train may be train 2 from the second round
    if passenger-another2Train>=0
        lowest = min(lowest, passenger-another2Train);
    end
   
    %Record the time to the earliest train into the results array
    results(i) = lowest;
end

%At last, we want to return the results
disp('Mean:')
disp(mean(results))
disp('Standard deviation:')
disp(std(results))
Upon running the script, the result comes out as a mean of 3.3334 (occasionally may get 3.3333) along with a standard deviation of 2.3572.

Thursday, December 8, 2011

Simulation of St. Petersburg Paradox

St. Petersburg Paradox exemplifies a situation where the expected value of an outcome doesn't reflect the realistic outcomes. The game can be played by flipping a coin until heads comes up. Let the outcome be 2 to the power of the number of coin flips. The derivation won't be shown here in detail (but is available on the link below), but essentially, there is 1/(2^n) chance of an outcome of (2^n), for all positive integers n. The expected payoff for each integer n is therefore 1, and the sum of the expected payoffs, the expected value of this game, is therefore infinity.

Realistic outcomes are far from this expected value. One can briefly visualize this by realizing that there's 50% chance of an outcome of 2, 25% chance of an outcome of 4, 12.5% chance of an outcome of 8, etc. Simply put, the chances of very high outcomes are very small. Let's use programming to simulate numerous rounds of this game. The Java code for the simulation method is as follows:
public static int simulation()
 {
     int times = 0;
     double flip = 0;
     while(flip < 0.5) //reflecting the 50% chance of getting heads
     {
         flip = Math.random();
         times++;
     }
     double result =  Math.pow(2,times);
     return (int)result;
 }
Writing a for loop code, this method was called 1,000,000 times, with the output values exported onto Microsoft Excel. The values were sorted and counted, and the results are as follows, along with the expected frequency of the different outcomes.

n Outcome (2^n) Frequency Expected Freq Deviation
1 2 500,592 500,000.00 0.118%
2 4 249,969 250,000.00 -0.012%
3 8 124,870 125,000.00 -0.104%
4 16 62,262 62,500.00 -0.381%
5 32 30,951 31,250.00 -0.957%
6 64 15,741 15,625.00 0.742%
7 128 7,843 7,812.50 0.390%
8 256 3,883 3,906.25 -0.595%
9 512 1,900 1,953.13 -2.720%
10 1,024 993 976.56 1.683%
11 2,048 484 488.28 -0.877%
12 4,096 233 244.14 -4.563%
13 8,192 144 122.07 17.965%
14 16,384 71 61.04 16.326%
15 32,768 34 30.52 11.411%
16 65,536 12 15.26 -21.357%
17 131,072 11 7.63 44.179%
18 262,144 3 3.81 -21.357%
19 524,288 4 1.91 109.715%

Even with 1 million trials, the greatest output value was only 524,288, which reflects the rare instance of 18 straight flips of tail before finally getting a heads. This only happened 4 times out of the 1 million trials, and was even considered strong positive deviation from the expected frequency of 1.91. The expected value of this game (expected average value) is still infinity, as the math demonstrates.

In this simulation of 1,000,000 trials, the average output value was 20.496084. The results are, as expected, very skewed to the right. If we let the output value measure monetary amount, it's interesting to note that the top 996 trials (0.0996%) contains 51.30% of the values. The top 0.7772% contains 65.86%. The bottom 96.8644% contains only 24.33%.

Sources: