Algorithm to generate free unlabelled trees uniformly at random

I am implementing an algorithm to generate free unlabelled trees uniformly at random (uar). For this I found this paper by Herbert S. Wilf (The uniform selection of trees. 1981. In Journal of Algorithms). This paper defines the procedure Free which generates free unlabelled trees by calling one of two smaller procedures (either Bicenter or … Read more

Expectation of multiplied random variables given their individual expectations

Suppose that I have two non-negative real valued random variables x,y∈Z+ that always satisfy x+y≤1. Also suppose that E[x]=1/2 and E[y]=1/4. What is the maximum possible value of E[xy]? Can it be larger than 1/8? More generally, is there a systematic way of analyzing E[xy] for say other values of E[x] and E[y]? (You can … Read more

Existence of normal number except random numbers

For normality, see https://en.wikipedia.org/wiki/Normal_number. For random number/sequence, see https://en.wikipedia.org/wiki/Algorithmically_random_sequence. Now, is there any number that is normal in every bases $b > 1$ except random numbers (or numbers expansion of which is algorithmically random sequence)? I suspect, there is only normal number in some bases except random number, normality in every bases $b>1$ is a … Read more

Subsequence of a sequence of digits of an algebraic irrational number

Consider an algebraic irrational number in $(0,1)$ with binary expansion $x = \sum_{n\ge 1} \frac{a_n}{2^n}$. Is it possible that the number $\sum_{n\ge 1}\frac{a_{2n}}{2^n}$ is again algebraic irrational ? My opinion is no. Heuristics: it should be difficult to determine binary expansions of other algebraic irrationals, even if we have a supply of other expansions, except … Read more

On earlier references for $P=BPP$ and Kolmogorov’s possible view on modern breakthroughs involving randomness?

Kolmogorov and Uspenskii in this paper ‘http://epubs.siam.org/doi/pdf/10.1137/1132060‘ speculate $P=BPP$ in $1986$. They do this without getting into circuit lower bounds and from a different view which for people like me is more well grounded than basing on some other unknown and pure beliefs. Is there a reference on $P=BPP$ possibility earlier than this that goes … Read more

Cohesive set with degree below non-high Martin-Löf random reals

A set A is cohesive if $A\subseteq ^* W_e$ or $A\subseteq^* \bar{W_e}$ for each $e\in \omega$ (standard enumeration of r.e. sets). By Jockusch and Stephan’s 1993 paper ‘A cohesive set which is not high.’, this is equivalent to saying that A is r-cohesive, i.e. restricted to those recursive sets $W_e$. My question is if given … Read more

What is the precise relation between Kolmogorov complexity and Shannon’s entropy?

Consider the discrete case: Shannon’s entropy is $H(x)=-\sum\limits_i^n p(x_i) log\space p(x_i)$. Probability based on prefix-free Kolmogorov complexity is $R(x_i)=2^{-K(x_i)}$ where $K(x_i)$ is the prefix-free Kolmogorov complexity of $x_i$. What is the relation between $R(x_i)$ and $p(x_i)$? Are they equal? I remember vaguely that a book has discuss on the relation without any precise result. Answer … Read more

Complete list of exceptions and efficient algorithm for Waring’s problem

2 weeks ago, Samir Siksek https://arxiv.org/abs/1505.00647 proved the more than 150-years-old conjecture that every positive integer other than 15, 22, 23, 50, 114, 167, 175, 186, 212, 231, 238, 239, 303, 364, 420, 428, 454 is a sum of at most seven positive cubes. It was known long ago that every sufficiently large integer is … Read more

Can you get a fair coin flip by rolling a fair, 5-sided die a finite number of times?

Can you get a fair coin flip by rolling a fair, 5-sided die a finite number of times? Answer I think the subtlety here is that one can imagine all sorts of complicated criteria hidden inside the “finite” method. But, however complex the method is, in the end it has to come down to looking … Read more

Set of Natural Numbers, Choice, Computer Programs

I am aware that the following question/discussion is ill-defined, and perhaps has more to do with philosophy than mathematics. My brother and I were talking and the topic came to “picking a random natural number.” I told him that to my best knowledge, as well as to my logic, there is no such thing as … Read more