%% The Saint Petersburg game
%% Introduction
% Let us now consider the following game, known as Saint Petersburg game: a player pays to a casino a fixed amount of F euros for entering in a game of chance consisting in throwing a fair coin until tails appears for the first time. The initial pot is 1 euro and it is doubled every time heads appears. So, if the fist flip of coin produces tails, the player wins 1 euro, if tails appears at the second toss, he wins 2 euros, if the first two throws give heads and the third tails he wins 4 euros, and so on.
% What is the correct amount F to be payed to the casino to have a fair game?
% Let us try to deduce it by evaluating the expected value of the winnings of the player in a single game. Let us call G the random variable representing the winnings. We find for any integer k\geq 0
% P(G=1)=\frac{1}{2},\qquad P(G=2)=\frac{1}{4}, \quad \ldots \quad P(G=2^k)=2^{-(k+1)},\quad \ldots
% Thus, the expected value of G is
% \mathbb{E}(G)=\sum_{k=0}^\infty 2^k\, P(G=2^k)=\sum_{k=0}^\infty 2^k\, 2^{-(k+1)}= \sum_{k=0}^\infty \frac{1}{2}=\infty
% It follows that the game is favourable to the player whatever is the entrance fee F for each trial. Nevertheless, it is clear that a lucky sequence of many consecutive heads is unlikely, so that the larger is F, the longer will the player have to play to render probable a positive gain.
%% Simulation of the game
% Let us try a single toss of the coin:

rng('shuffle')
coin_flip=rand;
if(coin_flip>0.5)
    fprintf('Heads ')
else
    fprintf('Tails ')
end

%
% Let us simulate the game to show the typical behaviour. If we fix F=6, a cheap entrance fee, the probability to have a negative net gain is still 7/8, so that on average only one trial over 8 produces a positive gain.

% Simulation of a single trial with entrance fee FF=6
FF=6;
pot=1;
heads_count=0;
coin_flip=rand;
while(coin_flip<=0.5)
    pot=2*pot;
    heads_count=heads_count+1;
    coin_flip=rand;
end
fprintf('\n The sequence has been %d consecutive heads before tails',heads_count)
fprintf('\n The final pot has been %g euros',pot)
fprintf('\n The final net gain is %g',pot-FF)

%
% Let us play many consecutive games to see the behaviour of the overall net gain:

% Simulation of 1000 trials with entrance fee FF=6
FF=6;
trials=1000;
net_gain=0;
for games_played= 1:trials
    pot=1;   
    coin_flip=rand;
    while(coin_flip<=0.5)
        pot=2*pot;    
        coin_flip=rand;
    end
    net_gain=net_gain+pot-FF;
end
fprintf('\n after this run of %g games, \n the net gain is %g ',trials,net_gain)

%
% By running the previous section several times, we can see that a single trial of one thousand times with entrance fee F=6 can produce a consistent gain as well as a loss. Is it possible to understand how many times one should play to make probable a positive final gain?
% Let us try to study heuristically the average winning when the number of consecutive games grow.

% Average winning playing 1 million times
trials=1e6;
ave_vect=zeros(trials,1);
average_pot=0;
tic
for games_played =1:trials
    pot=1;   
    coin_flip=rand;
    while(coin_flip<=0.5)
        pot=2*pot;    
        coin_flip=rand;
    end
    average_pot=average_pot*(games_played-1)/games_played+pot/games_played;
    ave_vect(games_played)=average_pot;
end
toc
fprintf('\nThe average winning has been %g after %g trials',average_pot,trials)
figure,
plot(1:trials,ave_vect)
xlabel('number of games played'), ylabel('average winning')

% Running several times the previous section it is possible to guess, neglecting statistical fluctuations, that the typical behaviour of the average winning is indeed growing when the number of games played grows, but slowly.
% It is possible to show (see Feller, An Introduction to Probability Theory and its Applications, vol.1) that its typical behaviour after playing n times the Saint Petersburg game is asymptotically \sim \frac{1}{2}\log_2 (n). To be more precise, one can prove an analogous of the law of large numbers that holds for the St. Petersburg game that states that for large n, the ratio of the accumulated gain S_n to the accumulated entrance fees e_n is likely to be near 1 if we put e_n=\frac n 2 \log_2(n). So, for any \varepsilon>0, it holds
% \mathrm P \bigg( \bigg| \frac{S_n}{e_n} -1\bigg|>\varepsilon \bigg)\to 0  if n\to\infty.
% So, entrance fees that makes the St. Petersburg game "fair" have to depend on the number of trial instead of remaining constant.
%
% Let us now run the game an arbitrary number of times for different entrance fee F.

% Vary number of trials and entrance fee FF
trials=5e7;
FF=11;
ave_vect=zeros(trials/100,1);% save partial results each 100 games played
tic
average_pot=0;
for games_played =1:trials
    pot=1;   
    coin_flip=rand;
    while(coin_flip<=0.5)
        pot=2*pot;    
        coin_flip=rand;
    end
    average_pot=average_pot*(games_played-1)/games_played+pot/games_played;
    if(rem(games_played,100)==0)
        ave_vect(games_played/100)=average_pot;
    end
end
toc
fprintf('\n average winning %g after %g trials',average_pot,trials)
figure,
plot(1:trials/100,ave_vect,1:trials/100,FF*ones(trials/100,1),1:trials/100,0.5*log2(trials)*ones(trials/100,1))
legend('average winnings','FF','log_2(n) / 2')
xlabel('number of games played x 100'), ylabel('euros')

%

help rng
help rand

%
% A classical resolution of the paradox of the discrepancy between what people seem willing to pay to enter the game and the infinite expected value is the introduction of a utility function, an expected utility hypothesis. A common utility model, suggested firstly by Bernoulli, is the logarithmic function of the gain U(G)=ln(G). Notice that the expected utility of the winnings \mathbb{E}(U(G)) in the St. Petersburg game is indeed finite with this choice of the log utility of the wealth.
% Saint Petersburg paradox - Wikipedia, the Free Encyclopedia