2
$\begingroup$

If I know the probability of winning an individual round (while playing, say, a slot machine), call it $p_0$, what is the expected number of groups of 3 consecutive wins in 200 rounds? Or, to make it more general, what is the expected number of $k$-consecutive-win groups in $n$ rounds?

The groups cannot overlap, so 4 consecutive wins do not count as 2 different groups of 3 wins, while 6 consecutive wins do count as 2 different groups.

I was thinking of looking for the total number of possible $k$-group configurations in $n$ rounds, but I'm not too sure.

Explaining how you got this result would be most welcome, though the final formula would do as well. Thank you very much.

$\endgroup$
2
$\begingroup$

My solution will not only answer your question exactly (within linear algebra roundoff error) for the general case, but actually gives you the entire probability distribution of number of successful (i.e., completed) streaks.

This can readily be solved by using a discrete time discrete state (time-homogeneous) Markov Chain, in an approach similar in spirit to, but with larger state space, than the methods I used in https://math.stackexchange.com/questions/383704/probability-of-streaks/1739987#1739987 . After you read my answer in that thread plus this thread, you should be a wizard in using Markov Chains to solve all manner of streaks problems.

I will let

p = probability of winning per round
k = number of wins for successful streak
n = number of rounds

Then g is determined to be the upper bound on largest number of streaks, calculated as

g = floor(n/k)

Define the states as bivariate pairs(i,j), in which i denotes the current number of successful (i.e., completed) streaks and j is the length of the current streak. i will range from 0 to g, and j will range from 0 to k-1, except for when i = g, in which case j only goes from 0 to 0, and we make that state, (g,0), an absorbing state because we can't get any additional successful streaks. Order the states with j increasing fastest, then i increasing. I.e., with k = 3, the states would be (0,0),(0,1),(0,2),(1,0),(1,1),(1,2), etc.

Once the Markov Chain one step transition matrix, M, has been populated (see below), we compute the n step Markov Chain transition matrix, Mn as $M^n$. Given that we start in state (0,0) before the first of n rounds, the first row of Mn contains the probabilities of being in the various states after n rounds. For each possible value of number of successful streaks i, the sum of the probabilities over j for all states (i,j) provides the probability of exactly i successful streaks having occurred. It is then trivial to compute the expected number of successful streaks.

The one step transition matrix is populated as follows (note that w.p. is short for "with probability"):

For each i from 0 to g-1 (I'll show here for the case k = 3)
State (i,0) transitions to (i,0) w.p. 1-p and to (i,1) w.p. p
State (i,1) transitions to (i,0) w.p. 1-p and to (i,2) w.p. p
State (i,2) transitions to (i,0) w.p. 1-p and to (i+1,0) w.p. p

The absorbing state (g,0) transitions w.p. 1 to (g,0)

The population of the one step Markov Chain for a general value of k (and n) is shown in my MATLAB code below. Everything on a line after % is a comment.

k = 3; n = 200; p = .6; % set k, n, and p to particular values
g = floor(n/k);
B = [(1-p)*ones(k,1),p*eye(k)]; % recurring block in transition matrix M.
% B is a k by (k+1) matrix, consisting of a column vector of (1-p) 's,
% right-horizontally concatenated with p times the k by k identity matrix
% Start building up one step transition matrix, M
M = zeros(g*k+1); % (g*k+1) by (g*k+1) matrix of zeros
for i=0:g-1, M(k*i+1:k*(i+1),k*i+1:k*(i+1)+1) = B; end; 
M(g*k+1,g*k+1) = 1; % Construction of M is now complete
Mn = M^n; % n step transition matrix
% Calculate array of probabilities of number of successful streaks
% and place in prob_array
prob_array = zeros(g+1,1);
for i=0:g-1, prob_array(i+1) = sum(Mn(1,k*i+1:k*i+k)); end;
prob_array(g+1) = Mn(1,g*k+1); % prob_array is now complete
expected_number_streaks = (0:g)*prob_array

Here are example results for n = 200 rounds, and streaks of length k = 3, with bonus results for streaks of length k = 5. Graph of Results

Here is an example one step transition matrix, for p = 0.6, n = 11, k = 3, which results in g = 3.

One Step Transition Matrix for n = 11, k = 3

$\endgroup$
  • $\begingroup$ Great. Yes, this agrees with observations... By the by, do you recommend any books to learn (relatively) advanced probability? I hadn't met the use of Markov Chains like this before. $\endgroup$ – Kristian D'Amato Apr 18 '16 at 7:02
  • $\begingroup$ @Kristian D'Amato , many so-called advanced probability books deal with rigorous theory - it sounds like that may not be what you want. It sounds like a book on stochastic processes might be good for you, or perhaps applied probability with significant stochastic processes content, but I don't have a specific book of such type to recommend. $\endgroup$ – Mark L. Stone Apr 18 '16 at 17:12
0
$\begingroup$

Since you're talking about a slot-machine, I assume that the probabilities are independent. The probability of $k$ consecutive wins is $p_0^k$. That probability is the expected portion of the groups with size $k$ that contain all wins. The number of groups with size $k$ (that does not overlap) is $200/k$, and we can call the number of all rounds $n$ (already alluded to in your question). So, the expected number of groups with size $k$ that contains consecutive wins would be

$p_0^k \cdot (n/k)$

And, in your particular example

$ p_0^3 \cdot (200/3)$

Edit:

Apparently this problem is deceptively hard, like really hard. Just answering what the probability is that one group of length $k$ will appear is hard. The probability $S(n,k)$ of a group of consecutive wins of length $k$ in a chain of $n$ events, with the probability of a win $p$ and probability of a fail $1-p=q$ is

$S(n,k) = p^k \sum_{i=0}^{\infty} {n - (i+1)k \choose i}(-qp^k)^i - \sum_{i=1}^{\infty} {n - ik \choose i}(-qp^k)^i$

Here, the groups can even overlap, which is not what you asked for. I hope this can point you in the right direction.

(I apologize for the wrong answer earlier, I hope I did not lead you astray too much)

$\endgroup$
  • $\begingroup$ Are you sure this is right? Observed information is not matching with this prediction (observations are about 50% higher) $\endgroup$ – Kristian D'Amato Apr 15 '16 at 10:47
  • $\begingroup$ Are you sure that the groups may not overlap? Because, if they are allowed to overlap I can understand why the estimate is missing by 50% and in that case you should use the formula n + 1 - k to estimate the number of possible blocks. $\endgroup$ – pimmen Apr 15 '16 at 11:41
  • $\begingroup$ Yep. Keep in mind that if they are allowed to overlap the chance of getting a second win-group overlapping with the first is not independent of the first (since you only need one more round to have another win-group)... Anyway they don't overlap. $\endgroup$ – Kristian D'Amato Apr 15 '16 at 12:35
  • $\begingroup$ I'm doubting myself, but I don't see how this could be wrong. p^k is the expected proportion of groups with all wins, n/k is the maximum amount of consecutive, non overlapping groups that can fit within the chain. Are you running simulations and could you supply some code in that case? $\endgroup$ – pimmen Apr 15 '16 at 13:40
  • $\begingroup$ I will when I'm able to later on. There are other k-chains in the entire sequence, since a group can start at position 2, for instance, covering 2-4, etc... $\endgroup$ – Kristian D'Amato Apr 15 '16 at 13:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.