On Day 1, Aaron draws a smiley face on the board. From then on, on each day he does the same thing as the previous day (draw a smiley face or not) with probability $\dfrac{2}{3}$. What’s the probability he draws a smiley face on Day 10?
This is the solution given at SMT site: https://www.stanfordmathtournament.com/pdfs/smt2019/general-solutions.pdf. I have given a different solution, just posting it for solution verification
Alternative approach:
There is a smiley face on day 10 if and only if there are an even number of flips in the 9 days between day 1 and day 10.
For $~k \in \{0,1,2,3,4\},~$ the probability of having exactly $~2k~$ flips is
$$f(k) = 3^{-9} \times \left[ ~\binom{9}{2k} 2^{9 - 2k} ~\right].$$
Therefore, the desired computation is
$$\sum_{k=0}^4 f(k).$$
A quick observation of running numbers for $n = 3$ it reveals that
The number of times there are flips (by which I mean a smiley face to no smiley face) within these events. Besides the first day, every time there is a flip, the successive day has a probability of $\dfrac{1}{3}$ of smiley face, and every time there is no flip, the successive day has a probability of $\dfrac{2}{3}$ of smiley face. The count of flips follows a binomial distribution of terms.
For $n = 3$,
No of flips; Total; Starting state
0 ; 1; Smiley
1 ; 2; No Smiley
2 ; 1; Smiley
So it follows that the $2^{(n-1)}$ follows a binomial distribution with probability of smiley $\dfrac{2}{3}$ and probability of no smiley$\dfrac{1}{3}$ such as this
For $n = 3$
$^{2}C_{0}(\frac{2}{3})(\frac{2}{3}) + ^{2}C_{1}(\frac{2}{3})(\frac{1}{3}) + ^{2}C_{2}(\frac{1}{3})(\frac{1}{3})$
In other words for $^{(n-1)}C_{i}(p^{(n-1-i)}*(q^{(i)})$, the even terms respond to a smiley while odd terms respond to no smiley Extending it to any n,
Sum of Even terms = $\frac{1}{2}\left[(\frac{2}{3} +\frac{1}{3})^{(n-1)}+(\frac{2}{3} -\frac{1}{3}))^{(n-1)}\right]$
= $\frac{1}{2}\left[1+(\frac{1}{3})^{(n-1)}\right]$
Required Probability = $\frac{1}{2}\left[1 + \frac{1}{3}^{(n-1)}\right]$
when n= 10 => $\frac{1}{2}\left[1+(\frac{1}{3})^{9}\right]$
= $\frac{9842}{19683}$
Let me know if this approach is reasonable.
Here is how I would approach it:
We have a Markov process.
$P_n\pmatrix {\text {smiley}\\\text {no smiley}} =\pmatrix{\frac 23& \frac13\\ \frac 13&\frac 23}P_{n-1}\pmatrix {\text {smiley}\\\text {no smiley}} = \pmatrix{\frac 23& \frac13\\ \frac 13&\frac 23}^{n-1}P_1\pmatrix {\text {smiley}\\\text {no smiley}}$
$\pmatrix{\frac 23 & \frac13\\ \frac 13 & \frac 23}^n = \frac 12 \pmatrix {1&-1\\1&1}\pmatrix {1\\&\frac 1{3^n}}\pmatrix {1&1\\-1&1} = \frac 12\pmatrix {1+\frac {1}{3^n}&1-\frac {1}{3^n}\\1-\frac {1}{3^n}&1+\frac {1}{3^n}}$
$\pmatrix{\frac 23 & \frac13\\ \frac 13 & \frac 23}^{9}\pmatrix{1\\0} = \pmatrix{\frac {1}{2}(1+\frac 1{3^{9}})\\\frac {1}{2}(1-\frac 1{3^{9}})}$
You can visualize this with a tree. Draw one node, and color it black (smiley face). Then, draw three nodes out of it, if the original node was black, color two black, otherwise, just color 1. Each level of the tree represents a different day, and the probability of getting a smiley face is the total number of black nodes divided by the number of all nodes for that day.
Therefore, given day $n-1$ with $k$ total black nodes, we have $2k + (3^{n-1}-k) = 3^{n-1}+k$ total black nodes and $3^n$ total nodes on day $n$. The probability transforms by: $$\frac{2k}{3^{n-1}} \to \frac{3^{n-1} + k}{3^n} =\frac{1}{3} + \frac{k}{3^n}$$ On day $10$, $k$ is $\sum_{n=1}^{9} 3^{n} + 1$, since $k$ is always a power of $3$ which you can derive from above. This is a geometric series, and the partial sum is given by: $$S_{9} + 1 = \frac{1-3^9}{1-3} +1= 9841+1 = 9842$$ Thus, we can find our final probability of $\frac{9842}{19683}$.
