Muhammad Ali pulls tiles from bag $3.$ A bag contains three tiles marked $A$, $L$, and $I$. Muhammad wants to pick the letters $ALI$, in that sucession. Randomly, he pulls one til from the bag. If the letter $A$ is drawn, he keeps it. If the letter pulled is other than $A$, he puts it back into the back. He does the same thing with the next tile. If the selected tile is $L$, he keeps it. If it is not $L$, he puts it back in the bag. The probability that Muhammad draws from the bag at most $10$ times can be written in the form $\frac{x_1}{x_2}$, where $x_1$ and $x_2$ are relatively prime numbers. Compute the remainder when $x_1+x_2$ is divided by $1000$. 
$\textbf{Thoughts}$
This seems like an application of casework counting. Here is my best try.
NOTE:Some of these cases could be incorrectly counted.
$3$ draws needed: $1$ case
$4$ draws needed: $2$ cases 
$5$ draws needed: $3$ cases
$6$ draws needed: $4$ cases
$7$ draws needed: $5$ cases
We have an emerging pattern. Therefore, we get $1+2+3+4+5+6+7+9=45$. However, I do not know what my denominator will be...
 A: What is the probability that it takes n draws, imagine the sequence of draws $x_1, x_2, \cdots, x_n$. 
For this this to be a valid draw we have some $x_i=A$ and $x_{n-1}=L$ such that $1 \le i <n-1$. And since it took $n$ draws then $x_n=I$
For a particular $i,j$ the probability is $p_n(i,j)$
$$p_n(i,j)=\left(\frac{2}{3}\right)^{i-1}\left(\frac{1}{3}\right)\left(\frac{1}{2}\right)^{n-i-2}\left(\frac12\right)$$
We need to sum this over all $i$ $$\sum_{i=1}^{n-2}\left(\frac{2}{3}\right)^{i-1}\left(\frac{1}{3}\right)\left(\frac{1}{2}\right)^{n-i-2}\left(\frac12\right)=\frac16\frac{1}{2^{n-2}} \sum_{i=1}^{n-2}\left(\frac{2}{3}\right)^{i-1}2^i=\frac{1}{3.2^{n-1}}.\frac{2\left((\frac{4}{3})^{n-2}-1\right)}{\frac{4}{3}-1} \\\text{Probability that n draws are needed}=p_n=\frac{1}{2^{n-2}}{\left((\frac{4}{3})^{n-2}-1\right)}$$
So probability that he draws at most 10 times $$\sum_{n=3}^{10}p_n=\sum_{n=3}^{10}\left(\left(\frac23\right)^{n-2}-\left(\frac12\right)^{n-2}\right)\\=\frac{(2/3)(1-(2/3)^8)}{(1-2/3)}-\frac{(1/2)(1-(1/2)^8)}{(1-1/2)}\\=\frac{12610}{6561}-\frac{255}{256}$$
Simplifying this we get $$\frac{1555105}{1679616}$$
The final answer $x_1=1555105, x_2=1679616$ and $x_1+x_2=3234721$, therefore that last 3 digits is $721$
A: We can afford $\leq7$ false draws. The probability $p_k$ that we get A after exactly $k\geq0$ false draws is given by
$$p_k=\left({2\over3}\right)^k\cdot{1\over3}\qquad(k\geq0)\ .$$
If we have made $k$ false draws to get the A we need to obtain the L in $\leq8-k$ draws. The probability that we make it is given by $$q_k=1-\left({1\over2}\right)^{8-k}\ ,$$
since only obtaining $8-k$ letters I in a row would mean failure.
The overall probability $p$ of success therefore is given by
$$p=\sum_{k=0}^7 p_k\>q_k={1555105\over1679616}\ ,$$
so that the answer to the question comes to $721$.
A: I have solved it using Markov Chain.  The first transition matrix is the steady state.  From then it is exponentiated to different powers to get the final 10 th draw.  The last three digits are  $\boxed{721}$
There seems to be some miscalculation from the other responder.

