Monthly Archives: June 2011

The strong converse for the MAC, part 2

Posted on by

The last time we saw that a packing lemma, together with a good choice of reference output distribution r (the Fano-* distribution) could give a converse for nonstationary DMC:

\log M \le \sum_{t=1}^{n} I(X_t ; Z_t) + (\frac{ 2 }{1 - \lambda} 3 |\mathcal{X}| n)^{1/2} + \log \frac{2}{1 - \lambda}

where the distribution on (X^n,Z^n) is given by the Fano distribution on the codebook, i.e. uniform input distribution on codewords followed by applying the channel. The next step in the argument is to apply this result to the MAC with inputs X and Y.

Continue reading →

Advertisement

A little puzzle

Posted on by

This came up as sub-problem during Young-Han’s group meeting today and we mulled over it for a few minutes but didn’t come up with a non-ugly answer. I’m sure, given the number of Real Mathematicians ™ who read this, that someone out there knows of an “obvious” explanation.

Suppose I give you p integers in an arbitrary order (where p is prime). While maintaining the order and using only addition, multiplication, and parenthesis, is it always possible to make an expression which evaluates to 0 mod p?

I think it’s true, but I’m sure there’s some special property of \mathbb{F}_p that I have forgotten. I guess further generalizations would include whether or not it’s possible for arbitrary p (not necessarily prime), how many elements of an arbitrary field you would need, and so on. I’d ask this on MathOverflow but… meh. It’s probably a homework problem.