# Tag Info

1

It never hurts to write "uniform" or "equal probability" to make things clear. Where there is some symmetry or no natural non-uniform distribution, it is often implicit that the probability measure should be uniform or should respect that symmetry. Unless stated otherwise, a "random" pair of distinct elements of a finite set means one chosen from the ...

1

There are many many positions that require 20 moves to solve, so I'd say the position that qualifies as "most scrambled" among them is the one that has fewest alternative paths to the sorted state. I have downloaded Herbert Kociemba's Cube Explorer (half-turn version) from http://kociemba.org/cube.htm and have been using it to track some 20-move positions. ...

0

This event is contained in the events that contain a finite number of these restrictions. The event with the first $k$ such restrictions has probability $2^{-k}$. Since the probability of your event is bounded above by these probabilities, it must be $0$. (To be rigorous, you might also want to show that it's measurable; I'm assuming that.)

0

There are only countably many Turing machines, and thus countably many sequences that they generate. For any iid sequence $X_n$ of random variables that is not almost surely constant, the probability of a particular sequence of values is $0$, and thus by countable additivity the probability of a Turing-computable sequence is $0$.

3

Let $\alpha \in (0,1): \quad \alpha=0.a_1a_2\cdots a_n \cdots \quad$ where the $a_n$ are numbers generated by a physical generator of genuinely random numbers (if it exists). Th[e]n it seems that $\color{blue}{\alpha\text{ should be a noncomputable number}}$. Is this statement true? If this can be understood as referring to an infinite sequence of ...

0

There is a bijection between walks which satisfy $S_n=k,M_n=r$ and walks which satisfy $S_n=2r-k$. To see that, reflect the path from the first time the walk reaches $r$ about $r$, so that from that point on +1 becomes -1 and vice versa.

1

Suppose you are aiming to do $2n$ tosses ending up with $n$ heads and $n$ tails, and so far you have seen $h$ heads and $t$ tails Then the probability that the next toss is heads should be $\dfrac{n-h}{2n-h-t}$ and you can write your program to simulate this This is make all the ${ 2n \choose n}$ possible patterns of heads and tails equally likely, ...

2

The answer is yes. As a concrete example of (1), suppose $X_1, X_2, X_3$ are exchangeable. We show $X_1, X_3$ are exchangeable by filling in the omitted slots with the 'everything' event: \begin{align} P(X_1\in A, X_3\in B)&=P(X_1\in A, X_2\in{\mathbb R}, X_3\in B)\\ &\stackrel{(*)}=P(X_3\in A, X_2\in {\mathbb R}, X_1\in B)\\ &=P(X_3\in A, ...

1

What is the name of this approach in the literature? This is called block entropy; however, it has two different interpretations, corresponding to the following two different scenarios. In both scenarios we have a fixed string of symbols $y_1..y_n$, each from a finite alphabet $A$, and $H(X)=-\ E\ \log(p(X))$ denotes the Shannon entropy of a random ...

1

It seems to me that iid is the only way (1) and (2) can hold. First, the vector comprising any three of the $\epsilon_k$s is independent of the triple comprising the other three. Thus, for example, $(\epsilon_1,\epsilon_3,\epsilon_4)$ is independent of $(\epsilon_2,\epsilon_5,\epsilon_6)$. Marginalizing, $\epsilon_1$ is independent of $\epsilon_2$; and ...

2

is there a formal measure of bitwise entropy that takes into account these factors? You're using the term entropy in reference to some given finite string, whereas entropy is a function defined on probability distributions. One way of reconciling this is to suppose that the relevant probability distributions are the actual ("empirical") distributions of ...

Top 50 recent answers are included