User dinesh - MathOverflow

Answer by Dinesh for Computing channel capacities for non-symmetric channels

2012-05-10T02:55:40Z

Given a memoryless ergodic channel $P(Y|X)$, the Shannon capacity of that channel $C$ is given by $C = \max_{p(x)} I(X;Y)$ where $I(\cdot,\cdot)$ is the mutual information and the maximization is over all input distributions (possibly subject to some constraints such as transmit power). This statement does not assume anything about the symmetric nature of the channel.

In the example that you mentioned (I am assuming that $P(Y=1 | X = 0) = p_1$ and $P(Y=0 | X = 1) = p_2$ which is the reverse of your notation), the capacity can be calculated as follows. Let us assume that $P(X = 0) = \alpha$ and $P(X = 1) = \beta = 1 - \alpha$. Also, let $q_i = 1-p_i$ for $i = 1,2$. The output distribution becomes $P(Y = 0) = \alpha q_1 + \beta p_2$. The conditional entropy of $Y$ given $X$ is

$H(Y|X) = \alpha h(p_1) + \beta h(p_2)$

where $h(\cdot)$ is the binary entropy function. The mutual information is given by

$I(X;Y) = H(Y) - H(Y|X)$ = $h(\alpha q_1 + \beta p_2) - \alpha h(p_1) - \beta h(p_2)$

Optimizing this over $\alpha$ will give us the capacity of this channel. This is messy and probably doesn't have a nice closed form expression which is one of the reasons why such examples don't show up in textbooks.

It is another question to ask how this capacity can be achieved, i.e., what kind of coding over the input alphabets can get us to this capacity? It is in this context that the channel symmetry becomes important - linear codes (which are a very important family of practically relevant codes) can be shown to approach channel capacity only for symmetric channels. Here, the notion of symmetry must be carefully defined but for the simple case of binary channel inputs, it will agree with the obvious definition ($p_1 = p_2$ in your notation).

Answer by Dinesh for Checking whether given binary operation is a group operation

2010-07-14T09:13:03Z

See this entry - http://rjlipton.wordpress.com/2010/06/03/an-amplification-trick-and-stoc-2010/ for a nice discussion on the question you have posed and other related ones. The article also has links to the original papers.

Image of a fixed element under a random endomorphism in an Abelian group

2010-07-03T06:38:58Z

Let $G$ be a finite Abelian group with endomorphism ring $End(G)$. I am interested in the probability $P(\phi(g_1) = g_2)$ for fixed $g_1,g_2 \in G$ and a uniformly chosen endomorphism $\phi(\cdot)$ from $End(G)$. Essentially, I want to understand where the set of endomorphisms will take each element $g \in G$. I ran into this question while considering homomorphic compression schemes that compress an $n$-length sequence $g^n$ into a sequence of length $k$ by applying a homomorphism $\phi \colon G^n \rightarrow G^k$. I describe the question in detail below.

Let $\mathbb{Z}_n$ be the cyclic group of $n$ elements. If $G ={\mathbb{Z}_{p^r}}$ , I understand what is going on and can prove for instance that $\phi(g)$ is uniformly distributed across the smallest subgroup of $\mathbb{Z}_{p^r}$ that $g$ belongs to as $\phi(\cdot)$ varies over $End(\mathbb{Z}_{p^r})$ . But, I am having trouble understanding what happens in the case of groups of the form $\mathbb{Z}_{p^r}^k$ such as $\mathbb{Z}_2^2$ for example. In this case, $\phi(g)$ is uniformly distributed over $\mathbb{Z}_2^2$ for all non-identity $g$ regardless of which subgroup $g$ belongs to.

Question: Is there a uniform way to write down the probability $P(\phi(g_1) = g_2)$ for fixed $g_1,g_2 \in G$ and an arbitrary $\phi(\cdot) \in End(G)$ for a finite Abelian group $G$?

I would greatly appreciate any pointers and hope the question isn't too elementary for MO. Please feel free to edit/re-tag the question if needed.

Answer by Dinesh for What is your favorite "strange" function?

2010-04-22T15:47:14Z

Minkowski's question mark function if only for the strange $?(\cdot)$ notation.

Answer by Dinesh for What are some mathematical concepts that were (pretty much) created from scratch and do not owe a debt to previous work?

2010-04-16T21:51:17Z

Shannon's work on Information theory. Maybe the math wasn't new but the ideas (such as positing a qualitative metric of information and identifying its relevance to design of communication systems) definitely were.

Answer by Dinesh for What should be offered in undergraduate mathematics that's currently not (or isn't usually)?

2010-03-15T05:35:51Z

Caveat: My undergraduate & graduate studies were both not in Math but in Engineering. But I would love to have taken a course on the history of mathematics and I think this isn't a commonly offered course. There are lots of compelling stories here and it also gives a great perspective on how the different areas of math came to be born (non-Euclidean geometry from work on the parallel postulate to name one). Knowing how a subject evolved historically can give a nice perspective on the subject especially when a formal course on the subject might not necessarily follow the same order of ideas.

Answer by Dinesh for Cool problems to impress students with group theory

2010-01-29T23:04:17Z

I love the proof of Wilson's theorem through consideration of the multiplicative group of integers modulo-p. The solution is very slick and it wasn't until I saw this early in an undergraduate course that I truly understood the power of group theory and its wide range of applicability. It also has a nice bit of history to it: After neither Wilson nor his mentor Warring was able to give a proof of the assertion, Gauss remarked in Disquisitiones Arithmeticae: "And Waring confessed that the proof seemed the more difficult, since one cannot imagine any notation to express a prime number. – In our opinion, however, such truths should be extracted from notions rather than from notations".

Number of uniform rvs needed to cross a threshold

2010-01-03T06:47:22Z

Let $N(x)$ be the number of uniform random variables (distributed in $[0,1]$) that one needs to add for the sum to cross $x$ ($x > 0$). The expected value of $N(x)$ can be calculated and it is a very cool result that $E(N(1)) = e$. The expression for general $x$ is

$E(N(x)) = \sum_{k=0}^{[x]} (-1)^k \frac{(x-k)^k}{k!} e^{x-k}$

where $[x]$ is the largest integer less than $x$. When $x$ is large, this function $E(N(x))$ grows linearly (as one would expect). Computer simulations suggest that $E(N(x)) \approx 2x + 2/3$. My question is as follows: is it possible to guess this form for $E(N(x))$ without actually computing it? The $2x$ part is intuitive but is there a good intuition for why there is an additive constant and why that value is $2/3$?

My motivation is as follows: When I computed $E(N(x))$ using the formula above for large values of $x$, I came across this asymptotic and found it surprising that a polynomial equation in powers of $e$ gives values that are very close to a rational number. I am very interested in knowing the reason (if any) behind it. Thanks in advance for any help.

Answer by Dinesh for Favorite popular math book

2009-12-29T23:17:06Z

Title: Gamma : Exploring Euler's constant

Author : Julian Havil

Short description: Provides a fascinating history of a constant that doesn't get nearly as much attention as $e$ or $\pi$. Definitely has more math than most books intended for a general audience but I feel the book is accessible to those who persevere with it. And the reward is lots and lots of beautiful mathematics.

Answer by Dinesh for "Embedding" functions in groups

2009-12-29T09:13:01Z

Thanks to all of you for your responses. For some reason (not enough rep points?), I don't see an "add comment" and so am posting this as an answer.

@Barton: I am interested in distributed function reconstruction where $x$ and $y$ are separately communicated to a computer who is interested in computing $f(x,y)$ and the problem is to minimize the rate of transmission of $x$ and $y$. I have a scheme that can do this whenever the function to be reconstructed is the group operation of some Abelian group (based on linear codes over that group). For other functions, I simply argue that they can be "embedded" in some group and thus can be reconstructed. My formal notation for this is very cumbersome and I was merely wondering if there is a neater way to characterize this notion. Towards this end, I would be interested in the following problem too: Given $f(x,y)$, is there an easy way to characterize all the Abelian groups (not necessarily the smallest) in which it can be embedded?

@Figueroa-O'Farrill: It is true that we need the function to be symmetric. Thanks for pointing it out.

Comment by Dinesh

2011-12-12T20:39:50Z

Don't you need a constraint on the rate of the code $C$? Otherwise, you can transmit $A$ uncoded and choose the reconstruction $\hat{A}$ such that $L(A,\hat{A})$ is minimized. If you constrain the rate of $C$ to $R$, the minimum distortion that you can achieve is the Shannon rate-distortion function $R(D)$. To approach this, you typically need to code over $A^n$ where the block length $n$ is very large. Except in some special cases, the optimal codebooks have little structure to them and aren't easy to build/describe.

Comment by Dinesh

2010-11-30T07:27:57Z

I thought this was very cool when I saw it first. But doesn't the same claim hold with more prosaic choices for $x,y$ like $e^{\ln 2}$?

Comment by Dinesh

2010-10-19T03:22:59Z

MathOverflow is for research level math questions. You will have a better chance of getting an answer by asking this question at math.stackexchange.com/questions

Comment by Dinesh

2010-07-07T01:38:18Z

@Robin,t3suji and Tom: Thanks for your comments. I am still trying to grok the arguments. I don't have much exposure to group theory but I hope to get there soon :) I am hoping to specialize Robin's answer and the ensuing comments to the case of $\mathbb{Z}_4$ vs $\mathbb{Z}_2^2$ and go from there. Thanks again.

Comment by Dinesh

2010-05-31T16:12:18Z

John Baez also has a couple of articles about the number 24 and the Leech lattice in his excellent expository articles - math.ucr.edu/home/baez/numbers/24.pdf and math.ucr.edu/home/baez/week95.html

Comment by Dinesh

2010-04-08T18:41:07Z

Yet another relation between tilings and Fibonacci numbers - this one was posed in IBM's ponder this challenge (domino.research.ibm.com/Comm/wwwr_ponder.nsf/…). The site provides a rough solution in the asymptotic regime but the exact expression would involve Fibonacci numbers.

Comment by Dinesh

2010-04-04T03:33:34Z

Mathworld(mathworld.wolfram.com/LambertW-Function.html) gives an asymptotic expression which if restricted to the first two terms gives $x \approx \frac{\log y}{\log \log y}$ as noted in gowers' answer. You can add more terms if need be to reach your desired level of accuracy.

Comment by Dinesh

2010-04-04T03:19:54Z

$g(y) = e^{W(\log y)}$ where $W(\cdot)$ is the Lambert W-function. Asymptotics of the Lambert W function is probably well studied. The Wikipedia article on the Lambert W function would be a good place to start.

Comment by Dinesh

2010-01-26T00:11:54Z

Thanks Douglas. I was curious about what happens when the uniform rvs are replaced by other rvs. Nice analysis. On an unrelated note, most of the Latex didn't parse correctly for me while some formulae did parse correctly. I couldn't edit the response either (not enough reps?). Anyone else having the same trouble?

Comment by Dinesh

2010-01-03T07:39:26Z

I was thinking of E(N(1))=e as a transient that dies away as x goes to infinity and the steady state behavior being just E(N(x)) = 2x. But in light of Leonid's answer below, I think I understand your point. Thanks.

Comment by Dinesh

2010-01-03T07:37:22Z

Beautifully explained. Thanks.

Comment by Dinesh

2009-12-29T09:31:33Z

Qiaochu, I see the mistake in that argument. I was trying to get the cardinality of the group down from 2^|S| in Jason's argument to |S|^2. I will edit the post accordingly. Thanks.