probability of a run of k heads or more in N tosses of a fair coin N>>k
4 Ansichten (letzte 30 Tage)
Ältere Kommentare anzeigen
Fred
am 6 Nov. 2013
Bearbeitet: Ben Petschel
am 7 Nov. 2013
is there a code for this. One solution is given in http://www.drdobbs.com/architecture-and-design/20-heads-in-a-row-what-are-the-odds/229300217 Good discussion… gives answer
0 Kommentare
Akzeptierte Antwort
Image Analyst
am 6 Nov. 2013
Bearbeitet: Image Analyst
am 7 Nov. 2013
It's pretty trivial if you have the Image Processing Toolbox:
numberOfTosses = 1000000;
% Throw coin numberOfTosses times with tails defined as 0, heads as 1.
tosses = randi(2, 1, numberOfTosses)-1;
% Use the Image Processing Toolbox to find stretches of N.
N = 20; % Look for 20 in a row.
measurements = regionprops(logical(tosses), 'area');
% Extract the lengths of all stretches of heads in a row.
allRuns = [measurements.Area];
% Count the number of times it's N or more
numberOfLongStretches = sum(allRuns >= N)
2 Kommentare
Ben Petschel
am 7 Nov. 2013
Bearbeitet: Ben Petschel
am 7 Nov. 2013
I don't think this answers the right question.
Weitere Antworten (2)
Roger Stafford
am 7 Nov. 2013
Here is an iterative method of finding the probability. Let k and N be the quantities you described. Then perform this matlab code:
p = zeros(N,1);
p(k) = 1/2^k;
if N > k, p(k+1) = p(k) + 1/2^(k+1); end
for n = k+2:N
p(n) = p(n-1) + (1-p(n-k-1))/2^(k+1);
end
Then p(n) is the probability for k consecutive heads out of n tosses for each of the values of n in 1<=n<=N. Note: This is not a Monte Carlo method; it is an exact computation.
This is based on the notion that if p is already evaluated from p(1) to p(n-1), then the probability p(n) event occurs in two mutually exclusive ways. Either the first n-1 of the n tosses contains such a contiguous sequence of k heads or else the last k of the n tosses are all heads, the toss immediately prior to them is a tails, and the remaining initial n-k-1 of them contains no such sequence of k consecutive heads. There is no other way this event can occur with the n tosses. The first of these ways clearly has probability p(n-1) and the second has probability equal to the product
1/2^(k+1)*(1-p(n-k-1))
and hence p(n) is their sum.
I ran this for two cases and arrived at the following results:
k = 3;
p(10) = 0.5078125 = 520/1024
k = 5;
p(50) = 0.5518753229536166 = 621356374702220/1125899906842624
0 Kommentare
Ben Petschel
am 7 Nov. 2013
The method in the link you gave can be modified to avoid the need for arbitrary-precision integer arithmetic in calculating the generalized Fibonacci numbers. Basically the solution to the recurrence relation can be expressed in terms powers of the roots of the characteristic polynomial. Then the solution can be written as:
r=@(k)roots([1,-ones(1,k)]); % roots of the characteristic polynomial
a=@(k)[1,zeros(1,k-1)]/vander(r(k)); % coefficients are solution to a Vandermonde system
% Have Fk(n) = a(k)*r(k).^(n+k-1) with Fk(0)=1
p=@(n,k)1-(2^k)*a(k)*(r(k)/2).^(n+k);
Some particular cases:
p(4,2) = 0.5000
p(10,3) = 0.5078 + 0.0000i
p(50,5) = 0.5519 - 0.0000i
p(1e6,20) = 0.3793 + 0.0000i
The small imaginary part in the solution is due to roundoff but it is about O(eps) in all cases indicating that the result is reasonably accurate.
0 Kommentare
Siehe auch
Kategorien
Mehr zu Particle & Nuclear Physics finden Sie in Help Center und File Exchange
Produkte
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!