Wikipedia:Reference desk/Archives/Mathematics/2016 June 11

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

June 11

Analyzing the multiple choice test

Consider a multiple choice test with $n$ questions, each having two choices, one of which is correct.

Suppose that $x$ answers are known, and so the remaining $n-x$ answers are unknown.

All the known answers are answered correctly, but the unknown answers are guessed randomly.

The number of correctly answered questions is $y$ and so the number of incorrectly answered questions is $n-y$.

The odds are

$2^{x}{\binom {n-x}{n-y}}$

because the number of ways of choosing $n-y$ out of $n-x$ unknown answers is the binomial coefficient, and guessing $n-x$ times provides $2^{-(n-x)}$. The constant factor $2^{-n}$ is omitted.

This odds-table for $n=10$ is computed by J

  5":(2^x)*|:(!/~)n-x=.i.1+n=.10
   1   10   45  120  210  252  210  120   45   10    1
   0    2   18   72  168  252  252  168   72   18    2
   0    0    4   32  112  224  280  224  112   32    4
   0    0    0    8   56  168  280  280  168   56    8
   0    0    0    0   16   96  240  320  240   96   16
   0    0    0    0    0   32  160  320  320  160   32
   0    0    0    0    0    0   64  256  384  256   64
   0    0    0    0    0    0    0  128  384  384  128
   0    0    0    0    0    0    0    0  256  512  256
   0    0    0    0    0    0    0    0    0  512  512
   0    0    0    0    0    0    0    0    0    0 1024

The mean value ± the standard deviation of the number of correctly answered questions is

$y\approx {\frac {n+x\pm {\sqrt {n-x}}}{2}}$

as $y-x$ has a binomial distribution. But this is uninteresting. I want to know the mean value ± the standard deviation of the number of known answers, $x$, knowing the observed number of correctly answered questions, $y$. It can be computed by brute force from the odds-table, but I want a simple formula like the one above. This is why I am requesting your assistance.

The challenge is to simplify the sums

$S_{k}=\sum _{x=0}^{y}x^{k}2^{x}{\binom {n-x}{n-y}}$.

Then it is easy to solve

$\mu ={\frac {S_{1}}{S_{0}}}$

$\mu ^{2}+\sigma ^{2}={\frac {S_{2}}{S_{0}}}$

for $x\approx \mu \pm \sigma$.

Perhaps the sum

$M_{k}=\sum _{x=0}^{y}{\binom {x}{k}}2^{x}{\binom {n-x}{n-y}}$

is easier to simplify analytically. Then

$S_{0}=M_{0}$

$S_{1}=M_{1}$

$S_{2}=2M_{2}+M_{1}$.

Bo Jacoby (talk) 09:33, 11 June 2016 (UTC).

What's your prior probability for $x$ ? Just a uniform distribution ? Jheald (talk) 14:00, 11 June 2016 (UTC)

Yes. Prior to the observation the possibilities $x=0,1,...,n$ are equally credible. Bo Jacoby (talk) 15:42, 11 June 2016 (UTC).

With an appropriate mapping of parameters, can you relate your posterior distribution to a negative binomial distribution? How close can you get? Jheald (talk) 14:14, 11 June 2016 (UTC)

After the observation of $y$ the only possibilities are $x=0,1,...,y$. A negative binomial distribution allows $x=0,1,2,...$ Bo Jacoby (talk) 15:42, 11 June 2016 (UTC).

A tiny simplification: substitute $x=y-i$ and $n=y+m$

$\sum _{x=0}^{y}{\binom {x}{k}}2^{x}{\binom {n-x}{n-y}}=\sum _{i}2^{y-i}{\binom {y-i}{k}}{\binom {m+i}{m}}$

Bo Jacoby (talk) 07:39, 12 June 2016 (UTC).

Your series are hypergeometric, and they don't factor. What sort of answer are you hoping for? --JBL (talk) 16:03, 13 June 2016 (UTC)

Thanks! I am hoping for a reasonable computational complexity (as I don't want to count when computing 28+94). Bo Jacoby (talk) 16:39, 13 June 2016 (UTC).

You already have a single sum of simple-to-compute summands. How much simpler can an answer be? (I don't understand what 28 and 94 have to do with anything.) --JBL (talk) 15:46, 14 June 2016 (UTC)

The formula

$y\approx {\frac {n+x\pm {\sqrt {n-x}}}{2}}$

estimate the number $y$ of correctly answered questions from the number $x$ of known answers. I want a similar formula

$x\approx \mu \pm \sigma$

to estimate the number $x$ of known answers from the number $y$ of correctly answered questions. (Forget about 28 and 96. I unsuccesfully tried to illustrate the difference between counting and computing.) Bo Jacoby (talk) 21:28, 14 June 2016 (UTC).

And you have exact formulas for mu and sigma, which involve ratios of single sums of simple-to-compute summands. So, something about "ratios of single sums of simple-to-compute summands" is unsatisfactory to you. But this is a pretty nice kind of answer (particularly because the sums don't factor). So could you make a clear statement of what properties an answer should have to be satisfactory? --JBL (talk) 23:32, 14 June 2016 (UTC)

When the formula

$y\approx {\frac {\sum _{y=x}^{n}y2^{x}{\binom {n-x}{n-y}}}{\sum _{y=x}^{n}2^{x}{\binom {n-x}{n-y}}}}\pm {\sqrt {{\frac {\sum _{y=x}^{n}y^{2}2^{x}{\binom {n-x}{n-y}}}{\sum _{y=x}^{n}2^{x}{\binom {n-x}{n-y}}}}-\left({\frac {\sum _{y=x}^{n}y2^{x}{\binom {n-x}{n-y}}}{\sum _{y=x}^{n}2^{x}{\binom {n-x}{n-y}}}}\right)^{2}}}$

is simplified into

$y\approx {\frac {n+x\pm {\sqrt {n-x}}}{2}}$

why can't the formula

$x\approx {\frac {\sum _{x=0}^{y}x2^{x}{\binom {n-x}{n-y}}}{\sum _{x=0}^{y}2^{x}{\binom {n-x}{n-y}}}}\pm {\sqrt {{\frac {\sum _{x=0}^{y}x^{2}2^{x}{\binom {n-x}{n-y}}}{\sum _{x=0}^{y}2^{x}{\binom {n-x}{n-y}}}}-\left({\frac {\sum _{x=0}^{y}x2^{x}{\binom {n-x}{n-y}}}{\sum _{x=0}^{y}2^{x}{\binom {n-x}{n-y}}}}\right)^{2}}}$

also be simplified? Bo Jacoby (talk) 20:28, 15 June 2016 (UTC).

Because the sum $\sum _{k=0}^{n}{\binom {n}{k}}x^{k}$ (essentially, a 1F0 hypergeometric function) and the other sums in the first expression have transformation identities that allow them to be written as products, and then the products cancel. But the series that appear in your example do not factor, so cancellation of the same kind doesn't happen.

(Three things about my comments: (1) I do not consider myself an expert in this area, and in particular I don't have anything to say about why some series factor and others don't. (2) I do not claim that I have provided a rigorous proof of impossibility of anything. (3) It's easy to see that your S_k functions can't factor nicely in general by setting k and y to be small positive integers; you'll get polynomials in n that do not factor nicely.) --JBL (talk) 21:36, 15 June 2016 (UTC)

Thanks! How to find the hypergeometric expressions? Bo Jacoby (talk) 22:54, 15 June 2016 (UTC).

If you mean how to find identities, I suggest the book of Gasper and Rahman or these articles: hypergeometric function, hypergeometric identity, generalized hypergeometric function. If you mean how to express one of your series as a hypergeometric function in its standard form, I would be happy to do an illustrative example of your choosing. --JBL (talk) 16:31, 16 June 2016 (UTC)

I found

$\sum _{i=n}^{N}i{i \choose n}=(n+1){N+2 \choose n+2}-{N+1 \choose n+1}$

which is promising. Can you similarily reduce these?

$\sum _{x=0}^{y}2^{x}{\binom {n-x}{n-y}}$

$\sum _{x=0}^{y}x2^{x}{\binom {n-x}{n-y}}$

$\sum _{x=0}^{y}x^{2}2^{x}{\binom {n-x}{n-y}}$

Bo Jacoby (talk) 20:23, 16 June 2016 (UTC).

These are, respectively, ${\binom {n}{n-y}}{_{2}}F_{1}(1,-y;-n;2)$, $2{\binom {n-1}{n-y}}{_{2}}F_{1}(2,1-y;1-n;2)$, and $2{\binom {n-1}{n-y}}{_{3}}F_{2}(2,2,1-y;1,1-n;2)$. (And these can be written lots of other ways, e.g., using the Euler and Pfaff transformations.) The hypergeometric function with z = 1 is summable to a product (essentially, this is Vandermonde's identity); that's why your first example is nice. The other three examples have z = 2, which is not summable to a product in general. --JBL (talk) 20:50, 16 June 2016 (UTC)

Thank you very much! Bo Jacoby (talk) 08:48, 17 June 2016 (UTC).

Rank deficient variant of matrix orthogonality

An $n\times n$ complex matrix $X$ satisfies this rank deficient variant of the orthogonality condition

$X^{T}X={\text{Diag}}(1,\dots ,1,0).$

where $X^{T}$ is the transpose of $X$. I'd ultimately like to construct the most general solution for $X$, but any pointers or suggestions are as welcome as a solution. Does anyone have any good ideas? Are there any possibly related concepts that you think could help? 92.12.167.39 (talk) 17:55, 11 June 2016 (UTC)

A large class of solutions is obtained by replacing the last column of an orthogonal matrix with 0's. In fact if we were talking about real matrices instead of complex, or using X^*X instead of X^tX then I believe those would be the only solutions. But the possibility of non-zero self-orthogonal vectors throws off my reasoning some. --RDBury (talk) 19:45, 11 June 2016 (UTC)

I think I have the step I was missing so here goes. The first n-1 columns of X are orthonormal; the first step is to show there is an nth column which forms an orthonormal basis for Cⁿ. Let the first n-1 columns be u₁, ... , u_n-1. These are linearly independent. To see this assume a₁u₁+...a_n-1u_n-1=0. Dot product both sides with u_i to get a_i = 0 for any 0. Since the vectors are linearly independent we can add an nth one v to make a basis for Cⁿ. Now let u_n = v - v⋅u₁ u₁ - ... - v⋅u_n u_n, following usual process for forming an orthogonal basis. Then u_n is orthogonal to the other u_i and u₁, ... , u_n is a basis, but I need to show u_n⋅u_n ≠ 0 before going on. (This is where it would be easier if it we were talking about real matrices.)

Write each u_j as y_1je₁+...+y_nje_n, where the e₁ are the standard basis vectors. (In fact the first n-1 columns of Y = (y_ij) are the same as the first n-1 of X, but I won't need that.) Expanding out the dot products, u_i⋅u_j = y_1iy_1j+...+y_niy_nj and so the matrix of dot products is (u_i⋅u_j) = Y^tY. The left hand side, given what we know about the u_i's, is diag(1, ... 1, u_n⋅u_n). The determinant of the The left hand side is then u_n⋅u_n. But Y is a nonsingular matrix so it's determinant is non-zero, and so the right hand side is |Y|² ≠ 0, therefore u_n⋅u_n ≠ 0.

Square roots always exist in C so divide u_n by √(u_n⋅u_n) to make Y an orthogonal matrix, i.e. Y^tY = YY^t = I. (Actually an orthogonal matrix is defined to be over the reals but I'll just stretch the definition a bit.) The first n-1 columns of the original X are u₁, ... , u_n-1 and the last column is some other vector w. Since the u_i's form a basis, write w=b₁u₁+...+b_nu_n. From X^tX=diag(1, ... , 1, 0) we have u_i⋅w = 0 for i<n and w⋅w = 0. Expanding, b_i=0 for i<n, so w=b_nu_n, w⋅w = b_n² = 0 so b_n = 0 and so w = 0. Therefor X is formed by replacing the last column of Y with 0's. Note that the argument fails if we're given X^tX=diag(1, ... , 1, 0, ... , 0) with more than one 0 on the diagonal. --RDBury (talk) 22:05, 11 June 2016 (UTC)

PS. The above reduces the problem to finding the elements of O_n(C). I'm not sure what is known about this group; I think O_n(R) and U_n(C) are better known. Do we have an article on it? --RDBury (talk) 22:11, 11 June 2016 (UTC)

Thanks RDBury, that seems convincing to me. Regarding complex orthogonal matrices. I've seen them come up in dicussions of Lie theory, and we have some brief comments on classical group and orthogonal group. If it helps, I think that based on the Lie group connection, you can construct these matrices by taking a parameterization of SO_n(R) in terms of a set of $n(n-1)/2$ real parameters (for example Euler-like angles) and analytically continuing them. 92.12.167.39 (talk) 09:16, 12 June 2016 (UTC)