CS 360: Introduction to Artificial Intelligence

This is simply the number of ways to choose five things from 52:

$$\begin{array}{ccccccc}\left(\genfrac{}{}{0ex}{}{52}{5}\right)& =& \frac{52!}{5!\left(52-5\right)!}& =& \frac{\left(52\right)\left(51\right)\left(50\right)\left(49\right)\left(48\right)}{5!}& =& 2598960\end{array}$$

Each hand is equally likely, so:

$$\frac{1}{2598960}$$

There are four royal straight flushes, so:

$$\begin{array}{ccc}\frac{4}{2598960}& =& \frac{1}{649740}\end{array}$$

Each hand of four of a kind is distinguished by two things, the card there is four of and the card that is different. There are 13 different cards to have four of and for each given four of a kind there are 48 cards that are different. So, the number of ways to get four of a kind is:

$$\begin{array}{ccc}\left(13\right)\left(48\right)& =& 624\end{array}$$

The probability then would be:

$$\begin{array}{ccc}\frac{624}{2598960}& =& \frac{1}{4165}\end{array}$$

From the question we are given probabilities about the events:

• t_g — The taxi was green
• t_b — The taxi was blue
• p_g — The perceived color was green
• p_b — The perceived color was blue

The information given is:

• All taxis are either blue or green:
  • P(t_g ∨ t_b) = 1
  • P(t_g ∧ t_b) = 0
• Discrimination between blue and green is 75% reliable. (An assumption is made that the person making the statement is being honest and that they are accurately reporting their perceptions.) This is somewhat tricky since it is possible to say, "I know what the perception is, so the perception is given." For the purposes of testing reliability though, the actual color is what was known and the perception was determined:
  • P(p_g | t_g) = P(p_b | t_b) = .75
  • P(p_g | t_b) = P(p_b | t_g) = .25

The desired quantity is the most likely color for the taxi:

$$\begin{array}{ccccc}{x}_i& \ni & x_i,x_j\in \left\{t_g,t_b\right\};i\ne j;P\left(x_i\right)>P\left(x_j\right)& \forall & i,j\end{array}$$

It is worth noting two facts:

• If there is a tie for the top place, then x_i is not defined
• For this situation where there are only two colors, the statement can be simplified to: $$\begin{array}{ccc}x& \ni & x\in \left\{t_g,t_b\right\};P\left(x\right)>0.5\end{array}$$

Consider the probability that the taxi was in fact blue given it was perceived to be blue, using Bayes' rule: (If this is less than 0.5 then the taxi was probably green.)

$$\begin{array}{ccccccc}P\left(t_b|p_b\right)& =& \frac{P\left(t_b,p_b\right)}{P\left(p_b\right)}& =& \frac{P\left(t_b,p_b\right)}{P\left(t_b,p_b\right)+P\left(t_b,\neg p_b\right)}& =& \frac{P\left(t_b,p_b\right)}{P\left(t_b,p_b\right)+P\left(t_b,p_g\right)}\end{array}$$ $$\begin{array}{ccccc}& =& \frac{P\left(p_b|t_b\right)P\left(t_b\right)}{P\left(p_b|t_b\right)P\left(t_b\right)+P\left(p_b|t_g\right)P\left(t_g\right)}& =& \frac{P\left(p_b|t_b\right)P\left(t_b\right)}{P\left(p_b|t_b\right)P\left(t_b\right)+P\left(p_b|t_g\right)\left(1-P\left(t_b\right)\right)}\end{array}$$

All of the conditional probabilities are known, but P(t_b) isn't, so the solution isn't known. This makes sense. Say for example there are 10,000 taxis in Athens. 9,999 are green and 1 is blue. The likelihood that I mistook one of the green ones for the blue one is much higher than the probability that I actually saw the one blue one.

This adds an additional known probability:

• P(t_g) = 0.9
• P(t_b) = 1 - P(t_g) = 0.1

With this information it is possible to solve the previous equation:

$$\begin{array}{ccccccc}P\left(t_b|p_b\right)& =& \frac{P\left(p_b|t_b\right)P\left(t_b\right)}{P\left(p_b|t_b\right)P\left(t_b\right)+P\left(p_b|t_g\right)\left(1-P\left(t_b\right)\right)}& =& \frac{\left(0.75\right)\left(0.1\right)}{\left(0.75\right)\left(0.1\right)+\left(0.25\right)\left(1-0.1\right)}& =& 0.25\end{array}$$

So, there is only a $\frac{1}{4}$ probability that the taxi was blue given I thought it was blue. I.e., it was probably green.

ii is clearly correct because a change in N or F_i will affect M_i. The statement of the question highly suggests that at least one of the other two is an inefficient solution.

i can be eliminated because M_i is only dependent on F_i. The count found by the first observer, M₁, is very likely correlated to the count found by the second, M₂.

iii doesn't have any conditional independences which is correct, though not terribly efficient.

ii is the most succinct network which requires the minimum of information to do computations.

If a telescope is out of focus it will undercount by at least three. Counting errors will cause an error of at most one, so it is not possible to undercount by two. Also it is not possible to overcount by more than one.

It is assumed that the likelihood of a counting error is equally likely in either direction, so:

$$\begin{array}{ccccc}P\left(M_i=k-1|N=k\right)& =& P\left(M_i=k+1|N=k\right)& =& \frac{e}{2}\end{array}$$

M1	P(M1 | N = 1)	P(M1 | N = 2)	P(M1 | N = 3)
0	$\frac{e}{2}$	0	f
1	1 - e	$\frac{e}{2}$	0
2	$\frac{e}{2}$	1 - e	$\frac{e}{2}$
3	0	$\frac{e}{2}$	1 - e - f
4	0	0	$\frac{e}{2}$

Since it is possible to undercount by an arbitrary number of stars, there is no maximum possible. Both M₁ and M₂ could be underestimating by 100,000 stars for all that is specified in the problem. The question is the minimum number. It is only possible to overcount by 1, so the minimum set by M₂ is 2.

$$\begin{array}{ccccc}2& \le & N& <& \mathrm{\infty }\end{array}$$

The likelihood that the telescopes are out of focus and a serious overcount is happening is constant at f. If this is the case then anything above N = 6 (M₂ + 3) has the same probability:

N	M1 - N	M2 - N	P(N | M1 = 1)	P(N | M2 = 3)	P(N | M1 = 1,M2 = 3)
≤ 1	≥ 0	≥ 2		01	0
2	-1	1	$\frac{e}{2}$	$\frac{e}{2}$	$\frac{e^2}{2}$
3	-2	0	02		0
4	-3	-1	$f$	$\frac{e}{2}$	$\frac{ef}{2}$
5	-4	-2		02	0
≥ 6	≥ -5	≥ -3	$f$	$f$	$f^2$

• ¹ — can't overcount by more than one
• ² — can't undercount by two

The most likely number of stars is 2. From the problem specification, it is stated that f is "much smaller" than e. This can be taken to assume:

$$\begin{array}{ccccccccccc}f& <& e& \Rightarrow & P\left(N=4|M_1=1,M_2=3\right)& =& \frac{ef}{2}& <& \frac{e^2}{2}& =& P\left(N=2|M_1=1,M_2=3\right)\end{array}$$ $$\begin{array}{ccccccccccc}f& <& \frac{e}{\sqrt{2}}& \Rightarrow & P\left(N\ge 6|M_1=1,M_2=3\right)& =& f^2& <& \frac{e^2}{2}& =& P\left(N=2|M_1=1,M_2=3\right)\end{array}$$

For the purposes of succinct representation, the full predicates are shortened:

• B = {b, ¬b} = Burglary
• J = {j, ¬j} = JohnCalls
• M = {m, ¬m} = MaryCalls

There are also hidden variables:

• A = {a, ¬a} = Alarm
• E = {e, ¬e} = Earthquake

The basics of this problem are predicated on the following Baysean network:

Recall, in general, for a Bayes' net:

$$\begin{array}{ccc}P\left(x_1,\dots ,x_n\right)& =& \underset{i=1}{\overset{n}{\Pi }}P\left(x_i|parents\left(X_i\right)\right)\end{array}$$

The problem is considered in terms of the entire probability distribution, P, as opposed to the probability of a particular event, P. For a given:

• X — query variable being investigated
• o — observed values of evidence variables
• u — unobserved variables

$$\begin{array}{ccccc}P\left(X|o\right)& =& \alpha P\left(X,o\right)& =& \alpha \sum _{u}P\left(X,o,u\right)\end{array}$$

So, for this example:

$$\begin{array}{ccccc}P\left(B|j,m\right)& =& \alpha P\left(B,j,m\right)& =& \alpha \sum _e\sum _{a}P\left(B,e,a,j,m\right)\end{array}$$

I really don't understand the $\sum _{e}e$. I thought e meant there was an earthquake whereas E represented the probability distribution. Why isn't the equation:

$$\begin{array}{ccccc}P\left(B|j,m\right)& =& \alpha P\left(B,j,m\right)& =& \alpha \sum _e\sum _{a}P\left(B,E,A,j,m\right)\end{array}$$

The syntax I'm going to use is:

$$\begin{array}{ccc}\sum _{y}P\left(Y\right)& =& P\left(y\right)+P\left(\neg y\right)\end{array}$$

The first step is to reconsider the problem in terms of the known conditional independences from the Baysean network:

$$\begin{array}{ccccc}P\left(B|j,m\right)& =& \alpha \sum _e\sum _{a}P\left(B,E,A,j,m\right)& =& \alpha \sum _e\sum _{a}P\left(B\right)P\left(E\right)P\left(A|B,E\right)P\left(j|A\right)P\left(m|A\right)\end{array}$$

Under the laws of summation, this is equivalent to:

$$\alpha P\left(B\right)\sum _{e}P\left(E\right)\sum _{a}P\left(A|B,E\right)P\left(j|A\right)P\left(m|A\right)$$

The next steps involve working through the equation from right to left producing a set of factors. Factors are produced in several ways.

For $P\left(m|A\right)$, m is a fixed value, and the factor for a fixed value is simply:

$$\begin{array}{ccc}{f}_m\left(A\right)& =& \left(\genfrac{}{}{0ex}{}{P\left(m|a\right)}{P\left(m|\neg a\right)}\right)\end{array}$$

Similarly for $P\left(j|A\right)$, j is a fixed value:

$$\begin{array}{ccc}{f}_j\left(A\right)& =& \left(\genfrac{}{}{0ex}{}{P\left(j|a\right)}{P\left(j|\neg a\right)}\right)\end{array}$$

There is another notational change here. Russell and Norvig use:

$$\begin{array}{ccccc}{f}_j\left(A\right)& =& f_J\left(j,A\right)& =& \left(\genfrac{}{}{0ex}{}{P\left(j|a\right)}{P\left(j|\neg a\right)}\right)\end{array}$$ $$\begin{array}{ccc}{f}_J\left(J,A\right)& =& \left(\begin{array}{cc}P\left(j|a\right)& P\left(j|\neg a\right)\\ P\left(j|\neg a\right)& P\left(\neg j|\neg a\right)\end{array}\right)\end{array}$$

Since $f_j\left(A\right)$ is the pairing of j with the elements from A, I am going to use $f_J\left(A\right)$ as the pairings of the elements of J with the elements of A. This is more intuitive since what would the notation $f_J\left(A\right)$ mean in Russell and Norvig's representation? It is a factor of what with the elements of A? If J needs to be present in the argument list to represent its inclusion in the factor then $f_J\left(A\right)$ doesn't make sense. So, for my notation, $f_J\left(J,A\right)$ is a 2×2×2 matrix since there's a dimension for each axis. Specifically:

$$\begin{array}{ccc}{f}_J\left(J,A\right)& =& f_j\left(A,J\right)\circlearrowleft f_{\neg j}\left(A,J\right)\\ & =& \left(\begin{array}{cc}P\left(j|a,j\right)& P\left(j|\neg a,j\right)\\ P\left(j|a,\neg j\right)& P\left(j|\neg a,\neg j\right)\end{array}\right)\circlearrowleft \left(\begin{array}{cc}P\left(\neg j|a,j\right)& P\left(\neg j|\neg a,j\right)\\ P\left(\neg j|a,\neg j\right)& P\left(\neg j|\neg a,\neg j\right)\end{array}\right)\\ & =& \left(\begin{array}{cc}1& 1\\ 0& 0\end{array}\right)\circlearrowleft \left(\begin{array}{cc}0& 0\\ 1& 1\end{array}\right)\end{array}$$

Where A↺B represents that A and B are the unstacked layers of a three-dimensional matrix. The above result is not useful in any way to the best of my knowledge, it simply serves to illustrate the meaning of the syntax and show the procedure for a three dimensional expansion.

For the next term, $P\left(A|B,E\right)$, dealing with the conditional probability on B and E, the factor is:

$$\begin{array}{ccc}{f}_A\left(B,E\right)& =& f_a\left(B,E\right)\circlearrowleft f_{\neg a}\left(B,E\right)\\ & =& \left(\begin{array}{cc}P\left(a|b,e\right)& P\left(a|b,\neg e\right)\\ P\left(a|\neg b,e\right)& P\left(a|\neg b,\neg e\right)\end{array}\right)\circlearrowleft \left(\begin{array}{cc}P\left(\neg a|b,e\right)& P\left(\neg a|b,\neg e\right)\\ P\left(\neg a|\neg b,e\right)& P\left(\neg a|\neg b,\neg e\right)\end{array}\right)\end{array}$$

The next element in the equation is the summation over a. Factors may be combined with a type of summation where:

$$\begin{array}{ccc}{f}_{\stackrel{\_}{A},j,m}\left(B,E\right)& =& \sum _a{f}_A\left(B,E\right)×f_j\left(A\right)×f_m\left(A\right)\\ & =& f_a\left(B,E\right)×f_j\left(a\right)×f_m\left(a\right)+f_{\neg a}\left(B,E\right)×f_j\left(\neg a\right)×f_m\left(\neg a\right)\end{array}$$

The operation × is the pointwise product. The pointwise product of two factors yields a new factor that is the union of the variables in the factors. Consider one of the elements in the previous equation: (Note that this operation divides the levels of f_A(B,E) and reduces the dimensionality by a level.

$$\begin{array}{ccc}{f}_a\left(B,E\right)×f_j\left(a\right)×f_m\left(a\right)& =& \left(\begin{array}{cc}P\left(a|b,e\right)& P\left(a|b,\neg e\right)\\ P\left(a|\neg b,e\right)& P\left(a|\neg b,\neg e\right)\end{array}\right)×\left(P\left(j|a\right)\right)×\left(P\left(m|a\right)\right)\\ & =& \left(\begin{array}{cc}0.95& 0.94\\ 0.29& 0.001\end{array}\right)\times \left(0.9\right)\times \left(0.7\right)\\ & =& \left(\begin{array}{cc}\left(0.95\right)\left(0.63\right)& \left(0.94\right)\left(0.63\right)\\ \left(0.29\right)\left(0.63\right)& \left(0.001\right)\left(0.63\right)\end{array}\right)\\ & =& \left(\begin{array}{cc}0.5985& 0.5922\\ 0.1827& 0.00063\end{array}\right)\end{array}$$

The process is the same for ¬a, and that factor is:

$$\begin{array}{ccc}{f}_{\neg a}\left(B,E\right)×f_j\left(\neg a\right)×f_m\left(\neg a\right)& =& \left(\begin{array}{cc}0.05& 0.6\\ 0.71& 0.999\end{array}\right)\times \left(0.1\right)\times \left(0.3\right)\\ & =& \left(\begin{array}{cc}0.0015& 0.0018\\ 0.0213& 0.02997\end{array}\right)\end{array}$$

The sum of those factors then is:

$$\begin{array}{ccc}{f}_{\stackrel{\_}{A},j,m}\left(B,E\right)& =& \sum _a{f}_A\left(B,E\right)×f_j\left(A\right)×f_m\left(A\right)\\ & =& f_a\left(B,E\right)×f_j\left(a\right)×f_m\left(a\right)+f_{\neg a}\left(B,E\right)×f_j\left(\neg a\right)×f_m\left(\neg a\right)\\ & =& \left(\begin{array}{cc}0.5985& 0.5922\\ 0.1827& 0.00063\end{array}\right)+\left(\begin{array}{cc}0.0015& 0.0018\\ 0.0213& 0.02997\end{array}\right)\\ & =& \left(\begin{array}{cc}0.5985+0.0015& 0.5922+0.0018\\ 0.1827+0.0213& 0.00063+0.02997\end{array}\right)\\ & =& \left(\begin{array}{cc}0.6& 0.594\\ 0.204& 0.0306\end{array}\right)\end{array}$$

Note that the process of summing $f_A\left(B\right)$ to $f_{\stackrel{\_}{A}}\left(B\right)$ reduced $f_A\left(B\right)$ from a 2×2 matrix to a 2×1. In general, summing will remove a dimension from the matrix.

The next element in the equation is $P\left(E\right)$ this is simply the probabilities of E not conditional on anything, and the factor is represented as:

$$\begin{array}{ccc}{f}_E& =& \left(\begin{array}{c}P\left(e\right)\\ P\left(\neg e\right)\end{array}\right)\end{array}$$

This is also a deviation from Russell and Norvig who represent this quantity as $f_E\left(e\right)$.

The next element in the equation is a summation over e which, as before, produces:

$$\begin{array}{ccc}{f}_{\stackrel{\_}{E},\stackrel{\_}{A},j,m}& =& \sum _e{f}_E×f_{\stackrel{\_}{A},j,m}\left(B,E\right)\\ & =& f_e×f_{\stackrel{\_}{A},j,m}\left(B,E\right)+f_{\neg e}×f_{\stackrel{\_}{A},j,m}\left(B,E\right)\\ & =& \left(P\left(e\right)\right)\times f_{\stackrel{\_}{A},j,m}\left(B,E\right)+\left(P\left(\neg e\right)\right)f_{\stackrel{\_}{A},j,m}\left(B,E\right)\\ & =& \left(0.002\right)\times \left(\begin{array}{cc}0.6& 0.594\\ 0.204& 0.0306\end{array}\right)+\left(0.998\right)\times \left(\begin{array}{cc}0.6& 0.594\\ 0.204& 0.0306\end{array}\right)\\ & =& \left(0.002\right)\times \left(\begin{array}{cc}0.6& 0.594\\ 0.204& 0.0306\end{array}\right)+\left(0.998\right)\times \left(\begin{array}{cc}0.6& 0.594\\ 0.204& 0.0306\end{array}\right)\end{array}$$ $$\begin{array}{ccc}P\left(B|j,m\right)& =& \left(\begin{array}{c}0.284\\ 0.716\end{array}\right)\end{array}$$

By counting:

• Enumeration: 24
• Elimination: 7

An examination of this question requires an application of chaining for a first-order Markov process which states:

$$\begin{array}{ccc}P\left(X_t|u_{1:t}\right)& =& \alpha P\left(u_t|X_t\right)\sum _{r\in X_{t-1}}P\left(X_t|r,u_{1:t-1}\right)P\left(r|u_{1:t-1}\right)\\ & =& \alpha P\left(u_t|X_t\right)\sum _{r\in X_{t-1}}P\left(X_t|r\right)P\left(r|u_{1:t-1}\right)\end{array}$$

This function allows the probability of a given event to be built up from a given set of evidence. Like any chain however, it must have an end. In this case, that end is P(R₀) = <P(r₀),P(¬r₀)> which is the probability distribution for rain on day 0.

For the sake of simplicity, P(R₀) will be assumed to be fixed at <0.5,0.5>. If, as the question asks, the distribution is converging on a fixed value, then the start point for the convergance should not matter.

The calculations start off with a computation of the probability distribution for rain on day 1 which is slightly different from other calculations because P(R₀|u₀) is defined as P(R₀).

Now, this value may be used for the first link in the chain:

The next link progresses in the same way, but u₁ is now defined and meaningful:

The next link in the chain is:

To do one more iteration to solidify the pattern:

The effect of having an umbrealla present every day means that the factors remain the same. The actual math has to date eluded me, but this program will estimate the converged value to an arbitrary number of decimal places. The value it comes up with is, to 50 places:

<0.89674554944846594496715149092767174611258015717335, 0.10325445055153405503284850907232825388741984282665>