User dinesh - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-18T05:21:34Z http://mathoverflow.net/feeds/user/2878 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/96493/computing-channel-capacities-for-non-symmetric-channels/96529#96529 Answer by Dinesh for Computing channel capacities for non-symmetric channels Dinesh 2012-05-10T02:55:40Z 2012-05-10T02:55:40Z <p>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.</p> <p>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 </p> <p>$H(Y|X) = \alpha h(p_1) + \beta h(p_2)$ </p> <p>where $h(\cdot)$ is the binary entropy function. The mutual information is given by </p> <p>$I(X;Y) = H(Y) - H(Y|X)$ = $h(\alpha q_1 + \beta p_2) - \alpha h(p_1) - \beta h(p_2)$</p> <p>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.</p> <p>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).</p> http://mathoverflow.net/questions/31814/checking-whether-given-binary-operation-is-a-group-operation/31815#31815 Answer by Dinesh for Checking whether given binary operation is a group operation Dinesh 2010-07-14T09:13:03Z 2010-07-14T09:13:03Z <p>See this entry - <a href="http://rjlipton.wordpress.com/2010/06/03/an-amplification-trick-and-stoc-2010/" rel="nofollow">http://rjlipton.wordpress.com/2010/06/03/an-amplification-trick-and-stoc-2010/</a> for a nice discussion on the question you have posed and other related ones. The article also has links to the original papers.</p> http://mathoverflow.net/questions/30377/image-of-a-fixed-element-under-a-random-endomorphism-in-an-abelian-group Image of a fixed element under a random endomorphism in an Abelian group Dinesh 2010-07-03T06:38:58Z 2010-07-04T06:21:20Z <p>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.</p> <p>Let <code>$\mathbb{Z}_n$</code> be the cyclic group of $n$ elements. If <code>$G ={\mathbb{Z}_{p^r}}$</code>, 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 <code>$\phi(\cdot)$</code> varies over <code>$End(\mathbb{Z}_{p^r})$</code>. But, I am having trouble understanding what happens in the case of groups of the form <code>$\mathbb{Z}_{p^r}^k$</code> 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. </p> <blockquote> <p>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$? </p> </blockquote> <p>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.</p> http://mathoverflow.net/questions/22189/what-is-your-favorite-strange-function/22205#22205 Answer by Dinesh for What is your favorite "strange" function? Dinesh 2010-04-22T15:47:14Z 2010-04-22T15:47:14Z <p>Minkowski's question mark function if only for the strange $?(\cdot)$ notation.</p> http://mathoverflow.net/questions/21562/what-are-some-mathematical-concepts-that-were-pretty-much-created-from-scratch/21620#21620 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? Dinesh 2010-04-16T21:51:17Z 2010-04-16T22:16:44Z <p>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.</p> http://mathoverflow.net/questions/3973/what-should-be-offered-in-undergraduate-mathematics-thats-currently-not-or-isn/18244#18244 Answer by Dinesh for What should be offered in undergraduate mathematics that's currently not (or isn't usually)? Dinesh 2010-03-15T05:35:51Z 2010-03-15T05:35:51Z <p>Caveat: My undergraduate &amp; 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.</p> http://mathoverflow.net/questions/13320/cool-problems-to-impress-students-with-group-theory/13434#13434 Answer by Dinesh for Cool problems to impress students with group theory Dinesh 2010-01-29T23:04:17Z 2010-01-29T23:04:17Z <p>I love the proof of <a href="http://en.wikipedia.org/wiki/Wilson%27s%5Ftheorem" rel="nofollow">Wilson's theorem</a> 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 <em>Disquisitiones Arithmeticae</em>: "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". </p> http://mathoverflow.net/questions/10567/number-of-uniform-rvs-needed-to-cross-a-threshold Number of uniform rvs needed to cross a threshold Dinesh 2010-01-03T06:47:22Z 2010-01-24T09:31:33Z <p>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 </p> <p>$E(N(x)) = \sum_{k=0}^{[x]} (-1)^k \frac{(x-k)^k}{k!} e^{x-k}$</p> <p>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$?</p> <p>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.</p> http://mathoverflow.net/questions/8609/favorite-popular-math-book/10078#10078 Answer by Dinesh for Favorite popular math book Dinesh 2009-12-29T23:17:06Z 2009-12-29T23:17:06Z <p><strong>Title</strong>: Gamma : Exploring Euler's constant</p> <p><strong>Author</strong> : Julian Havil</p> <p><strong>Short description</strong>: 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.</p> http://mathoverflow.net/questions/9996/embedding-functions-in-groups/10012#10012 Answer by Dinesh for "Embedding" functions in groups Dinesh 2009-12-29T09:13:01Z 2009-12-29T09:28:33Z <p>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.</p> <p>@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?</p> <p>@Figueroa-O'Farrill: It is true that we need the function to be symmetric. Thanks for pointing it out.</p> http://mathoverflow.net/questions/83248/optimal-lossy-coding-under-known-utility-function Comment by Dinesh Dinesh 2011-12-12T20:39:50Z 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. http://mathoverflow.net/questions/40337/ingenuity-in-mathematics/40400#40400 Comment by Dinesh Dinesh 2010-11-30T07:27:57Z 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}$? http://mathoverflow.net/questions/42733/how-can-i-compute-the-pmf-of-a-random-sum Comment by Dinesh Dinesh 2010-10-19T03:22:59Z 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 <a href="http://math.stackexchange.com/questions" rel="nofollow">math.stackexchange.com/questions</a> http://mathoverflow.net/questions/30377/image-of-a-fixed-element-under-a-random-endomorphism-in-an-abelian-group/30378#30378 Comment by Dinesh Dinesh 2010-07-07T01:38:18Z 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. http://mathoverflow.net/questions/26540/4900-a-particularly-square-number/26559#26559 Comment by Dinesh Dinesh 2010-05-31T16:12:18Z 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 - <a href="http://math.ucr.edu/home/baez/numbers/24.pdf" rel="nofollow">math.ucr.edu/home/baez/numbers/24.pdf</a> and <a href="http://math.ucr.edu/home/baez/week95.html" rel="nofollow">math.ucr.edu/home/baez/week95.html</a> http://mathoverflow.net/questions/11885/nontrivial-question-about-fibonacci-numbers/11896#11896 Comment by Dinesh Dinesh 2010-04-08T18:41:07Z 2010-04-08T18:41:07Z Yet another relation between tilings and Fibonacci numbers - this one was posed in IBM's ponder this challenge (<a href="http://domino.research.ibm.com/Comm/wwwr_ponder.nsf/Challenges/June2006.html" rel="nofollow">domino.research.ibm.com/Comm/wwwr_ponder.nsf/&hellip;</a>). The site provides a rough solution in the asymptotic regime but the exact expression would involve Fibonacci numbers. http://mathoverflow.net/questions/20277/approximately-invert-xx Comment by Dinesh Dinesh 2010-04-04T03:33:34Z 2010-04-04T03:33:34Z Mathworld(<a href="http://mathworld.wolfram.com/LambertW-Function.html" rel="nofollow">mathworld.wolfram.com/LambertW-Function.html</a>) 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. http://mathoverflow.net/questions/20277/approximately-invert-xx Comment by Dinesh Dinesh 2010-04-04T03:19:54Z 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. http://mathoverflow.net/questions/10567/number-of-uniform-rvs-needed-to-cross-a-threshold/12812#12812 Comment by Dinesh Dinesh 2010-01-26T00:11:54Z 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? http://mathoverflow.net/questions/10567/number-of-uniform-rvs-needed-to-cross-a-threshold Comment by Dinesh Dinesh 2010-01-03T07:39:26Z 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. http://mathoverflow.net/questions/10567/number-of-uniform-rvs-needed-to-cross-a-threshold/10568#10568 Comment by Dinesh Dinesh 2010-01-03T07:37:22Z 2010-01-03T07:37:22Z Beautifully explained. Thanks. http://mathoverflow.net/questions/9996/embedding-functions-in-groups/10012#10012 Comment by Dinesh Dinesh 2009-12-29T09:31:33Z 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.