TITLE: Regular expresson a's and b's
QUESTION [1 upvotes]: Need to construct a regular expression that recognizes the following language of strings over the alphabet {a,b}:  -  The set of all strings over alphabet {a,b} in which every occurrence of b is followed by at least two a's. For example, the empty string is in this language, as is every string consisting solely of a's. The string abaa is in the language, but aba is not.
What i have come up with is a*b*a{2,}  but that do not accept the empty string.

REPLY [3 votes]: Hint:

If you were to treat "baa" as a single symbol, then your language would be the full language.
The regular expression for the full language over $\Sigma = \{\alpha, \beta\}$ is $(\alpha\mid \beta)^*$.

I hope this helps $\ddot\smile$


TITLE: A.s. convergence of sum
QUESTION [0 upvotes]: Let $A_1,A_2,...,B_1,B_2,...,C_1,C_2,...$ be independent random variables with
$$
EA_n=0, \qquad EA_n^2=1, \qquad EB_n=0, \qquad EB_n^2=n^2
$$
and let $C_n$ be Bernoulli distributed with $P(C_n=1)=\frac{1}{n^2}$.
Assume that $(A_n)_{n\geq1}$ is an IID sequence.
I've shown that
$$
\frac{1}{n}\sum_{i=1}^{n}(A_i+B_iC_i) \xrightarrow{a.s}E(A_1+B_1C_1)=0
$$
and that $\sum_{i=1}^{n}B_iC_i$ converges almost surely to some limit.
However I have now been tasked with showing almost sure convergence of
$
\frac{1}{n}\sum_{i=1}^{n}(A_i+B_iC_i)^2
$
Furthermore I should conclude if it converges to $E((A_1+B_1C_1)^2)$
To tackle this problem I first split the sum like so:
$$
\frac{1}{n}\sum_{i=1}^{n}(A_i+B_iC_i)^2=\frac{1}{n}\sum_{i=1}^{n}A_i^2+\frac{1}{n}\sum_{j=1}^{n}(B_jC_j)^2+\frac{2}{n}\sum_{k=1}^{n}A_k B_kC_k
$$
The first term converges to 1 by the strong law of large numbers, I believe that I have shown that the sums in the second term converges almost surely, since
$$
\sum_{j=1}^{\infty}P((B_jC_j)^2>0)\leq \sum_{j=1}^{\infty}P(C_j=1)=\sum_{j=1}^{\infty}\frac{1}{n^2}<\infty
$$
implies that the terms in $\sum_{j=1}^{n}(B_jC_j)^2$ will be $0$ eventually, thus the sum will have a finite limit. Does this mean, that $\frac{1}{n}\sum_{j=1}^{n}(B_jC_j)^2$ converges almost surely to $0$?
I can apply almost the same argument to $\frac{2}{n}\sum_{k=1}^{n}A_k B_kC_k$, and end up with the same result. However this would mean, that
$$
\frac{1}{n}\sum_{i=1}^{n}(A_i+B_iC_i)^2 \xrightarrow{a.s} 1 \neq 2=E((A_1+B_1C_1)^2)
$$
Am I correct in my reasoning?

REPLY [1 votes]: This is all correct. The main step as you noted is showing that with probability $1$, only finitely many $C_i$ are non-zero. Thus for any sequence $\{X_i\}$, we have $\sum_{i=1}^nX_iC_i$ is almost surely eventually constant, and at any such sample point we obviously have $\frac1n\sum_{i=1}^nX_iC_i\to0$
A couple of things are worth pointing out. That a sequence of independent random variables $\{Z_i\}$ satisfies $\frac1n\sum_{i=1}^nZ_i\to c$ with $c\neq E(Z_1)$ is not particularly surprising - take $\{Z_i\}_{i\ge2}$ iid and $E(Z_1)=E(Z_2)+1$, for instance - but what makes the case $Z_i=(A_i+B_iC_i)^2$ interesting is that $E(Z_i)=E(Z_1)$ for all $i$, so the sequence of averages has constant mean and yet converges to a different constant. This is an example of the more general property that $X_n\to X$ a.s. does not imply $E(X_n)\to E(X)$.
If you want to know why it fails in this case, notice here that the statement "with probability $1$, only finitely many $C_i$ are non-zero" inherently involves looking at all the $C_i$ at once, whereas taking the mean one-by-one will never be able to see this information. So, with probability $1$, there is some constant $M$ such that
$$\frac1n\sum_{i=1}^n(A_i+B_iC_i)^2=\frac1n\sum_{i=1}^nA^2_i+\frac{M}n$$
for $n$ large enough, and so the limit will only depend on $\{A_i\}$. In fact, a similar statement is true if you remove the square, so it is actually the first case (i.e. $\frac1n\sum_{i=1}^n(A_i+B_iC_i)\to E(A_1+B_1C_1)$) that is exceptional in this situation - if $E(B_i)\neq0$, this would no longer be true.


TITLE: Partial Derivative of Mean Absolute Error
QUESTION [1 upvotes]: I have a Linear Function, $Y= a+bX$. The Mean Absolute Error would be
$$f(a,b)=\frac1n \sum |y-(a+bx)|$$
To find the partial derivative I used this formulae
$$\frac{\partial f(x,y)}{\partial x} = \frac{g(x,y)\frac{\partial g(x,y)}{\partial x}}{|g(x,y)|}$$
and arrived at
$$\frac{\partial f}{\partial a}  = \frac{-(y-(a+bx))}{|y-(a+bx)|}$$
$$\frac{\partial f}{\partial b}  = \frac{-x(y-(a+bx))}{|y-(a+bx)|}$$
Is this the right way to do it?

REPLY [0 votes]: Yes, that is the right way. You only have to add the sigma sign. The formula can be derived if you use that $|g(x)|=\sqrt{(g(x))^2}$ , $\forall \ x, g(x) \in \mathbb R$ .
The derivative is $\frac{d}{dx}\sqrt{(g(x))^2}=\frac{d}{dx} \left((g(x))^2\right)^{\frac12}$. Now we apply the chain rule twice.
$$=\frac12\cdot \left((g(x))^2\right)^{-\frac12}\cdot 2\cdot g(x)\cdot g^{'}(x)$$
$$=\frac12\cdot 2\cdot \frac1{ \left((g(x))^2\right)^{\frac12}}\cdot  g(x)\cdot g^{'}(x)=\frac1{ |g(x)|}\cdot  g(x)\cdot g^{'}(x)$$


TITLE: Properties of resolution of singularities
QUESTION [0 upvotes]: Let $X$ be a complex algebraic varieties and $\pi:X' \to X$ be a resolution of singularities of $X$. Let $Y$ be a smooth (irreducible) subvariety of $X$.
Is $\pi^{-1}(Y)$ smooth and irreducible? What if $Y$ is a hypersurface in $X$?

REPLY [1 votes]: No to the first question. For example, the minimal resolution of an isolated surface singularity might require replacing the singular point $p$ of $X$ with $\pi^{-1}(p)$ a chain of rational curves. Then $\pi^{-1}(p)$ is reducible and connected, hence singular.


TITLE: Deriving the 37-percent rule for dating
QUESTION [8 upvotes]: I am trying to prove the theoretical "37-percent rule" for dating.  The setup, if I remember correctly, is this.  Suppose that you will meet exactly $N$ potential mates in your life, and you will meet them one at a time, in a perfectly random order.  The potential mates rank from best to worst (in a total ordering), and you want to maximize the probability that you end up with the best one.  However, you can only tell how good the mates are relative to each other, so while you can fully rank the people you've already met, you can't say anything about the ones you have yet to meet.  Also, for each potential mate, you can either stay with them forever or leave forever, i.e. there is no divorce or post-breakup dating.
The result I have heard, and which I am trying to prove, is that your best strategy is to wait and reject the first 37% of them ($1/e$, to be precise), and then marry the next one that is better than all you have previously met.  The $1/e$ number presumably arises as the limit as $N \to \infty$.
Obviously, you should never marry someone who isn't strictly better than all the previous ones, because then your chances of picking the right one are $0$.  Also, given a strategy that you wait through the first $K$ partners and then marry the next one that is the best so far, I calculate your expected chances of succeeding as
\begin{equation}
\frac{\displaystyle \sum_{M = K}^{N-1} \frac{M - 1 \choose K-1}{N - M}}{N \choose K}
\end{equation}
(Let $M$ be the maximum value among the first $K$ people you meet, where $1$ is the value of the worst person, $2$ is the next, and so on, with your desired mate having value $N$.  Given $M$, your chances of winning are $\frac{1}{N - M}$, because the value $N$ must be the first to appear out of the highest $N - M$ values.  The chances of the maximum being exactly $M$ are ${M - 1\choose K - 1}/{N \choose K}$.)
(The above formula doesn't technically work for $K = 0$, but the reasonable convention ${-1 \choose -1} = 1$ gives the desired value $\frac1N$.)
The two things I am unable to prove, and which I would like to see ideas for, are:

Given that you never pick someone unless they are the best so far, how do you prove further that the best strategy must involve waiting for some $K$ people and then going for anyone else after that $K$?
Why is the formula above optomized at $K = N / e$, and how could one show this?

REPLY [3 votes]: The decision to marry or not need only be made when the current result is better than all previous results (otherwise the current choice is definitely suboptimal).
The choice, at point $K$ to marry or not (provided the $K$th date is better than all before) does not depend on the previous dates in anay ways (aprt from them being worse than the $K$th) because all relatiev orders are equally likely.
Therefore, any optimal strategy must consist of probabilities $p_k$ for $1\le k\le N$ such that when the $k$th date is better than all before, we marry (and stop) with probability $p_k$ and continue otherwise.
Let $q_k$ be the probability of picking the best provided we picked none of the first $k$. Then the probability of picking the best provided we picked none of the first $k-1$ is
$$ q_{k-1}=\frac{\frac1Np_k+\frac{N-k}{N}\frac1k(1-p_k)q_k+\frac{N-k}{N}(1-\frac1k)q_k}{P(\text{none of the first $k-1$ selected})}=\alpha_kp_k+\beta_k$$
($k$th is best and we pick, or best is after $k$ and $k$ is best of first and we don't pick it, or best is after $k$ and $k$ is not best of first)
and hence is clearly maximized at $p_k=0$ ($\alpha<0$) or $p_k=1$ ($\alpha>0$) or in a rare possibility $p_k$ does not matter at all ($\alpha=0$) and can wlog. be selected to be $0$ or $1$.
You can make yourself clear that haveing $p_k=1$ and $p_{k+1}=0$ cannot be optimal.


TITLE: Do orders uniquely describe a group?
QUESTION [7 upvotes]: Possible Duplicate:
Three finite groups with the same numbers of elements of each order

With any finite group $G$ I can associate a multiset $S_G = \{\text{ord}(g) : g \in G\}$. Is the map $G \mapsto S_G$ injective? Is there an algorithm to generate a multiplication table of $G$ from $S_G$? Given any multiset $S$, how hard is it to check if it represents some group in this way?
Having tried a few groups, it does look like an injection, but a formal proof or a construction (brute force aside) escapes me.

REPLY [3 votes]: For a simple counterexample, $\mathbb{Z}_4\times \mathbb{Z}_4$, $\mathbb{Z}_4\rtimes \mathbb{Z}_4$, and $Q_8\times \mathbb{Z}_2$ all have the same multisets of element orders.  In general, the list of element orders does not tell you very much about a group's structure.
I addressed your second question here and your third question here.


TITLE: Convergence or divergence of a sequence
QUESTION [0 upvotes]: Determine the convergence or divergence of
$$\sqrt[n]{n!}$$
I was trying to use the propriety $\lim_{n\to\infty}\sqrt[n]{n}=1$, maybe I can write this
$\lim_{n\to\infty}\sqrt[n]{n!}=\lim_{n\to\infty}\sqrt[n]{n \ \times(n-1)\times(n-2)\times(n-3)\cdots2\ \times \ 1}=\lim_{n\to\infty}\sqrt[n]n \ \times\sqrt[n]{(n-1)}\times\sqrt[n]{(n-2)}\times\sqrt[n]{(n-3)}\cdots\sqrt[n]{2}\ \times \sqrt[n] 1= 1\times1\times1\times1\times1\times\cdots1\times1\times1=1$
Am I right?

REPLY [1 votes]: Whenever I see a factorial somewhere in a problem of limits, I automatically thing about Stirling approximation
$$n!\sim \sqrt{2\pi n}\,\left(\frac n e \right)^n$$ $$\sqrt[n]{n!}\sim (2 \pi n)^{\frac 1{2n}}\,\frac n e $$ So, for large $n$ $$\sqrt[n]{n!}\sim \frac n e $$