function OutcomeSequence(Sequence, N_Outcomes)
%==========================================================================
%OutcomeSequence
% Compute the expected time to get a given sequence of independent
% and equally-likely-to-happen outcomes.
%
% OutcomeSequence(Sequence, N_Outcomes)
%
%==========================================================================
% INPUTS:
%
% Sequence:
%
% - Sequence (row vector) of numbers representing the different
% possible outcomes. The occurrence times of those outcomes are
% assumed to be I.I.D. random variables, i.e. the outcomes occur
% independently of each other and are equally likely to happen.
%
% N_Outcomes:
%
% - Number of different possible (independent) outcomes.
%
%==========================================================================
% OUTPUT:
%
% Expected_Time:
%
% - Expected time to get the input sequence of outcomes. This time
% would correspond to a number of tosses of a coin, throws of a
% dice and so on depending on the problem considered.
%
%==========================================================================
% EXAMPLE 1: Coin Toss
% You toss a coin. What is the expected number of tosses to get the
% sequences:
% 1.1 'Tails-Heads-Heads'?
% 1.2 'Tails-Heads-Tails'?
% 1.3 'Tails-Tails-Tails-Heads'?
%
% Answer 1.1
% >> OutcomeSequence([1, 0, 0], 2)
% Expected_Time = 2^3 = 8
%
% Answer 1.2
% >> OutcomeSequence([1, 0, 1], 2)
% Expected_Time = 2^3 + 2^1 = 10
%
% Answer 1.3
% >> OutcomeSequence([1, 1, 1, 0], 2)
% Expected_Time = 2^4 = 16
%
%**************************************************************************
% EXAMPLE 2: Dice Throw
% You throw a dice. What is the expected number of throws to get
% the sequences:
% 1.1 '4, 2, 1'?
% 1.2 '1, 2, 3 ,2, 1'?
%
% Answer 1.1
% >> OutcomeSequence([4, 2, 1], 6)
% Expected_Time = 6^3 = 216
%
% Answer 1.2
% >> OutcomeSequence([1, 2, 3 ,2, 1], 6)
% Expected_Time = 6^5 + 6^1 = 7782
%
%**************************************************************************
% EXAMPLE 3: Random Keyboard Hit
% You randomly hit your 26-key keyboard. What is the expected
% number of keys you have to hit to get the sequences:
% 3.1 "Hello" ?
% 3.2 "ABRACADABRA" ?
%
% Answer 3.1
% >> OutcomeSequence([1, 2, 3, 3, 4], 26)
% Expected_Time = 26^5 = 11881376
%
% Answer 3.2
% >> OutcomeSequence([1 2 18 1 3 1 4 1 2 18 1], 26)
% Expected_Time = 26^11 + 26^4 + 26^1 = 3670344487444778
%
%**************************************************************************
% EXAMPLE 4: with Non-Uniform Probabilities
% You play one poker game everyday. Assume you are likely to win 1
% out of 4 games you play. What is the expected number of days you
% have to play to:
% 4.1 win 3 times in a row ?
% 4.2 lose 3 times in a row ?
%
% Answer 4.1
% >> OutcomeSequence([1, 1, 1], 4)
% Expected_Time = 4^3 + 4^2 + 4^1 = 84
%
% Answer 4.2
% >> OutcomeSequence([1, 1, 1], 4/3)
% Expected_Time = 1.333^3 + 1.333^2 + 1.333^1 = 5.481
%
%==========================================================================
% Rodolphe Sitter - MSFM Student - The University of Chicago
% March 30, 2009
%==========================================================================
N=N_Outcomes;
seq=Sequence;
S = sort(seq);
NS = histc(seq,S);
NS(NS==0) = [];
ns=length(NS);
if ns>N
error('The number of distinct elements in the sequence must be smaller than the number of possible outcomes.')
end
M=length(seq);
Expected_Time=N^M;
fprintf('Expected_Time = %0.4g^%0.4g',N,M)
for i=M-1:-1:1
if min(seq(1:i)==seq(M-i+1:M))==1
Expected_Time=Expected_Time+N^i;
fprintf(' + %0.4g^%0.4g',N,i)
end
end
fprintf(' = %0.4g \n\n',Expected_Time)
