Reviewing Movies II

If $R$ is any run, then the probability that that run has length at least $n$ , given that it is a run of $k$ stars, is $\mathbb{P}[R \ge n| k \; \text{stars}] \; = \; p_k^{n-1} \hspace{2cm} n \ge 1$ and hence the expected length of a run, given that is a run of $k$ stars, is $\sum_{n \ge 1} \mathbb{P}[R \ge n| k \; \text{stars}] \; = \; \frac{1}{1-p_k}$ Thus we need to consider the Markov chain whose states are the number of stars that are being counted in successive runs. This Markov chain has transition matrix $\left(\begin{array}{ccc} 0 & \frac{p_2}{p_2+p_3} & \frac{p_3}{p_2+p_3} \\ \frac{p_1}{p_1+p_3} & 0 & \frac{p_3}{p_1+p_3} \\ \frac{p_1}{p_1+p_2} & \frac{p_2}{p_1+p_2} & 0 \end{array}\right)$ and hence the expected length of the $n$ th run is $\mu_n \; = \; \left(\begin{array}{c} p_1 \\ p_2 \\ p_3\end{array}\right)^T \left(\begin{array}{ccc} 0 & \frac{p_2}{p_2+p_3} & \frac{p_3}{p_2+p_3} \\ \frac{p_1}{p_1+p_3} & 0 & \frac{p_3}{p_1+p_3} \\ \frac{p_1}{p_1+p_2} & \frac{p_2}{p_1+p_2} & 0 \end{array}\right)^{n-1} \left(\begin{array}{c} \tfrac{1}{1-p_1} \\ \tfrac{1}{1-p_2} \\ \tfrac{1}{1-p_3} \end{array}\right)$ With $p_1 = 0.17$ , $p_2 = 0.79$ , $p_3 = 0.04$ we obtain $\mu_1 = \frac{18631}{4648} \hspace{1cm} \mu_2 = \frac{19573}{10458} \hspace{1cm} \mu_3 = \frac{374027959}{97217568} \hspace{1cm} \mu_4 = \frac{1757602213}{874958112} \hspace{1cm} \mu_5 = \frac{7565208908051}{2033402652288}$ so that $\sum_{j=1}^5 \mu_j \; = \; \frac{31429396450771}{2033402652288}$ making the answer $\boxed{33462799103059}$ .

I find a recursive relation for $\mu_{n}$ and solve it with a Python3 program.

Let $a,b,c$ be $p_{1},p_{2},p_{3}$ , in no particular order, and $P(x,n)$ be the probability the $n$ -th run is a run of reviews which appear with probability $x$ . For example, $P(0.79,4)$ is the probability the $4$ -th run is one made of $2$ -star reviews.

Then $P(a,n)=\frac{a}{a+b}P(c,n-1)+\frac{a}{a+c}P(b,n-1)$ , since for a run to be made of, say, $1$ -star reviews, the previous run must be one of $2$ -star or $3$ -star reviews, and, of course, the first review must be a $1$ star.

Finally, the expected length of a run made of reviews which appear with probability $x$ is $\frac{1}{1-x}$ .

We're then looking to find $\frac{P(p_{1},5)}{1-p_1}+\frac{P(p_{2},5)}{1-p_2}+\frac{P(p_{3},5)}{1-p_3}$ , given that $P(p_{k},1)=p_{k}$ for $k=1,2,3$ .

So here's the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

from fractions import *

memory={}
probs=[17,79,4]

#Set up base cases:
for i in range(0,3):
  memory[(probs[i],1)]=Fraction(probs[i],100)

def P(a,n):
  if (a,n) in memory:
    return memory[(a,n)]

  #Get b and c values:
  b=0
  c=0
  for i in range(0,3):
    if probs[i]!=a and b==0:
      b=probs[i]
    elif probs[i]!=a:
      c=probs[i]

  #Our recursive relation:
  ans=Fraction(a,a+b)*P(c,n-1)+Fraction(a,a+c)*P(b,n-1)

  #Add to memory:
  memory[(a,n)]=ans

  return ans

s=0
for i in range(1,6):  

  #Expected length of i-th run:
  expected=0
  for j in range(0,3):
    expected+=P(probs[j],i)/(1-Fraction(probs[j],100))

  s+=expected
print(s)

Output is $31429396450771/2033402652288$ , making the answer $33462799103059$

First run starts with an $i$ -star review with probability $p_i$ and ends after $1/q_i$ movies reviewed on average, with $q_i = 1 - p_i$ , since that is the expected number of Bernoulli trials until a non- $i$ outcome. If the first run starts with one star, it ends with either a two-star or a three-star review, with respective probabilities $p_2/q_1$ and $p_3/q_1$ . Mind that the conditional probabilities of a 2- and 3-star review are normalized to the given that a 1-star run cannot be ended with a 1-star review. If the initial 1-star run is ended with a 2-star review, the second run is then a 2-star run and ends after $1/q_2$ movies reviewed on average, etc.

The processes is governed by a two-way probability branching save for the initial three-way branching. The same logic applies to general $n$ -star reviewing. Let's write down one term for $\mu_3$ which represents the "1-run, 2-run, 1-run" possibility.

$p_1 \, \frac{p_2}{q_1} \, \frac{p_1}{q_2} \, \frac{1}{q_1} = \frac{p_1}{q_1} \, \frac{p_2}{q_2} \, \frac{p_1}{q_1}$

Such terms should be summed over all possible root-to-leaf paths, which turns out to be tuples of elements $\{1, 2, 3\}$ with distinct successive elements. There are 12 such tuples for $n = 3$ . This readily suggests two programming approaches one can try. Both my solutions are written in Mathematica, or the Wolfram Language as it's called now. First I did a sum over tuples.

Second approach is more traditional perhaps, traversing the probability tree.