Episode #125 of the Stack Overflow podcast is here. We talk Tilde Club and mechanical keyboards. Listen now

2 of 8 showed the non-decreasing claim

"this class of problems lie"s in RE, so its name is "RE".

$$\operatorname{Prob}(\hspace{.02 in}M \text{ accepts}) \; = \; \operatorname{Prob}\hspace{-0.04 in}\big(\hspace{-0.02 in}(\exists n)(\hspace{.02 in}M \text{ accepts after exactly } n \text{ steps})\big)$$
$$=$$

$$\displaystyle\sum_n \operatorname{Prob}(\hspace{.02 in}M \text{ accepts after exactly } n \text{ steps})$$

$$=$$
$$\displaystyle\lim_N \left(\displaystyle\sum_{n\leq \hspace{.02 in}N} \operatorname{Prob}(\hspace{.02 in}M \text{ accepts after exactly } n \text{ steps})\hspace{-0.04 in}\right)$$

$$=$$

$$\displaystyle\lim_N \: \operatorname{Prob}(\hspace{.02 in}M \text{ accepts in at most } N \text{ steps}) \;\;\; = \;\;\; \displaystyle\lim_n \: \operatorname{Prob}(\hspace{.02 in}M \text{ accepts in at most } n \text{ steps})$$

For all $$m$$ and $$n$$, if $$\: m\leq n \:$$ then for all randomness strings $$r$$,

$$\text{on randomness } r, \: M \text{ accepts in at most } m \text{ steps}$$
$$\iff$$
$$(\exists t)\big((\text{on randomness } r, \: M \text{ accepts after exactly } t \text{ steps}) \: \text{ and } \: t\leq m\big)$$
$$\implies$$
$$(\exists t)\big((\text{on randomness } r, \: M \text{ accepts after exactly } t \text{ steps}) \: \text{ and } \: t\leq n\big)$$
$$\iff$$
$$\text{on randomness } r, \: M \text{ accepts in at most } n \text{ steps}$$

.

For all $$m$$ and $$n$$, if $$\: m\leq n \:$$ then $$\operatorname{Prob}(\hspace{.02 in}M \text{ accepts in at most } m \text{ steps}) \; \leq \; \operatorname{Prob}(\hspace{.02 in}M \text{ accepts in at most } n \text{ steps}) \;\;\;\;$$.

$$\frac12 \;\; < \;\; \operatorname{Prob}(\hspace{.02 in}M \text{ accepts})$$

$$\iff$$

$$\frac12 \;\; < \;\; \displaystyle\lim_n \: \operatorname{Prob}(\hspace{.02 in}M \text{ accepts in at most } n \text{ steps})$$

$$\iff$$

$$(\exists n)\left(\frac12 < \operatorname{Prob}(\hspace{.02 in}M \text{ accepts in at most } n \text{ steps})\hspace{-0.02 in}\right)$$

 answered Dec 9 '14 at 23:48 user12859